Algoritmo migliore per trovare i bordi (poligono) dei vertici

Question

Ho una vasta gamma di vertici, alcuni di loro sono bordi, alcuni sono ridondanti (all'interno della forma) e voglio rimuoverli.

L'algoritmo più semplice che potessi pensare è quello di verificare uno ad uno se colpiscono la forma formata dagli altri. Ma dovrebbe essere un algoritmo molto lento.

Ho pensato di sceglierne uno dal bordo (quello più lontano dall'origine per esempio) e calcolare il percorso più lungo da questo inizio ... dovrebbe ottenere il percorso bordo, giusto?

Qualche suggerimento?

Answer 1

Il trucco con gli algoritmi poliedrici è scegliere quello che si adatta al vostro input e al vostro output desiderato, poiché vi è più di un modo per rappresentare un poliedro e la conversione tra le rappresentazioni può essere costosa. In questo caso, stai iniziando con i punti e vuoi finire con i vertici, quindi l'algoritmo Graham scan per calcolare i vertici dello convex hull dovrebbe fare il trucco, anche se potrebbe essere necessario un certo sforzo per estenderlo oltre il caso 2-D. È O (n log n) nel numero di vertici di input.

Answer 2

Non so quale sia il miglior algoritmo per trovare il poligono, ma il poligono che si sta cercando si chiama "Convesso Scafo".

Effettuando una ricerca, è necessario trovare un algoritmo di corrispondenza.

Answer 3

The Convex Hull è uno dei problemi più ricercati della geometria computazionale. Graham Scan è uno dei più semplici convex hull algorithms, ma certamente non l'unico. The Gift-wrapping Algorithm, chiamato anche Jarvis 'March, è il più semplice che io conosca. The Stony Brook algorithm repository ha diverse implementazioni degli algoritmi dello scafo convesso in C e C++. Geometry in Action mostra principalmente applicazioni di scafi convessi. Ecco una raccolta di programmi di calcolo dello scafo convesso low-dimensional e arbitrary-dimensional.