Autor Wątek: Triangulacja  (Przeczytany 1897 razy)

Offline counterClockWise

  • Użytkownik

# Czerwiec 27, 2007, 17:18:09

Szukam rzetelnych informacji na temat triangulacji losowej chmury dużej ilości dość blisko rozmieszczonych punktów. Googluje, ale ciągle trafiam na rozprawy doktorskie, ustawione pod specyficzny problem (wiem, że nie ma idealnej metody) albo znaną wszystkim Delaunay lub Rekurencyjnego Przeglądania Kątów.
Macie jakieś hasła (nazwy algorytmów...itp), pod którymi mógłbym szukać dalej w jakimś stopniu przez was sprawdzone/zasłyszane ?
 

Offline Mr. Spam

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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 27, 2007, 17:56:46
Może już mam taki odchył, ale ja bym spróbował wymyśleć coś samemu, na przykład dodawać krawędzie* w kolejności od najkrótszych, wyłączając te krawędzi, które powodowały by powstanie trzech trójkątów o wspólnej krawędzi. Na koniec trzeba oczywiście wyczyścić wynik z niepotrzebnych krawędzi i gotowe. Można tutaj optymalizować zbiór krawędzi, które rozwarzamy ignorując krawędzie powyżej okreslonej długości i/lub dla każdego wierzchołka wybierając jedynie określoną ilość krawędzi z nim sąsiadujących. :)

* zakładam, że krawędź może łączyć dwa dowolne wierzchołki

Offline counterClockWise

  • Użytkownik

# Czerwiec 27, 2007, 17:59:16
Może już mam taki odchył, ale ja bym spróbował wymyśleć coś samemu, na przykład dodawać krawędzie

Na tym sie pewnie skończy ;)

Offline Areal

  • Użytkownik

# Czerwiec 27, 2007, 18:28:02
Niedawno miałem do napisania algorytm triangulacyjny i stanąłem przed podobnym problemem. W sieci pełno jest materiałów na temat triangulacji Delaunay, ale mnie osobiście ten algorytm nie satysfakcjonował. No i wymyśliłem coś takiego (sprawdzone i działa):
1) tworzony jest prostokąt, który złożony jest z 2 trójkątów
2) wstawianie punktu polega na:
 a) wybraniu krawędzi startowej,
 b) poruszanie sie po siatce od danej krawędzi startowej do punktu, który ma być wstawiony,
 c) wstawienie punktu, co wiąże się z podziałem danego trójkąta na 3 mniejsze,
 d) lokalna optymalizacja pobliskich trójkątów za pomocą przerzucania przekątnych wg kryterium większych kątów

Dodatkowo jeśli punktu są wstawiane jeden za drugim, czyli znajdują się blisko siebie na płaszczyźnie, to ustawiając krawędź startową na ostatnio stworzoną, możemy uzyskać algorytm działający w czasie liniowym dla określonych przypadków.
Oczywiście osobnym (i chyba najważniejszym) problemem jest tu dobór odpowiedniej struktury danych reprezentujących taką siatkę. U mnie podstawowym elementem siatki była krawędź, która zawierała 2 punkty oraz wskaźniki na sąsiednie krawędzie. W jednej z wersji udało mi się zoptymalizować algorytm tak, że dla miliona punktów działał w kilka sekund.

Offline Spider100

  • Moderator
    • Strona domowa

# Czerwiec 28, 2007, 11:31:12
Cytuj
W sieci pełno jest materiałów na temat triangulacji Delaunay, ale mnie osobiście ten algorytm nie satysfakcjonował.
Który algorytm bo tych jest z kolei dużo jest to jeden z najlepszych sposobów triangulacji :D

Polecam zainteresować się diagramem Voronoi jest to obiekty dualny do siatki triangulacji więc łatwo przekształcić.

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Czerwiec 28, 2007, 12:38:20
Zobacz może Marching Cubes Algorithm.

Offline counterClockWise

  • Użytkownik

# Czerwiec 28, 2007, 14:04:31
Zobacz może Marching Cubes Algorithm.

Hehe :) Akurat ten algorytm mi sie po nocach śni, znam go bardzo dobrze.
Diagramy Voronoi i tak przeważnie prowadzą ostatecznie do Delaunay ;)

Dzięki za odpowiedzi - doszedłem do wniosku że posiedzę nad tym dłużej i spróbuje dojść do czegoś łączącego zalety wszystkich metod:)


edit: O jaką okrągła liczbe wiadomości mam ;)