Un algoritmo per gonfiare / sgonfiare (compensare, buffering) i poligoni

Come faccio a “gonfiare” un poligono? Cioè, voglio fare qualcosa di simile a questo:

alt text

Il requisito è che i nuovi bordi / punti del poligono (gonfiati) siano tutti alla stessa distanza costante dal vecchio (originale) poligono (nell’immagine di esempio non lo sono, da allora dovrebbe usare archi per i vertici gonfiati, ma facciamo dimenticarlo per ora;)).

Il termine matematico per ciò che sto cercando è in realtà il poligono verso l’interno / l’esterno . +1 a Balint per indicarlo. La denominazione alternativa è il buffer poligonale .

Risultati della mia ricerca:

    Ecco alcuni link:

    • Un’indagine sulle strategie di compensazione del poligono
    • Offset poligono, PROBLEMA
    • Buffering Polygon Data

    Ho pensato di poter menzionare brevemente la mia libreria poligonale di ritaglio e sfalsamentoClipper .

    Mentre Clipper è progettato principalmente per operazioni di clipping poligonale, esegue anche la compensazione del poligono. La libreria è freeware open source scritto in Delphi, C ++ e C # . Ha una licenza Boost molto ingombrante che ne consente l’uso sia in applicazioni freeware che commerciali senza costi aggiuntivi.

    La compensazione del poligono può essere eseguita utilizzando uno dei tre stili di sfalsamento: quadrato, rotondo e mitra.

    Stili di compensazione poligonali

    Il poligono che stai cercando è chiamato poligono di offset verso l’interno / verso l’esterno nella geometria computazionale ed è strettamente correlato allo scheletro lineare .

    Questi sono diversi poligoni offset per un poligono complicato:

    E questo è lo scheletro dritto per un altro poligono:

    Come sottolineato anche in altri commenti, a seconda di quanto si intende “gonfiare / sgonfiare” il poligono, si può finire con una connettività diversa per l’output.

    Dal punto di vista del calcolo: una volta ottenuto lo scheletro rettilineo, si dovrebbe essere in grado di build i poligoni offset relativamente facilmente. La libreria CGAL open source e (gratuita per non commerciale) ha un pacchetto che implementa queste strutture. Guarda questo esempio di codice per calcolare i poligoni offset utilizzando CGAL.

    Il manuale del pacchetto dovrebbe darti un buon punto di partenza su come build queste strutture anche se non intendi usare CGAL e contiene riferimenti ai documenti con le definizioni e proprietà matematiche:

    Manuale CGAL: scheletro dritto 2D e compensazione del poligono

    Mi sembra che quello che vuoi sia:

    • Partendo da un vertice, girare in senso antiorario lungo un bordo adiacente.
    • Sostituire il bordo con un nuovo bordo parallelo posizionato alla distanza d alla “sinistra” di quello vecchio.
    • Ripeti per tutti i bordi.
    • Trova le intersezioni dei nuovi bordi per ottenere i nuovi vertici.
    • Rileva se sei diventato un polinomiale incrociato e decidi cosa fare al riguardo. Probabilmente aggiungere un nuovo vertice al punto di incrocio e sbarazzarsi di alcuni vecchi. Non sono sicuro se ci sia un modo migliore per rilevare questo oltre al semplice confronto di ogni coppia di bordi non adiacenti per vedere se la loro intersezione si trova tra entrambe le coppie di vertici.

    Il poligono risultante si trova alla distanza richiesta dal vecchio poligono “abbastanza lontano” dai vertici. Vicino a un vertice, l’insieme di punti alla distanza d dal vecchio poligono è, come dici tu, non un poligono, quindi il requisito dichiarato non può essere soddisfatto.

    Non so se questo algoritmo ha un nome, codice di esempio sul web o un’ottimizzazione diabolica, ma penso che descriva quello che vuoi.

    Non ho mai usato Clipper (sviluppato da Angus Johnson) ma per questi tipi di cose di solito uso JTS . A scopo dimostrativo, ho creato questo jsFiddle che utilizza JSTS (porta JavaScript di JTS). Hai solo bisogno di convertire le coordinate che hai in coordinate JSTS:

     function vectorCoordinates2JTS (polygon) { var coordinates = []; for (var i = 0; i < polygon.length; i++) { coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y)); } return coordinates; } 

    Il risultato è qualcosa del genere:

    inserisci la descrizione dell'immagine qui

    Informazioni aggiuntive : Di solito uso questo tipo di gonfiaggio / sgonfiaggio (leggermente modificato per i miei scopi) per l'impostazione di limiti con raggio su poligoni che sono disegnati su una mappa (con Leaflet o Google maps). Converti coppie (lat, lng) in coordinate JSTS e tutto il resto è lo stesso. Esempio:

    inserisci la descrizione dell'immagine qui

    Ogni linea dovrebbe dividere il piano in “dentro” e “contorno”; lo puoi scoprire usando il solito metodo del prodotto interno.

    Sposta tutte le linee verso l’esterno di una certa distanza.

    Prendi in considerazione tutte le coppie di linee adiacenti (linee, non segmenti di linea), trova l’intersezione. Questi sono i nuovi vertici.

    Pulisci il nuovo vertice rimuovendo le parti che si intersecano. – abbiamo qualche caso qui

    a) Caso 1:

      0--7 4--3 | | | | | 6--5 | | | 1--------2 

    se lo spendi per uno, hai questo:

     0----a----3 | | | | | | | b | | | | | 1---------2 

    7 e 4 si sovrappongono .. se vedi questo, rimuovi questo punto e tutti i punti in mezzo.

    (b) caso 2

      0--7 4--3 | | | | | 6--5 | | | 1--------2 

    se lo spendi per due, hai questo:

     0----47----3 | || | | || | | || | | 56 | | | | | | | 1----------2 

    per risolvere questo, per ogni segmento di linea, devi verificare se si sovrappone a questi ultimi segmenti.

    (c) caso 3

      4--3 0--X9 | | | 78 | | | 6--5 | | | 1--------2 

    spesa per 1. questo è un caso più generale per il caso 1.

    (d) caso 4

    come per il caso 3, ma consumano per due.

    In realtà, se puoi gestire il caso 4. Tutti gli altri casi sono solo casi speciali con sovrapposizione di linee o vertici.

    Per fare il caso 4, mantieni una pila di vertici .. spingi quando trovi linee che si sovrappongono a quest’ultima linea, spuntala quando ottieni la seconda linea. – proprio come quello che fai con lo scafo convesso.

    Ecco una soluzione alternativa, vedi se ti piace di più.

    1. Fai una triangolazione , non devi essere delaunay – qualsiasi triangolazione farebbe.

    2. Gonfia ogni triangolo: questo dovrebbe essere banale. se si memorizza il triangolo in senso antiorario, è sufficiente spostare le linee sul lato destro e fare l’intersezione.

    3. Uniscili usando un algoritmo di ritaglio Weiler-Atherton modificato

    Nel mondo GIS si utilizza il buffering negativo per questa attività: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

    La libreria JTS dovrebbe fare questo per te. Vedere la documentazione per il funzionamento del buffer: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

    Per una panoramica generale, consultare anche la Guida per gli sviluppatori: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

    Grazie mille ad Angus Johnson per la sua libreria di clipper. Ci sono buoni esempi di codice per fare il clipping sulla homepage del clipper su http://www.angusj.com/delphi/clipper.php#code ma non ho visto un esempio per la compensazione del poligono. Quindi ho pensato che potrebbe essere utile a qualcuno se pubblico il mio codice:

      public static List GetOffsetPolygon(List originalPath, double offset) { List resultOffsetPath = new List(); List polygon = new List(); foreach (var point in originalPath) { polygon.Add(new ClipperLib.IntPoint(point.X, point.Y)); } ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset(); co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon); List> solution = new List>(); co.Execute(ref solution, offset); foreach (var offsetPath in solution) { foreach (var offsetPathPoint in offsetPath) { resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y))); } } return resultOffsetPath; } 

    Sulla base del consiglio di @ JoshO’Brian, sembra che il pacchetto rGeos nel linguaggio R implementa questo algoritmo. Vedi rGeos::gBuffer .

    Un’ulteriore opzione è usare boost :: polygon – la documentazione è in qualche modo carente, ma dovresti trovare che i metodi resize e bloat , e anche l’operatore += sovraccarico, che effettivamente implementa il buffering. Ad esempio, aumentare la dimensione di un poligono (o un insieme di poligoni) di qualche valore può essere semplice come:

     poly += 2; // buffer polygon by 2 

    Esistono un paio di librerie utilizzabili (utilizzabili anche per set di dati 3D).

    1. https://github.com/otherlab/openmesh
    2. https://github.com/alecjacobson/nested_cages
    3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

    Si possono anche trovare pubblicazioni corrispondenti per queste librerie per comprendere gli algoritmi in modo più dettagliato.

    L’ultimo ha meno dipendenze ed è autonomo e può leggere in file .obj.

    I migliori auguri, Stephan