Znajdowanie trójkątów

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ć?

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.

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.

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

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