Algorytmy triangulacji wielokąta

9

Miałem trudności ze znalezieniem algorytmu lub opublikowaniem artykułów na temat triangulacji samoblokującego się wielokąta (również wielokąta o strukturze dziury).

Czy ktoś może poprowadzić mnie do znalezienia opublikowanej pracy / algorytmu, proszę?

PS: proszę odpowiednio oznaczyć to pytanie, nie mam wystarczającej liczby punktów reputacji, aby to zrobić.

ds.algorithms reference-request cg.comp-geom

— Prashant Cholachagudda
źródło

5

Być może twój nacisk kładzie się na samo-przecinający się aspekt twoich wielokątów? Większość algorytmów (takich jak sugeruje Suresh) zakłada prosty wielokąt. Najpierw musisz obliczyć punkty przecięcia na przejazdach własnych, np. Przez przemiatanie samolotem. Następnie możesz zastosować algorytm Seidela.

— Joseph O'Rourke

4

Czy zastanawiałeś się nad projektem „FIST” Martina Helda ? (Zobacz także artykuł Martina .)

— Jeffε
źródło

7

Czy rozważałeś algorytm Seidela ?

— Suresh Venkat
źródło

Algorytm Seidela, choć bardzo szybki, wymaga modyfikacji w celu obsługi skrzyżowań. To nie jest niemożliwe, ale nie od razu oczywiste.

— Simon F

1

Myślę, że możesz spojrzeć na http://sigbjorn.vik.name/projects/Triangulation.pdf, który był pierwszym wynikiem google dla „samo przecinającego się algorytmu triangulacji wielokąta”, najpierw omówi algorytm Seidela i jego implementację, a następnie go uogólni w „5.2 Skrzyżowania” mówi o samo-przecinających się wielokątach.

— Saeed
źródło