Il miglior algoritmo per trovare i bordi (poligono) dei vertici

Question

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

L'algoritmo più semplice che mi viene in mente è controllare uno per 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 del bordo, giusto?

Qualche suggerimento?

Answer 1

Il trucco con algoritmi poliedrici è quello di scegliere quello che si adatta al tuo input e all'output desiderato, poiché esiste più di un modo per rappresentare un poliedro e la conversione tra le rappresentazioni può essere costosa. In questo caso, stai iniziando con punti e vuoi finire con vertici, quindi l'algoritmo Graham scan per calcolare i vertici dello scafo convesso dovrebbe fare il trucco, anche se potrebbe richiedere qualche sforzo per estendere 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 quel poligono, ma il poligono che stai cercando si chiama " Convex Hull " ;.

Cercandolo, dovresti trovare un algoritmo corrispondente.

Answer 3

Lo scafo convesso è uno dei problemi più ricercati della geometria computazionale. Graham Scan è uno dei più semplici algoritmi dello scafo convesso , ma certamente non l'unico. L'algoritmo di confezione regalo , chiamato anche Jarvis 'March, è il più semplice che io conosca. Il repository degli algoritmi Stony Brook ha diverse implementazioni dello scafo convesso algoritmi in C e C ++. Geometry in Action mostra principalmente applicazioni di scafi convessi. Ecco una raccolta di a bassa dimensione e programmi di calcolo dello scafo convesso arbitrari