Come intersecare più poligoni?

Question

Sto cercando un algoritmo con il seguente input e output:

Ingresso:Un insieme di poligoni su un piano.Per esempio.P1...Pn e S.(P1...Pn potrebbe essere concavo, S è convesso.)

Produzione:L'area dell'insieme di poligoni in questo piano che è uguale alla differenza di S e all'unione di P1...Pn.

Ho trovato algoritmi per intersecare o unire DUE poligoni.Ma poiché ciascuna di queste operazioni potrebbe produrre diversi poligoni, se lo facessi ingenuamente ne creerei tonnellate.

COSÌ:Come gestire l'intersezione di più poligoni?

Sarebbe ok se tutti i poligoni fossero collegati insieme poiché solo l'area è ciò che cerco.Il mio pensiero era di utilizzare poligoni orientati per simulare i buchi ma poi ho di nuovo il problema di scoprire se ho una "rappresentazione minima" in quanto n potrebbe esplodere.[Capisci di cosa sto parlando?E' abbastanza strano...)

Answer 1

Potresti mettere insieme tutti i bordi in un Algoritmo della linea di sweep. Potrebbe non essere ottimale (?) Ma almeno otterrai la rappresentazione minima che stai cercando.

Answer 2

Una soluzione è convertire ogni poligono in un mucchio di triangoli. Una volta che lo fai è abbastanza facile trovare unione/intersezione/differenza tra una serie di aree poiché è possibile svolgere le stesse funzioni banalmente su un triangolo (il risultato su due triangoli può includere fino a 6 triangoli).

Answer 3

L'approccio più semplice sarebbe scomporre i poligoni concavi in ​​poligoni convessi.Quindi intersecare due poligoni convessi è quasi banale.