Come intersecare due poligoni?

Question

Questo non sembra banale (viene chiesto spesso su vari forum), ma ne ho assolutamente bisogno come elemento costitutivo per un algoritmo più complesso.

Ingresso:2 poligoni (A e B) in 2D, forniti come elenco di bordi [(x0, y0, x1, y2), ...] ogni.I punti sono rappresentati da coppie di doubleS.Non so se siano dati in senso orario, antiorario o in qualsiasi direzione.IO Fare sappi che non sono necessariamente convessi.

Produzione:3 poligoni che rappresentano A, B e il poligono intersecante AB.Ciascuno dei quali può essere un poligono vuoto (?), ad es. null.

Suggerimento per l'ottimizzazione:Questi poligoni rappresentano i confini della stanza e del piano.Quindi il confine della stanza normalmente si intersecherà completamente con il confine del pavimento, a meno che non appartenga ad un altro piano sullo stesso piano (argh!).

Spero che qualcuno lo abbia già fatto in C# e mi permetta di usare la sua strategia/codice, poiché ciò che ho trovato finora su questo problema è piuttosto scoraggiante.

MODIFICARE:Quindi sembra che non sia del tutto ingenuo a sentirmi svenire alla prospettiva di fare una cosa del genere.Vorrei riaffermare qui l'output desiderato, poiché questo è un caso speciale e potrebbe rendere il calcolo più semplice:

Produzione:Primo poligono meno tutti i pezzi che si intersecano, poligoni di intersezione (il plurale va bene).Non mi interessa veramente il secondo poligono, solo la sua intersezione con il primo.

EDIT2:Attualmente sto utilizzando il GPC (Clipper poligonale generale) libreria che lo rende davvero semplice!

Answer 1

Quello che penso dovresti fare

Non tentare di farlo da solo se puoi evitarlo.Utilizzare invece uno dei tanti algoritmi di intersezione di poligoni già esistenti.

Stavo seriamente considerando la seguente base di codice in base alla forza del loro codice dimostrativo e al fatto che menzionavano la loro gestione della maggior parte/tutti i casi strani.Dovresti donare un importo (a scelta tua o della tua azienda) se lo usi a scopo commerciale, ma ne vale la pena per ottenere una versione robusta di questo tipo di codice.

http://www.cs.man.ac.uk/~toby/gpc/

Ciò che in realtà ho fatto è stato utilizzare un algoritmo di intersezione di poligoni che fa parte delle librerie Java2D.Puoi eventualmente trovare qualcosa di simile da utilizzare nelle librerie C# di MS.

Ci sono anche altre opzioni là fuori;cerca "clipper poligono" o "ritaglio poligono", poiché gli stessi algoritmi di base che gestiscono l'intersezione dei poligoni tendono ad essere utilizzabili anche per i casi di ritaglio generale.

Una volta che hai effettivamente una libreria di ritaglio di poligoni, devi solo sottrarre il poligono B dal poligono A per ottenere il primo pezzo di output e intersecare i poligoni A e B per ottenere il secondo pezzo di output.

Come arrotolarsi da soli, per i masochisti senza speranza

Quando stavo pensando di crearne uno mio, ho scoperto che l'algoritmo di Weiler-Atherton aveva il maggior potenziale per il taglio generale dei poligoni.Ho usato quanto segue come riferimento:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

I dettagli, come si suol dire, sono troppo densi per essere inclusi qui, ma non ho dubbi che sarai in grado di trovare riferimenti su Weiler-Atherton negli anni a venire.In sostanza, dividi tutti i punti in quelli che entrano nel poligono finale o escono dal poligono finale, quindi formi un grafico con tutti i punti e poi percorri il grafico nelle direzioni appropriate per estrarre tutti i pezzi del poligono che hai Volere.Modificando il modo in cui definisci e tratti i poligoni di "entrata" e di "uscita", puoi ottenere diverse possibili intersezioni di poligoni (AND, OR, XOR, ecc.).

In realtà è abbastanza implementabile, ma come con qualsiasi codice di geometria computazionale, il diavolo è nelle degenerazioni.

Answer 2

FastGEO biblioteca di Arash Partow contiene implementazioni di molti algoritmi interessanti in geometria computazionale. Poligono intersezione è uno di loro. E 'scritto in Pascal, ma è solo la matematica attuare quindi è abbastanza leggibile. Si noti che è certamente dovrete pre-elaborare i vostri bordi un po ', per farli in senso orario o antiorario ordine.

ETA: Ma in realtà, il modo migliore per farlo è quello di non fare questo . Trova un altro modo di affrontare il problema che non coinvolge le intersezioni di poligoni arbitrari.

Answer 3

Se si sta programmando in .NET Framework, si consiglia di dare un'occhiata a classe SqlGeometry disponibile in assembly .NET spediti come Microsoft SQL Server System tipi CLR

La classe SqlGeometry fornisce STIntersection metodo

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);

Answer 4

Si consiglia inoltre di avere uno sguardo alla NetTopologySuite o anche provare importarlo al server SQL 2008 e si tratta di strumenti spaziali.

Answer 5

Un poligono è descritto da un elenco ordinato di punti (P1, P2, ..., Pn). I bordi sono (P1 - P2), (P2 - P3), ..., (Pn - P1). Se si hanno due poligoni A e B che si sovrappone, ci sarà un punto An (dall'elenco punti che descrivono poligono A) che si trova all'interno della zona circondata da poligono B o viceversa (un punto di B si trova in A). Se non viene trovato alcun punto tale, allora i poligoni non si sovrappongono. Se viene trovato un tale punto (cioè Ai) controllare i punti adiacenti del poligono A (i-1) e A (i + 1). Ripetere fino a trovare un punto al di fuori della zona o tutti i punti sono stati estratti (quindi il primo poligono bugie completamente entro il secondo poligono). Se hai trovato un punto al di fuori allora si può calcolare il punto di attraversamento. Trova il bordo corrispondente di poligono B e seguire con ruoli resersed = ora controllare se i punti di poligono B trovano all'interno poligono A. In questo modo è possibile costruire un elenco di punti che descrivono il poligono sovrapposizione. Se necessario si dovrebbe verificare se i poligoni sono identici, (P1, P2, P3) === (P2, P3, P1).

Questa è solo un'idea e modi là forse migliori. Se si trova un lavoro e di soluzione testata mi sento di raccomandare che lo si utilizza ...

narozed

Answer 6

Prova ad utilizzare strumenti GIS per questo, come ArcObjects, TopologySuite, GEOS, OGR, ecc non sono sicuro se tutte queste distribuzioni sono availuable NET, ma fanno tutti lo stesso.

Answer 7

Clipper è un open source freeware di poligono libreria (scritto in Delphi e C ++) clipping che fa esattamente quello che stai chiedendo - http://sourceforge.net/projects/polyclipping/

Nel mio test, Clipper si sia significativamente più veloce e molto meno soggetto a errori di GPC (si veda il confronto più dettagliate qui - http://www.angusj.com/delphi/clipper.php#features ). Inoltre, mentre c'è il codice sorgente sia per Delphi e C ++, la biblioteca Clipper comprende anche una DLL compilata per rendere molto facile da utilizzare le funzioni di ritaglio in altre lingue (Windows) anche.

Answer 8

documento accademico spiega come fare questo.

Answer 9

Se avete il coraggio di dare un'occhiata al codice di altre persone GPL C ++, si può vedere come lo fanno in Inkscape:

http: / /bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (linea 126)