Come intersecare due poligoni?

Question

Questo sembra non banale (viene chiesto molto sui vari forum), ma ho assolutamente bisogno di questo come un elemento fondamentale per un algoritmo più complesso.

Ingresso: 2 poligoni (A e B) in 2D, indicati come un elenco di spigoli [(x0, y0, x1, y2), ...] ciascuno. I punti sono rappresentati da coppie di double s. Non so se sono dati in senso orario, antiorario o in qualsiasi direzione. I do sanno che non sono necessariamente convessi.

Uscita: 3 poligoni che rappresentano A, B e il poligono intersecante AB. Uno dei due può essere un poligono vuoto (?), Ad es. null.

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

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

EDIT: Quindi sembra che io non sia interamente pollo per svenimento alla prospettiva di farlo. Vorrei ribadire l'uscita desiderata qui, in quanto questo è un caso speciale e potrebbe rendere semplice calcolo:

uscita: primo poligono meno tutti i bit intersecano, poligoni intersezione (plurale è ok). Non mi interessa davvero il secondo poligono, solo la sua intersezione con il primo.

EDIT2: Attualmente sto usando la libreria GPC (General Polygon Clipper) che lo rende veramente facile!

Answer 1

quello che penso si dovrebbe fare

Non tentare di farlo da soli, se si può forse farne a meno. Invece, utilizzare uno dei molti algoritmi di intersezione di poligono disponibili già esistenti.

Stavo considerando seriamente il seguente codebase sulla forza del loro codice dimostrativo e sul fatto che hanno menzionato la loro gestione della maggior parte/tutti i casi strani. Dovresti donare un importo (di tua scelta/della tua azienda) se lo usi commercialmente, ma ne vale la pena per ottenere una versione robusta di questo tipo di codice.

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

Quello che ho fatto è stato in realtà di utilizzare un algoritmo poligono di intersezione che fa parte delle librerie Java2D. È possibile trovare qualcosa di simile nelle librerie C# di MS da utilizzare.

Ci sono anche altre opzioni; cercare "poligono clipper" o "poligono di ritaglio", poiché gli stessi algoritmi di base che gestiscono l'intersezione del poligono tendono anche a essere utilizzabili per i casi di clipping generali.

Una volta che si dispone di una libreria di ritaglio poligonale, è sufficiente 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 a rotolare il proprio, per il irrimediabilmente masochista

Quando mi stava prendendo in considerazione rotazione mia, ho trovato l'algoritmo di Weiler-Atherton ad avere le maggiori potenzialità di generale poligono-taglio. Ho usato il seguente come riferimento:

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

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

I dettagli, come si dice, sono troppo densi per includere qui, ma non ho dubbi che sarete in grado di trovare i riferimenti su Weiler-Atherton per gli anni a venire. Essenzialmente, dividi tutti i punti in quelli che stanno entrando nel poligono finale o uscendo dal poligono finale, quindi formi un grafico da tutti i punti, e poi percorri il grafico nelle direzioni appropriate per estrarre tutti i pezzi di poligono che volere. Cambiando il modo in cui definite e trattate i poligoni "in entrata" e "in uscita", potete ottenere diverse intersezioni di poligoni (AND, OR, XOR, ecc.).

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

Answer 2

La libreria di Arash Partow FastGEO contiene implementazioni di molti algoritmi interessanti nella geometria computazionale. L'intersezione del poligono è uno di questi. È scritto in Pascal, ma implementa solo la matematica, quindi è abbastanza leggibile. Si noti che sarà necessario pre-elaborare i bordi un po ', per farli in senso orario o antiorario.

ETA: Ma davvero, il modo migliore per farlo è non farlo. Trova un altro modo per affrontare il problema che non coinvolge le intersezioni poligonali arbitrarie.

Answer 3

Si potrebbe anche voler dare un'occhiata allo NetTopologySuite o anche provare a importarlo nel server SQL 2008 & è strumenti spaziali.

Answer 4

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)

Answer 5

Un poligono è descritto da una ordinata lista di punti (P1, P2, ..., Pn). I bordi sono (P1 - P2), (P2 - P3), ..., (Pn - P1). Se si hanno due poligoni A e B che si sovrappongono, ci sarà un punto An (dall'elenco sui punti che descrivono il poligono A) che si trova all'interno dell'area circondata dal poligono B o viceversa (un punto di B si trova in A). Se non viene rilevato alcun punto, i poligoni non si sovrappongono. Se un tale punto viene trovato (cioè Ai) controlla i punti adiacenti del poligono A (i-1) e A (i + 1). Ripeti finché non trovi un punto al di fuori dell'area o tutti i punti sono controllati (quindi il primo poligono giace completamente all'interno del secondo poligono). Se hai trovato un punto all'esterno, puoi calcolare il punto di attraversamento. Trova il bordo corrispondente del poligono B e seguilo con i ruoli resersed = ora verifica se i punti del poligono B si trovano all'interno del poligono A. In questo modo puoi creare un elenco di punti che descrivono il poligono sovrapposto. Se necessario, è necessario verificare se i poligoni sono identici (P1, P2, P3) === (P2, P3, P1).

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

narozed

Answer 6

tenta di utilizzare strumenti GIS per questo, come ArcObjects, TopologySuite, GEOS, OGR, etc.Non sono sicuro che tutte queste distribuzioni siano disponibili su .net, ma tutte fanno lo stesso.

Answer 7

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 CLR Types

La classe SqlGeometry fornisce STIntersection metodo

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

Answer 8

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

Nel mio test, Clipper è molto più veloce e molto meno soggetto a errori rispetto a GPC (vedere i confronti più dettagliati qui - http://www.angusj.com/delphi/clipper.php#features). Inoltre, mentre il codice sorgente è disponibile sia per Delphi che per C++, la libreria Clipper include anche una DLL compilata per semplificare l'uso delle funzioni di ritaglio anche in altre lingue (Windows).

Answer 9

Questo academic paper spiega come eseguire questa operazione.