Minimalizuj wierzchołki wielokątów

Question

Jaki jest dobry algorytm zmniejszania liczby wierzchołków w wielokącie bez zmiany sposobu, w jaki wygląda bardzo?

Wejście: wielokąt, reprezentowana jako lista punktów, ze zbyt wielu verticies: surowy wejście od myszy, na przykład.

Wyjście: wielokąt o mniejszej liczbie punktów w pionie, który nadal wygląda bardzo podobnie do oryginału: coś użytego do wykrywania kolizji, na przykład (niekoniecznie wypukły).

Edit: Rozwiązaniem tego problemu byłoby podobne do znalezienia wielo-segmentową linię najlepszego dopasowania na wykresie. W mojej książce algorytmów nazywa się "Najmniejsze kwadraty".

Edycja2: Algorytm Douglas Peucker jest tym, czego naprawdę chcę.

Answer 1

EDIT: O popatrz, Simplifying Polygons

Wspomniałeś wykrywania kolizji. Możesz pójść naprawdę prosto i obliczyć wokół niego otaczający go wypukły kadłub.

Jeśli dbał o wklęsłych obszarów, można obliczyć wklęsły kadłub biorąc ciężkości swojego wieloboku i wybranie punktu rozpoczęcia. Od punktu początkowego obróć się wokół środka ciężkości, znajdując każdy wierzchołek, który chcesz zachować, i przypisując go jako następny wierzchołek w kadłubie ograniczającym. Złożoność algorytmu polegałaby na określeniu, które wierzchołki należy zachować, ale jestem pewien, że już o tym pomyślałeś. Możesz rzucić wszystkie swoje wierzchołki do wiader na podstawie ich położenia względem środka ciężkości. Gdy wiadro osiągnie więcej niż dowolna liczba wierzchołków, możesz je podzielić. Następnie weź średnią wierzchołków w tym wiadrze jako wierzchołek, który ma zostać użyty w kadłubie ograniczającym. Albo zapomnij o kubłach, a kiedy poruszasz się po centroidzie, wybierz punkt, jeśli jest on większy niż odległość od ostatniego punktu.

Faktycznie, można prawdopodobnie wystarczy użyć wszystkie wierzchołki wielokąta, jak w „chmury punktów” i obliczyć wklęsły kadłub wokół tego. Poszukuję linku algorytmu. Najgorszym przypadkiem byłby całkowicie wypukły wielokąt.

Inną alternatywą jest rozpoczęcie od prostokąta obwiedni. Dla każdego wierzchołka prostokąta znajdź odległość od punktu do wielokąta. Dla najdalszego wierzchołka podziel go na dwa dodatkowe wierzchołki i przenieś w niektórych. Powtarzaj, dopóki pewna część obu wierzchołków lub obszaru nie zostanie osiągnięta. Musiałbym trochę więcej przemyśleć szczegóły tego jednego.

Jeśli zależy ci na tym, aby wielokąt rzeczywiście wyglądał podobnie, nawet w przypadku wielokąta przecinającego się, konieczne byłoby inne podejście, ale nie brzmi tak, ponieważ jest to konieczne, ponieważ pytasz o wykrywanie kolizji.

Ten post ma pewne szczegóły o wypukłej części kadłuba.

Answer 2

Jest dużo materiału. Tylko google na takie rzeczy jak „redukcji oczek”, „uproszczenia”, „oczek optymalizacji oczek”, itp