Trova l'asse mediale di un poligono usando C#

Question

Sono stato incaricato di capire come trovare la linea centrale di un poligono. Le mie ricerche su google mi hanno portato a credere che ciò di cui ho bisogno è chiamato "Asse mediale". Come questo:

alt text http://www.ndl.kiev.ua/downloads/center_line.png

Secondo quello che ho letto, quello che mi serve può essere prodotto utilizzando un algoritmo di costruzione diagramma di Voronoi 2D per i segmenti.

ho trovato una versione C# dell'algoritmo Voronoi su CodePlex (FortuneVoronoi) e dopo l'applicazione il mio poligono ad esso, io alla fine con questo:

alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png

Il verde è il poligono originale. L'arancione sono i vertici di Voronoi e le linee nere sono i bordi di voronoi.

Riesco a vedere le caratteristiche di ciò di cui ho bisogno in quei vertici, ma non sono sicuro del prossimo passaggio necessario per filtrare tutte le cose che non mi servono.

Apprezzerei qualsiasi aiuto tu possa offrire.

Answer 1

Una soluzione semplice sarebbe come suggerito nei commenti:

1. Costruire la triangolazione Delaunay dei vertici del poligono.
2. Identificare i vertici Voronoi all'interno del poligono (vedi http://en.wikipedia.org/wiki/Point_in_polygon)
3. uscita il Voronoi bordi collega due vertici interni Voronoi.

Se si dispone di dati enormi, le intersezioni potrebbero essere piuttosto costose.

Quindi si potrebbe fare un approccio simile come nel question e this solution potrebbe funzionare anche per voi. Il modo in cui lo farei:

1. Costruire la triangolazione di Delaunay dei vertici del poligono.
2. Inserire il punto medio di ogni bordo del poligono che non è coperto da un bordo delaunay. Fai questo in modo ricorsivo finché tutti i bordi del poligono non sono coperti da bordi Delaunay.
3. Contrassegnare tutti i bordi di Delaunay che corrispondono a un bordo di poligono.
4. Estrarre l'asse mediale utilizzando i passaggi 3.-5. in this solution

PS. Si noti che entrambe le soluzioni dare qualche approssimazione dell'asse mediano, l'informatica è esattamente molto più costoso, ma come un teaser ... è possibile ottenere risultati come questo per i punti di campionamento di ingresso neri:

Answer 2

Wow. Vado qui su un arto qui e suggerisco che forse l'algoritmo è confuso tra l'interno e l'esterno del poligono. Quando definisci i bordi e i vertici del tuo poligono originale, devi assicurarti che siano definiti in modo tale che "dentro" sia sempre trovato usando qualcosa come la "regola della mano destra". Osservando il poligono nell'angolo in basso a destra, sembra che il bordo del poligono si incrocia effettivamente. Forse l'algoritmo sta vedendo quella sezione, e gli altri, come "dentro e fuori". Lo stesso in basso a sinistra.

Questo è il mio istinto, che l'algoritmo non sembra essere in grado di determinare quale direzione è dentro e ciò che è all'esterno.

Penso che un approccio ingenuo sarebbe quello di filtrare tutti i "nodi" di Voroni che sono al di fuori del poligono, tuttavia, non penso che sembrerà. Osservando più da vicino il diagramma, sembra che ogni nodo abbia 3 spigoli che lo collegano ad altri nodi. Forse puoi filtrare i nodi in cui uno qualsiasi dei 3 lati è collegato a nodi al di fuori del poligono. Funzionerebbe?

Answer 3

Un simile costrutto è lo Straight skeleton, che può essere costruito riducendo il poligono su se stesso e tracciando i vertici mentre si avvicinano al centro. Questo può essere un po 'più facile da costruire, sebbene non sia la stessa curva dell'asse mediale.