Riduci al minimo i vertici poligonali

Question

Qual è un buon algoritmo per ridurre il numero di vertici in un poligono senza cambiare molto l'aspetto?

Input: un poligono, rappresentato come un elenco di punti, con troppi vertici: input grezzo dal mouse, ad esempio.

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

Modifica: la soluzione a questo sarebbe simile a trovare una linea multi-segmentata di migliore adattamento su un grafico. Si chiama Segmented Least Squares nel mio libro sugli algoritmi.

Modifica2: l'algoritmo Douglas Peucker è ciò che voglio davvero.

Answer 1

Modifica: Oh guarda, Poligoni semplificanti

Hai menzionato il rilevamento delle collisioni. Potresti andare davvero semplice e calcolare uno scafo convesso di delimitazione attorno ad esso.

Se ti occupavi delle aree concave, puoi calcolare uno scafo concavo prendendo il centroide del poligono e scegliendo un punto per iniziare. Dal punto di partenza, ruota attorno al centroide, trovando ogni vertice che desideri mantenere e assegnandolo come vertice successivo nello scafo delimitante. La complessità dell'algoritmo verrebbe dal modo in cui hai determinato quali vertici mantenere, ma sono sicuro che ci hai già pensato. Puoi gettare 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 pieno, è possibile dividerlo. Quindi prendi la media dei vertici in quel secchio come vertice da usare nello scafo delimitante. Oppure dimentica i secchi e quando ti sposti attorno al centroide, scegli un punto solo se è superiore a una determinata distanza dall'ultimo punto.

In realtà, probabilmente potresti semplicemente usare tutti i vertici nel tuo poligono come "nuvola di punti" e calcola lo scafo concavo attorno a quello. Cercherò un collegamento all'algoritmo. Il caso peggiore su questo sarebbe un poligono completamente convesso.

Un'altra alternativa è iniziare con un rettangolo di delimitazione. Per ogni vertice sul 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 raggiunta una parte dei vertici o dell'area. Dovrei pensare un po 'di più ai dettagli di questo.

Se ti interessa che il poligono appaia in modo simile, anche nel caso di un poligono autointersecante, sarebbe necessario un altro approccio, ma non suona come è necessario poiché hai chiesto il rilevamento delle collisioni.

Questo post contiene alcuni dettagli sulla parte dello scafo convesso.

Answer 2

C'è molto materiale là fuori. Google per cose come "riduzione mesh", "semplificazione mesh", "ottimizzazione mesh", ecc.