Calcola unione di due forme arbitrarie

Question

Sto lavorando su un'applicazione, ho bisogno di essere in grado di combinare due forme arbitrarie sovrapposte come disegnata dall'utente. Questo sarebbe un'operazione dell'Unione sui due forme. La forma risultante sarebbe la sagoma delle due forme sovrapposte.

Le forme sono memorizzati come una sequenza di punti in senso orario.

Idealmente vorrei un algoritmo che avrà due schiere di punti (x, y) e restituire una singola matrice della forma risultante.

Ho letto su Wikipedia operazioni booleane sui poligoni che menziona il algoritmo di linea Sweep ma non riesco a fare il collegamento tra questo e il mio obiettivo, ahimè io non sono un matematico.

sto sviluppando l'applicazione in ActionScript 3, ma ho familiarità con C #, Java e posso scegliere la mia strada attraverso C e C ++.

Answer 1

L'implementazione operazioni booleane correttamente non è banale; per fortuna, ci sono librerie che già implementano questa funzionalità.

Che lingua stai usando? Se si tratta di C ++, dare un'occhiata a CGAL , l'Algoritmi Biblioteca Geometria Computazionale.

Answer 2

Date due liste di punti (A e B)
  - [1] per ogni linea in A non si interseca una linea in B
    -.- [2] se non (più) linee si intersecano, non c'è sovrapposizione
    -.- [3], se una linea in (A) interseca una linea in B allora
     -.-.- [4] aggiungere il punto di intersezione in uscita
     -.-.- [5] non la prossima linea da A interseca B
       -.-.-.- [6] in caso contrario, aggiungere questo per l'output (è all'interno B) goto 5
       -.-.-.- [7] in caso affermativo, aggiungere l'Intersect per l'output e l'interruttore elenchi A e B goto 2

Si veda anche punto di intersezione di due linee . Non ho intenzione di scrivere il codice dispiace:)

Answer 3

Si veda anche GPC .

Answer 4

questo algoritmo lavoro per voi?

Answer 5

Come su:

1. Selezionare il punto più a sinistra delle due forme. Chiamata che forma A e renderla la forma attuale.
2. del vento in senso orario lungo la forma corrente al punto successivo e controllare per vedere se una o più linee si intersecano.
   • Se tutte le linee si intersecano, trovare il primo punto di intersezione e aggiungere che alla vostra nuova forma. Passare alla avvolgimento lungo l'altra forma.
   • Se non ci sono linee si intersecano passare a quella successiva punto in forma A e aggiungere che il punto in cui la nuova forma. Continuare snoda lungo la forma attuale.
3. Ripetere il passaggio 2.

Credo che se si continua a snoda lungo a seconda di quale forma è attuale, alla ricerca di incroci, che dovrebbe fare quello che vuoi. Penso che dovrebbe far fronte con forme concave e ...

Sono sicuro che ci sono un sacco di ottimizzazioni è possibile aggiungere una volta che hai le basi di lavoro.

Answer 6

Sembra che ci sia anche un'API JavaScript:

https://github.com/bjornharrtell/jsts/

che sembra attuare le JTS di serie e ha diverse implementazioni differnt:

http://tsusiatsoftware.net/jts/jts-links.html#ports

tutti dovrebbero essere in grado di eseguire l'unione etc:

http://tsusiatsoftware.net/jts/JTSUser/contents.html

Ma csg.js è il progetto più imponente IMO

https://github.com/evanw/csg.js