modulo javascript per funzioni booleane poligono (unione, intersezione, differenza e XOR)

Question

Ho impostato poligono. In questo set alcuni sono poligoni esterni e alcuni possono (o non possono) essere fori. In questo momento non so quali siano i buchi poligonali. Voglio calcolare il poligono finale che combina tutti i poligoni compresi i fori.

ho pensato di questo approccio:

//'SomeLib' that has polygon boolean fucntions 
var polygonSet = [poly1,poly2,...polyn]; 

var union, intersection; 
var combinedPoly = SomeLib.XOR(polygonSet[0], polygonSet[1]); 
for(var i=2; i<polygonSet.length ; i++) { 
    combinedPoly = SomeLib.XOR(combinedPoly, polygonSet[i]); 
    //or if XOR is not available 
    union = SomeLib.union(combinedPoly, polygonSet[i]); 
    intersection = SomeLib.intersection(combinedPoly, polygonSet[i]); 
    combinedPoly = union - intersection; 
} 

Quindi la mia richiesta per il modulo è

1. solo quattro poligoni funzioni booleane
2. se il modulo NPM è disponibile la sua buona
3. peso leggero come il poligono combinato sarebbe una delle tante funzioni. Voglio dire come le dimensioni dell'applicazione è già di più, quindi in cerca di libreria leggera.
4. efficienza: nel mio caso il numero di poligoni in set non può essere elevato, ma i punti in poligoni sono in gran numero in modo cerca di O (k.log (n)) non O (kn)

Lista le librerie che ho trovato e alcuni punti, come ho capito:

• JSCLipper efficiente, nessun modulo NPM, è il github project in sincronia con soureforge JSClipper?
• kld-intersections presente intersezione di poligono ma unione non presente (o che non sono in grado di trovare), ha molte altre funzioni (oltre al poligono booleano). Questa è la porta javscript di this project
• polygon.js dipendente da jQuery, efficienza? , Nessun modulo NPM, non lo confondere con polygon.js
• boolean in paper.js suo add-on di paper.js lib, non un modulo indipendente
• raphael-boolean suo add-on di Raffaello lib, non un modulo indipendente
• tess2.js GLU tesselator porting in Javascript, contiene molte funzioni per la tesselation - la tassellazione è necessaria per le funzioni booleane del poligono? Non ho potuto trovato le funzioni booleane, alcuna documentazione, c'è qualche errore nella pagina di test html, nessun modulo NPM
• turf-donuts dipendente da un altro grande biblioteca JSTS
• JSTS Topology Suite grande libreria non modulare

In alcuni casi queste funzioni fanno parte di grandi librerie che sono sovraccariche di altre funzioni o le librerie funzionano con SVG o ambiente geo-spaziale o molte sono aggiunte alla libreria esistente.

Si prega di suggerire per il mio requisito quale libreria è appropriata? Esistono altre librerie modulari di javscript per le funzioni booleane poligono?

Answer 1

Avevo iniziato a implementare Vatti polygon clipping algorithm, qui è the code repository. Ma ho trovato l'algoritmo di ritaglio poligono Greiner Hormann molto meglio. Quindi non sto mantenendo the code ora.

Suggerisco Greiner Hormann implementation in JavaScript per il clipping poligonale o altre operazioni booleane.

Answer 2

Io uso i miei metodi che operano su SVG poligoni convessi:

1. insieme convesso poligoni in senso antiorario Punti

2. Poligoni - Fix per convesso/CCW

3. punto interno convesso Polygon: Jordan Curve Theorem

4. Line Intersect Polygon - vector analysis

5. Intersecting Poligoni - analisi vettori

6. Composite intersecanti Poligono - Teorema della curva di Jordan

7. Convex Poligoni - Trim, Usi Sutherland-Hodgman algoritmo

Questi sono mostrati here clipping.

Inoltre, è possibile controllare this.