JavaScript-Modul für boolesche Funktionen des Polygons (Vereinigung, Schnittpunkt, Differenz und XOR)

Question

Ich habe Polygon-Set. In diesem Satz sind einige äußere Polygone und einige können Löcher sein (oder auch nicht). Ich weiß in diesem Stadium nicht, welche Polygonlöcher sind. Ich möchte das endgültige Polygon berechnen, das alle Polygone einschließlich der Löcher kombiniert.

Ich dachte, diesen Ansatz:

//'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; 
} 

meine Anforderung Also für Modul ist

1. nur vier Polygon Booleschen Funktionen
2. wenn npm Modul ist sein gutes
3. geringeres Gewicht als Polygon kombiniert wäre eine von vielen Funktionen. Ich meine, als Anwendungsgröße ist schon mehr, also auf der Suche nach leichter Bibliothek.
4. Effizienz: in meinem Fall Anzahl der Polygone in Satz kann nicht hoch sein, aber Punkte in Polygon sind in großer Zahl so für O suchen (k.log (n)) nicht O (kn)

Liste der die Bibliotheken, die ich stieß auf und einige Punkte, wie ich verstanden:

• JSCLipper effizient, kein npm Modul ist die github project synchron mit soureforge JSClipper?
• kld-intersections Polygon-Schnittpunkt vorhanden, aber Union nicht vorhanden (oder ich bin nicht in der Lage zu finden), hat viele andere Funktionen (andere als polygon boolean). Dies ist Javscript-Port von this project
• polygon.js abhängig von jQuery, Effizienz? kein npm Modul, nicht mit polygon.js
• boolean in paper.js seine Add-on von paper.js lib verwechseln, nicht ein eigenständiges Modul
• raphael-boolean seine Add-on von raphael lib, kein eigenständiges Modul
• tess2.js GLU Tesselator portiert zu Javascript, enthält viele Funktionen zur Tesselation - ist Tesselation für Boolesche Polygonfunktionen erforderlich? Ich konnte die Booleschen Funktionen nicht gefunden, keine Dokumentation, gibt es einige Fehler auf Test HTML-Seite, keinen npm Modul
• turf-donuts abhängig von einer anderen großen Bibliothek JSTS
• JSTS Topology Suite große Bibliothek nicht modular

In einigen Fällen Diese Funktionen sind Teil großer Bibliotheken, die mit anderen Funktionen überladen sind, oder Bibliotheken arbeiten mit SVG oder einer Geo-räumlichen Umgebung, oder viele fügen der vorhandenen Bibliothek hinzu.

Bitte schlagen Sie für meine Anforderung vor, welche Bibliothek geeignet ist? Gibt es weitere modulare javscript-Bibliotheken für boolesche Polygonfunktionen?

Answer 1

Ich hatte mit der Implementierung Vatti polygon clipping algorithm begonnen, hier ist the code repository. Aber ich fand Greiner Hormann Polygon-Clipping-Algorithmus ist viel besser. Also führe ich jetzt keine the code.

Ich empfehle Greiner Hormann implementation in JavaScript für Polygon-Clipping oder andere boolesche Operationen.

Answer 2

ich meine eigenen Methoden verwenden, die auf SVG konvexen Polygonen arbeiten:

1. Set konvexen Polygonen Counter-Clockwise Punkte

2. Polygonen - Fix für Convex/CCW

3. Punkt innerhalb Convex Polygon: Jordan Curve Theorem

4. Linie schneiden Polygon - Vektor-Analyse

5. schneidende Polygone - Vektoren Analyse

6. Verbund Intersecting Polygon - Jordan Kurvensatz

7. konvexen Polygonen - Trim, Uses Sutherland-Hodgman Algorithmus clipping

Diese here gezeigt sind.

Auch möchten Sie vielleicht this auschecken.