Znajdowanie trójkątów

Odpowiedz Nowy wątek
2004-04-15 20:43

Rejestracja: 18 lat temu

Ostatnio: 8 lat temu

0

Mam daną figurę podobną, jak ta z rysunku A: http://thenkles.w.interia.pl/triangles.jpg. Problem polega na znalezieniu wszystkich trójkątów, jakie można odnaleźć w tejże figurze. Wszystkie trójkąty dla tego przykładu zaznaczone są na rysunkach B-E. Posiadam współrzędne wszystkich linii osobno (czyli w tym przypadku osobno dwie linie na każdy bok dużego trójkąta), tym samym także wszystkie wierzchołki. Jak się za to zabrać?

Pozostało 580 znaków

2004-04-16 13:17

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

Rozwiazywalem kiedys takie zadanie!! [hurra]
No prawie. To byl jeden z problemow czesciowych. Mialem pewnosc, ze calosc miesci sie w jednym trojkacie. Zaczynalem przechodzic po calym trojkacie od jednego boku i rekurenycjnie "rozdzielac" sciezke w kazdym kierunku. Takie sprawdzanie nalezalo wykonac od kazdego wierzcholka i kierunek poruszania sie po trojkatach zawsze byl w kierunku ruchu wskazowek zegara. Tym sposobem zawsze wyznaczylo sie wszystkie mozliwe trojkaty.


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

TKW
2004-08-26 11:49
TKW

Rejestracja: 15 lat temu

Ostatnio: 15 lat temu

0

Aby podzielić dowolny wielokąt na trójkąty, należy:
mieć współrzędne kolejnych wierzchołków, i
kolejnemu trójkątom dawać co drugi wierzchołek,
jednocześnie dawać wierzchołki dwom trójkątom,
skończyć, gdy każdy wierzchołek zostanie użyty.

Pozostało 580 znaków

2004-08-26 21:36

Rejestracja: 16 lat temu

Ostatnio: 14 lat temu

0

W przypadku bardziej skomplikowanych figur może być ciężko z prostym wyliczeniem trójkątów. Ja bym to zrobił tak:

Najpierw musimy policzyć ilość wszystkich odcinków (dane do zadania to nie są wszystkie odcinki!). Najlepiej będzie chyba dla każdego danego odcinka policzyć prostą na jakiej się znajduje . Teraz posortowałbym odcinki, jako podstawowe kryterium sortowania przyjmowałbym prostą na której znajduje się odcinek, a wśród odcinków na tej samej prostej współrzędną x początku odcinka (przyjmuję, że odcinek jest skierowany w prawo) i ewentualnie współrzędnej y, jeżeli współrzędna x jest identyczna. Z tak posortowanych odcinków mogę zliczać grupy odcinków, które są połączone. Funkcja licząca ilosc odcinkow w grupie składającej się z n połączonych odcinków może wyglądać tak:

int ilosc(int n)
{
    if (n>1) return (n-1) + ilosc(n-1);
    else return 0;
}

Jednak przydałoby się dodać te "nowe" odcinki do zbioru wszystkich odcinków, aby mieć je później do dalszej analizy. Napisanie odpowiedniej funkcji nie powinno stanowić problemu. Teraz bieżemy dwa odcinki o wspólnym punkcie (początek lub koniec) i sprawdzamy czy w zbiorze odcinków istnieje odcinek, który domknie je do trójkąta.

Teraz małe rozwarzanie na temat implementacji. Jako strukturę do przechowywania danuch o odcinkach użyłbym drzewa binarnego - jest proste w implementacji i powinno dać wystarczająco dobre rezultaty. Dodatkowo, łatwo dodawać do niego elementy (choć dodawane "nowe" odcinki będą posortowane z racji metody tworzenia, co może stworzyć długie "gałęzie" w naszym drzewku ).

Nie mam pomysłu na wydajne szukanie połączonych odcinków, ale pewnie przepisałbym wszystkie do tablicy i sprawdzał każde 2 odcinki (wyjdzie mi wtedy 3 razy tyle trójkątów! - wynik trzeba podzielić przez 3) . Więc do czego było mi drzewo binarne? Możemy w nim szybko sprawdzić czy istnieje odcinek "domykający".

Nie wiem jak zadziała to w praktyce, ale powinno być dobrze :d


Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0