Trova punti d'angolo di un Quadrilatero da un insieme di punti

Question

Cerco di ottenere i punti d'angolo di un Quadrilatero da un insieme di punti.

• L'insieme dei punti sono ordinate e descrivere un contorno
• A volte il contorno ha qualche rumore (vedi seconda foto)
• Il ricercato punti d'angolo non devono essere punti fuori del set di data punti (vedi 3 ° in basso a sinistra dell'immagine)
• L'cercato punti d'angolo descrivono un convesso Quadrilatero, non necessariamente un rettangolo

La seconda immagine è un po 'estrema, ma la "qualità" del mio set di punti si trova tra il primo e il secondo quadro.

Prima ho pensato di creare un istogramma da oltre 1-360 ° e la lunghezza, descrivono due punti seguenti. I quattro picchi più alti descrivono la lunghezza di ciascuna linea. Ma con questo perdere i punti ordine, basta conoscere il grado e la lunghezza o una linea e non sapere a quale posizione appartiene una linea.

Poi ho pensato di unire due righe seguenti se hanno più o meno lo stesso grado, ma non so come gestire il rumore qui o prevedere un angolo.

Qualcuno sa di un Algoritmo che gestisce questo problema o qualcosa di simile?

Answer 1

È possibile considerare questo come un problema di clustering, in cui i "centri" del cluster sono in realtà linee rette. Per calcolare il clustering è possibile utilizzare un algoritmo k-means:

1. Scegliere 4 coppie di punti casuali. Adatta una linea a ciascuna, in modo da avere 4 linee che attraversano la nuvola di punti.
2. Ripetere fino a quando la soluzione sembra essere convergente:
   1. Per ciascuno dei punti, calcolare la distanza da ciascuna delle 4 linee.
   2. Assegnare il punto a un secchio che corrisponde alla linea a cui si trova più vicino.
   3. FIT 4 nuove linee ai punti in ciascuno dei 4 secchi (è possibile utilizzare la regressione lineare o SVD)

Per migliorare il primo passo si potrebbe prendere la vostra idea di prendere un istogramma sul angoli e assegnare ciascun punto inizialmente a un secchio corrispondente al picco più vicino. Quindi adattare le linee ai quattro contenitori e iniziare l'iterazione.

Puoi anche considerare questo come un problema di ottimizzazione: scegli 4 punti in modo che l'area della differenza (area bianca all'interno e area nera all'esterno del quadrilatero) sia la più piccola possibile. Probabilmente gli algoritmi di ottimizzazione generici funzionano, ma per velocizzare è necessario un algoritmo ragionevole per calcolare le aree.