Calcola Voronoi attorno al poligono

Question

Devo generare un Voronoi diagram attorno a un poligono concavo (non convesso) all'interno. Ho cercato metodi online, ma non sono stato in grado di capire come farlo. Fondamentalmente, genero lo scafo convesso dei punti, calcola i doppi punti e costruisco una rete di bordo tra questi punti. Tuttavia, quando si incontrano i bordi del poligono interno, deve assomigliare al bordo della forma, proprio come lo scafo convesso. Quindi, facendo questo e tagliando tutti i bordi ai bordi, dovrei finire con un diagramma di Voronoi che ha dei bordi piacevoli ai bordi del poligono interno e nessuna cella che si trova su entrambi i lati del poligono interno.

Vi faccio un esempio:

Il problema di questo è che le cellule attraversano i bordi poligono all'interno e non v'è alcuna relazione visiva tra la struttura cellulare e la forma poligonale.

Qualcuno sa come affrontare questo problema? C'è qualche algoritmo che fa già questo o si avvicina a quello che sto cercando di ottenere?

Grazie mille per qualsiasi tipo di input!

Answer 1

Potrebbe essere possibile costruire una triangolazione di Delaunay conforme (ad esempio una triangolazione che include i bordi del poligono come vincoli) e quindi formare il diagramma Voronoi come doppio. Una triangolazione conforme assicurerà che nessun bordo nella triangolazione si intersechi con un bordo di vincolo: tutti i bordi di vincolo saranno un bordo nella triangolazione.

Dai un'occhiata al pacchetto Triangle here, come riferimento per questo tipo di approccio. Nella mia esperienza è una libreria veloce e solida, sebbene sia scritta in c non java.

Non sono sicuro di capire a questo punto in che modo i punti (i centri di Voronoi) sono generati nel diagramma. Se si sta effettivamente cercando di generare mesh in un dominio poligonale, potrebbero esserci altri approcci da considerare, sebbene il pacchetto Triangle supporti la generazione di mesh di perfezionamento Delaunay (conforme).

MODIFICA: Sembra che sia anche possibile creare direttamente il diagramma di Voronoi per i segmenti di linea generali, controllare la libreria VRONI, here. Affrontare il tuo commento - Non sono sicuro che puoi sempre aspettarti di avere un diagramma Voronoi uniforme che sia anche conforme a un limite poligonale generale. Mi aspetterei che la forma del limite poligonale imporrebbe una dimensione massima sulle celle Voronoi di confine.

Spero che questo aiuti.

Answer 2

Chiaramente è necessario generare il diagramma di Voronoi sui vincoli del poligono maggiore. Sebbene tu ti riferisca ad esso come un poligono, noto che il tuo diagramma di esempio ha bordi basati su spline. Dimentichiamo quello per ora.

Quello che vuoi fare è assicurarti di iniziare con il poligono contenente (sia generato da te che da un'altra fonte) con bordi di lunghezza abbastanza uguale; un fattore di varianza renderebbe questo aspetto più naturale. Probabilmente opterei per una varianza del 10-20%.

Ora che hai il poligono contenente delimitato da segmenti di segmenti di lunghezza approssimativamente uguale, hai una base da cui iniziare a generare il tuo diagramma di Voronoi.Per ogni spigolo sul tuo contenitore:

• Determina il bordo normale (la linea perp si protende verso l'interno dal centro di quel segmento).
• Utilizzare il bordo normale come scala mobile su cui posizionare un nuovo centro nodo Voronoi. La distanza dal bordo stesso sarebbe determinata da ciò che si desidera che il "diametro" della cella Voronoi medio sia, se fossero tutti presi come cerchi. Nel tuo esempio assomiglia a circa 30 pixel (o qualunque sia l'equivalente nelle unità del tuo mondo). Di nuovo, dovresti applicare un fattore di varianza a questo in modo che non tutti i centri cellulari siano posti equidistanti dal suo bordo sorgente.
• Genera la cella Voronoi per il tuo nuovo centro.
• Memorizza il punto di origine della cella Voronoi in un elenco.

Come si genera in modo incrementale ogni punto, è necessario iniziare a vedere che l'algoritmo suddivide ogni convessa "area costituente" del contenitore concavo in modo radiale.

Forse ti starai chiedendo a cosa serve l'elenco. Beh, ovviamente, non hai ancora finito, hai generato solo una frazione della tessellazione Voronoi che desideri. Una volta create queste celle "limite" del tuo spazio concavo, non vuoi che nuove celle vengano generate più vicino al confine di quanto lo siano già le celle di confine, le vuoi solo all'interno di quell'area. Mantenendo un elenco dei punti di origine della cella limite, è possibile verificare che qualsiasi altro punto creato sia all'interno dell'area nell'area. È un po 'come prendere una somma Minkowski interna per assicurarti di avere una zona cuscinetto. Ora puoi randomizzare il resto delle tue cellule in questo spazio concavo derivato, fino al completamento.

(Caveat emptor: Dovrai fare attenzione con questo passaggio precedente.Se le eventuali aree di "passaggio" sono troppo strette, i confini di questo spazio derivato si sovrappongono, avrai un poligono non semplice, e tu potresti trovarti a piazzare punti nei posti sbagliati nonostante i tuoi sforzi.La soluzione è quella di garantire che la distanza massima di posizionamento dai bordi non sia mai superiore alla metà della larghezza minima di passaggio ... o usi qualche altro mezzo geometrico, incluso Minkowski sommatoria come una possibilità, per assicurarti di non finire con un poligono derivato degenerato.È abbastanza probabile che finirai con un multipoligono, cioè frammenti.)

Non ho ancora applicato questo metodo, ma nonostante ci saranno sicuramente degli errori da risolvere, penso t L'idea generale ti farà iniziare nella giusta direzione.

Answer 3

Cercare un articolo intitolato:

"efficiente calcolo degli scheletri continui" di Kirkpatrick, David G, scritto nel 1979.

Ecco il riassunto:

An Algoritmo O (n lgn) è presentato per la costruzione di scheletri di figure poligonali arbitrarie di n-linee. Questo algoritmo si basa su un algoritmo O (n lgn) per la costruzione di diagrammi Voronoi generalizzati (la nostra generalizzazione sostituisce i set di punti con serie di segmenti segmenti vincolati da intersecare solo nei punti finali). L'algoritmo di diagramma Voronoi generalizzato impiega un algoritmo di tempo lineare per la fusione di due diagrammi Voronoi arbitrari (standard).

"insiemi di segmenti di linea rappresenta l'costretti ad intersecare solo nei punti finali" è il poligono concavo si descrive.