Autor Wątek: Algorytm łączenia wierzchołków w trójkąty  (Przeczytany 1937 razy)

Offline zwierz

  • Użytkownik

# Październik 21, 2009, 12:30:32
Witam,

Poszukuję algorytmu, który przyjmując zbiór wierzchołków łączyłby je w trójkąty w taki sposób, że wnętrze figury powstałej przez połączenie kolejnych wierzchołków byłoby wypełnione trójkątami.

Oto rysunek (made in Paint) obrazujący problem:


Numery oznaczają kolejne wierzchołki. Wierzchołki łączone są zgodnie z numeracją. Czerwone linie oznaczają krawędzie figury natomiast niebieskie krawędzie trójkątów. Sposób połączenia wnętrza figury w trójkąty jest bez znaczenia byle figura zoastała wypełniona w pełni i żeby żaden trójkąt nie wychodził poza krawędzie figury np. trójkąt {1,3,4} lub {2,3,4}.

Interesuje mnie cokolwiek co mogłoby rozwiązać ten problem. Korzystam z biblioteki Papervision3D do Adobe Flex.
« Ostatnia zmiana: Październik 22, 2009, 16:19:33 wysłana przez zwierz »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Angru

  • Użytkownik

# Październik 21, 2009, 12:32:34
Poczytaj o delaunay triangulation.

Offline zwierz

  • Użytkownik

# Październik 21, 2009, 13:09:08
Niestety nie do końca dobry jest ten algorytm bo nie sprawdza się w przypadku figur wklęsłych :(
Korzystając z appletu http://www.cs.cornell.edu/Info/People/chew/Delaunay.html i rysując kształt, który przedstawiłem w pierwszym poście widać, że utworzone zostaną trójkąty (2,3,4), (5,6,7), (8,9,10) i (11,12,1), które są niepożądane.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 21, 2009, 13:48:24
Cytuj
Poczytaj o delaunay triangulation.
Z reguły to jest dobry strzał, ale w tym przypadku - pudło.


Najprostszy algorytm to "ear clipping" (aka przycinanie uszu). Skoro masz obwód obiektu, to szukasz na tym obwodzie trzech kolejnych wierzchołków, które tworzą dopuszczalny trójkąt (czyli tworzą kąt ostry i trójkat nie zawiera w swoim wnętrzu innych wierzchołków obwodu). Jak już taki trójkąt znajdziesz, wycinasz go z obwodu przez usunięcie szczytowego wierzchołka i kontynuujesz proces, dopóki masz trzy lub więcej wierzchołków w obwodzie.

Offline zwierz

  • Użytkownik

# Październik 21, 2009, 16:11:10
Dzięki, to jest dokładnie to czego mi potrzeba.

Offline Xion

  • Redaktor
    • xion.log

# Październik 21, 2009, 18:18:11
Pozwolę sobie wskazać, iż coś takiego zdarzyło mi się opisać tutaj:

http://xion.org.pl/2008/04/27/podzial-wielokatow-na-trojkaty/

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 21, 2009, 18:25:35
Pozwolę sobie wskazać, iż coś takiego zdarzyło mi się opisać tutaj:

http://xion.org.pl/2008/04/27/podzial-wielokatow-na-trojkaty/
Algorytm w Twoim opisie jest nieco trudniejszy w implementacji i używa pojęć typu "mieści się w wielokącie" oraz "czy da się połączyć", co sugeruje, że chcesz sprawdzac przecinanie się krawędzi. Tymczasem, jak napisałem powyżej, wystarczy sprawdzić, czy w nowo tworzonym trójkącie znajduje się jakikolwiek z pozostałych wierzchołków wielokąta. Przy założeniu, że obwód wielokąta nie przecina sam siebie wychodzi dokładnie na to samo. :)


EDIT: Ale i tak znacznie lepsza jest zabawa z triangulacją wielokątów z dziurami, zwłaszcza jeżeli są one umieszczone pod dowolnym kątem w przestrzeni 3D, a do tego mogą posiadać wierzchołki współliniowe na obwodach. :)
« Ostatnia zmiana: Październik 21, 2009, 18:27:54 wysłana przez Krzysiek K. »

Offline Limal

  • Użytkownik
    • http://wolnik.co.uk

# Październik 21, 2009, 19:02:43
Używam TetGena i jestem zadowolony :)

Offline zwierz

  • Użytkownik

# Październik 22, 2009, 16:19:15
Niestety muszę odświeżyć wątek ponieważ podczas próby implementacji napotkałem na problem, którego nie potrafię rozwiązać.

Otóż ogólnie algorytm "ear clipping" polega na iteracji po kolejnych wierzchołkach wielokąta i sprawdzaniu czy w trójkącie utworzonym przez wierzchołki (Vi-1,Vi,Vi+1) znajduje się jakiś innych wierzchołek czy nie. Jeżeli nie znajduje się wtedy wierzchołek Vi jest uchem trójkąta co oznacza że usuwa się go z listy wierzchołków po, których się iteruje a tworzony przez niego trójkąt dodaje się do listy trójkątów budujących wielokąt.

Problem polega na tym, że trójkąt (Vi-1,Vi,Vi+1) można badać pod kątem zawierania innych wierzchołków tylko wtedy kiedy kąt przy wierzchołku Vi jest mniejszy od 180 stopni. Odnosząc się do rysunku, który wstawiłem w pierwszym poście trójkąt utworzony przez wierzchołki (2,3,4) (przestrzeń pomiędzy prawym a górnym ramieniem krzyża) nie zawiera żadnych wierzchołków więc zostałby dodany do listy trójkątów budujących wielokąt mimo, że nie powinien. Dzieje się tak ponieważ kąt przy wierzchołku 3 jest równy 270 stopni i dlatego trójkąt (2,3,4) w ogólnie nie powinien być poddawany testowi na zawieranie innych wierzchołków.

Muszę więc w jakiś sposób sprawdzac czy kąt przy aktualnie przetwarzanym wierzchołku jest mniejszy czy większy od 180. Jedyne rozwiązanie jakie przyszło mi do głowy to liczenie iloczynu skalarnego wektorów tworzących ramiona kąta przy badanym wierzchołku. Tu z kolei okazuje się jest to niemożliwe ponieważ arccos zwraca wartości z przedziału (0,180) i w przypadku chęci zbadania kąta przy wierzchołku 3 dowiem się że ma on wartość 90 stopni (a nie 270).

Gdybym mógł stwierdzić czy wartość arccos dla badanego wierzchołka jest wartością katą wewnętrznego czy zewnętrznego wielokąta to nie byłoby problemu bo w przypadku zwrócenia wartości dla kąta zewnętrznego odejmowałbym otrzymaną wartość od 360 i wiedziałbym czy poddawać dany trójkąt testowaniu czy nie.

Jedyny sensowny opis algorytmu "ear clipping" znalazłem pod tym adresem http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Jakoś ludzie to implementują więc musi być sposób na przejście tego problemu. Proszę o pomoc bo coś czuję, że sam nie dam rady :)

Ps.
TetGen nie wchodzi w grę bo to biblioteka c++ a ja piszę w actionscripcie.
« Ostatnia zmiana: Październik 22, 2009, 16:25:00 wysłana przez zwierz »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 22, 2009, 17:19:58
Cytuj
Muszę więc w jakiś sposób sprawdzac czy kąt przy aktualnie przetwarzanym wierzchołku jest mniejszy czy większy od 180. Jedyne rozwiązanie jakie przyszło mi do głowy to liczenie iloczynu skalarnego wektorów tworzących ramiona kąta przy badanym wierzchołku. Tu z kolei okazuje się jest to niemożliwe ponieważ arccos zwraca wartości z przedziału (0,180) i w przypadku chęci zbadania kąta przy wierzchołku 3 dowiem się że ma on wartość 90 stopni (a nie 270).
Arccos?? Jeżeli w obliczeniach geometrycznych zaczynają Ci się pojawiać funkcje trygonometryczne, to najprawdopodobniej masz coś źle. Nie prościej sprawdzić, po której stronie prostej Vi-1 Vi leży punkt Vi+1?

Offline zwierz

  • Użytkownik

# Październik 23, 2009, 15:07:02
Arccos wyszedł w naturalny sposób z iloczynu skalarnego, ale skoro mówisz, że lepiej nie używać funkcji trygonometrycznych to z racji mojego znikomwgo doświadczenia w tej dziedzinie wierzę, że masz rację. Twoja sugestia o sprawdzaniu po której stronie prostej Vi-1 Vi leży punkt Vi+1 doprowadziła mnie do wniosku, że to nic nie da więc sięgnąłem do źródeł implementacji "ear clipping" na stronie geometrictools.com (klik), ale o tym później. Najpierw chciałem wyjaśnić problem związany ze sprawdzaniem położenia punku Vi+1 względem prostem Vi-1 Vi.



Otóż dla wierzchołka 3 punkt Vi+1 leży po prawej stronie odpowiedniej prostej, ale punkt Vi+1 znajduje się też po prawej stronie odpowiednich prostych wierzchołków 1 i 11. Kat przy wierzchołku 3 jest wklęsły natomiast przy wierzchołkach 1 i 11 wypukły. Taka metoda nie pozwala jednoznacznie stwierdzić jaki jest kąt przy badanym wierzchołku.

Wracając do źródeł tego co znalazłem na geometrictools.com:
Autor w funkcji isConvex(i:int) sprawdzającej czy wierzchołek o numerze i jest wypukły wywołuje funkcję toLine, która sprawdza po której stronie jakiejś prostej - trudno mi wywnioskować z kodu ponieważ nie pojmuje jego matematycznego sensu - leży badany punkt. Jeżeli leży po prawej wtedy funkcja uznaje badany wierzchołek za wypukły, w przeciwnym razie za wklęsły.

Wygląda więc na to, że masz rację ze sprawdzaniem położenia punktu względem prostej w celu określenia czy kąt przy danym wierzchołku jest wklęsły czy wypukły. Proszę więc rozwiń swoją myśl tak żebym i ja mógł zrozumieć :)


Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Październik 23, 2009, 15:34:53
Cytuj
Otóż dla wierzchołka 3 punkt Vi+1 leży po prawej stronie odpowiedniej prostej
Nieprawda. Dla wierzchołka 3 punkt Vi+1 leży po LEWEJ stronie prostej 2-3. Zapomniałes o fakcie, że prosta 2-3 biegnie w dół. :)