Riduci a icona Poligono Vertici

Question

Che cos'è un buon algoritmo per ridurre il numero di vertici in un poligono senza cambiare il modo in cui appare molto?

Input: un poligono, rappresentato come un elenco di punti, con troppe vertici: ad esempio, l'input non elaborato dal mouse.

Output: un poligono con molto meno vertici che sembra ancora molto simile all'originale: qualcosa di utile per il rilevamento delle collisioni, ad esempio (non necessariamente convesso).

Modifica: la soluzione sarebbe simile alla ricerca di una linea multi-segmentata di miglior adattamento su un grafico. Si chiama Segmented Least Squares nel mio libro degli algoritmi.

Edit2: L'algoritmo di Douglas Peucker è quello che voglio veramente.

Answer 1

Edit: Oh guarda, Simplifying Polygons

Lei ha parlato di rilevamento delle collisioni. Potresti andare davvero semplice e calcolare attorno ad esso uno scafo convesso.

Se ti interessano le aree concave, puoi calcolare uno scafo concavo prendendo il centroide del poligono e scegliendo un punto da cui iniziare. Dal punto di partenza ruota intorno al centroide, trovando ogni vertice che vuoi mantenere e assegnandolo come il prossimo vertice nello scafo di delimitazione. La complessità dell'algoritmo verrebbe nel modo in cui hai determinato quali vertici mantenere, ma sono sicuro che ci hai già pensato. Puoi lanciare tutti i tuoi vertici in secchi in base alla loro posizione rispetto al centroide. Quando un bucket ottiene più di un numero arbitrario di vertici, puoi dividerlo. Quindi prendi la media dei vertici in quel secchio come il vertice da usare nello scafo delimitante. Oppure, dimentica i secchi, e quando ti muovi attorno al centroide, scegli solo un punto se è più di una distanza dall'ultimo punto.

In realtà, potresti probabilmente utilizzare tutti i vertici del poligono come "nuvola di punti" e calcolare lo scafo concavo attorno a quello. Cercherò un collegamento algoritmo. Il caso peggiore su questo sarebbe un poligono completamente convesso.

Un'altra alternativa è iniziare con un rettangolo di delimitazione. Per ogni vertice del rettangolo, trova la distanza dal punto al poligono. Per il vertice più lontano, dividerlo in altri due vertici e spostarli in alcuni. Ripeti fino a quando non viene soddisfatta una parte dei vertici o dell'area. Dovrei pensare un po 'di più ai dettagli di questo.

Se ci si preoccupa del poligono che sembra effettivamente simile, anche nel caso di un poligono autointersecante, è necessario un altro approccio, ma non sembra necessario poiché si è interrogato sul rilevamento delle collisioni.

Questo post ha alcuni dettagli sulla parte convessa dello scafo.

Answer 2

C'è molto materiale là fuori. Solo Google per cose come "riduzione di maglia", "semplificazione della maglia", "ottimizzazione della maglia", ecc