Najlepszy algorytm do znajdowania krawędzi (wielokątów) wierzchołków

Question

Mam duży wachlarz wierzchołków, niektóre z nich to krawędzie, niektóre są zbędne (wewnątrz kształtu) i chcę je usunąć.

Najprostszym algorytmem, jaki mógłbym wymyślić, to sprawdzanie pojedynczo, jeśli uderzy w kształt utworzony przez inne. Ale powinien to być bardzo powolny algorytm.

Myślałem o wybraniu jednego z brzegu (najdalej od pochodzenia na przykład) i obliczeniu najdłuższej ścieżki od tego początku ... powinienem uzyskać ścieżkę krawędzi, prawda?

Jakieś sugestie?

Answer 1

Trik z wielościennymi algorytmami wybiera taki, który pasuje do twojego wejścia i pożądanej wydajności, ponieważ istnieje więcej niż jeden sposób reprezentowania wielościanu, a konwersja pomiędzy reprezentacjami może być kosztowna. W tym przypadku zaczynasz od punktów i chcesz zakończyć wierzchołkami, więc algorytm Graham scan obliczania wierzchołków convex hull powinien zrobić lewy, choć może to wymagać trochę wysiłku, aby przedłużyć go poza przypadek 2-D. Jest to O (n log n) w liczbie wierzchołków wejściowych.

Answer 2

Nie wiem, jaki najlepszy algorytm można znaleźć, ale wielokąt, którego szukasz, nazywa się "kadłubem wypukłym".

Wyszukując to, powinieneś znaleźć pasujący algorytm.

Answer 3

The Convex Hull to jeden z bardziej zbadanych problemów Geometrii Obliczeniowej. Graham Scan jest jednym z prostszych convex hull algorithms, ale z pewnością nie jedynym. The Gift-wrapping Algorithm, zwany także Marszem Jarvisa, jest najprostszy, jaki znam. The Stony Brook algorithm repository ma kilka implementacji algorytmów wypukłych kadłubów w C i C++. Geometry in Action pokazuje głównie zastosowania wypukłych kadłubów. Oto zbiór programów do obliczania wypukłych kadłubów low-dimensional i arbitrary-dimensional.