Compute Vereinigung von zwei beliebigen Formen

Question

Ich arbeite an einer Anwendung, muss ich der Lage sein, beliebige Formen zu kombinieren zwei überlappende, wie vom Benutzer gezogen. Dies wäre eine Union-Operation an den zwei Formen sein. Die sich ergebende Form würde die Silhouette der beiden überlappenden Formen sein.

sind die Formen als Folge von Punkten im Uhrzeigersinn gespeichert.

Idealer Ich möchte ein Algorithmus, der zwei Anordnungen von Punkten stattfinden wird (x, y) und gibt eine einzelne Anordnung der resultierenden Form.

Ich habe Wikipedia gelesen, auf Boolesche Operationen auf Polygonen denen erwähnt die Sweep Linie Algorithmus aber ich kann nicht die Verbindung zwischen diesen machen und mein Ziel, leider bin ich kein Mathematiker.

Ich entwickle die Anwendung in Actionscript 3, aber ich bin mit C #, Java, und ich kann mich durch C und C ++ wählen.

Answer 1

Die Implementierung Boolesche Operationen ist nicht korrekt trivial; zum Glück gibt es Bibliotheken, die bereits diese Funktionalität implementieren.

Was Sprache verwenden Sie? Wenn es C ++ ist, werfen Sie einen Blick auf CGAL , die Computational Geometry Algorithms-Bibliothek.

Answer 2

Bei zwei Listen von Punkten (A und B)
  - [1] für jede Zeile in A tut es schneiden, um eine Linie in B
    -.- [2], wenn keine (mehr) Linien schneiden, gibt es keine Überlappung
    -.- [3] Wenn eine Zeile in (A) schneidet, dann in eine Linie B
     -.-.- [4] Der Schnittpunkt in Ausgangs
     -.-.- [5] hat die nächste Zeile von A intersect B
       -.-.-.- [6], wenn nicht, fügen Sie diese Ausgabe (es ist innen B) goto 5
       -.-.-.- [7] Wenn ja, fügen Sie den intersect zur Ausgabe und Schaltlisten A & B goto 2

Siehe auch Schnittpunkt zweier Linien . Ich werde nicht den Code schreiben leider:)

Answer 3

Siehe auch GPC .

Answer 4

dieser Algorithmus Arbeit für Sie?

Answer 5

Wie wäre:

1. Wählen Sie die am weitesten links gelegenen Punkt der beiden Formen. Rufen Sie diese Form A und machen es die aktuelle Form.
2. Wind im Uhrzeigersinn entlang der aktuellen Form auf den nächsten Punkt und prüfen Sie, ob eine oder mehr Linien schneiden.
   • Wenn irgendwelche Linien schneiden sich, finden Sie den ersten Schnittpunkt und fügen hinzu, dass zu Ihrer neuen Form. Wechseln Sie in den entlang der anderen Form gewickelt wird.
   • Wenn keine Linien kreuzen bewegen Sie sich auf den nächsten Punkt in Form A und fügen hinzu, dass als der Punkt in der neuen Form. Weiter entlang der aktuellen Form gewickelt wird.
3. Wiederholen Sie Schritt 2.

ich denke, wenn Sie über kurvige halten je nachdem, welche Form aktuell ist, für Kreuzungen suchen, sollte das tun, was Sie wollen. Ich denke, dass mit konkaven Formen und ...

fertig werden soll

Ich bin sicher, es gibt eine Menge von Optimierungen können Sie hinzufügen, sobald Sie die Grundlagen haben zu arbeiten.

Answer 6

Es scheint auch ein JavaScript-API zu sein:

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

, die die JTS-Standard zu implementieren scheint und hat mehrere Differnt Implementierungen:

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

alle von ihnen sollten in der Lage sein Vereinigung auszuführen etc:

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

Aber csg.js ist das beeindruckendste Projekt IMO

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