Berechne die Vereinigung zweier beliebiger Formen

8

Ich arbeite an einer Anwendung, ich muss in der Lage sein, zwei überlappende beliebige Formen wie vom Benutzer gezeichnet zu kombinieren. Dies wäre eine Unionsoperation an den beiden Formen. Die resultierende Form wäre die Silhouette der zwei überlappenden Formen.

Die Formen werden als eine Reihe von Punkten im Uhrzeigersinn gespeichert.

Idealerweise möchte ich einen Algorithmus, der zwei Arrays von Punkten (x, y) benötigt und ein einzelnes Array der resultierenden Form zurückgibt.

Ich habe Wikipedia auf Booleschen Operationen für Polygone gelesen, in denen die Sweepline Algorithmus , aber ich kann die Verbindung zwischen diesem und meinem Ziel nicht herstellen, leider bin ich kein Mathematiker.

Ich entwickle die Anwendung in ActionScript 3, aber ich bin mit C #, Java und C und C ++ vertraut.

    
Greg B 26.01.2010, 14:43
quelle

6 Antworten

5

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

Welche Sprache benutzen Sie? Wenn es C ++ ist, werfen Sie einen Blick auf CGAL , die Bibliothek für Algorithmische Geometriealgorithmen.

    
Martin B 26.01.2010, 14:48
quelle
3

Gegeben zwei Listen von Punkten (A und B)
  - [1] für jede Linie in A schneidet sie eine Linie in B
    -.- [2] Wenn sich keine (mehr) Linien schneiden, gibt es keine Überlappung |     -.- [3] Wenn eine Linie in (A) eine Linie in B schneidet, dann
     -.-.- [4] füge den Schnittpunkt zur Ausgabe hinzu      -.-.- [5] schneidet die nächste Zeile von A B
       -.-.-.- [6] Wenn nicht, füge dies zur Ausgabe hinzu (es ist in B) gehe zu 5
       -.-.-.- [7] falls ja, füge die Schnittmenge zum Ausgang hinzu und vertausche die Listen A & amp; B gehe zu 2

Siehe auch Kreuzungspunkt von zwei Linien . Ich werde den Code nicht schreiben, sorry:)

    
Dead account 26.01.2010 15:07
quelle
3

Siehe auch GPC .

    
lhf 27.01.2010 10:54
quelle
2

Würde dieser Algorithmus für Sie funktionieren?

    
Jon Cage 26.01.2010 15:10
quelle
1

Wie wäre es mit:

  1. Wählen Sie den am weitesten links liegenden Punkt der beiden Formen. Nennen Sie diese Form A und machen Sie sie zur aktuellen Form.
  2. Wickeln Sie im Uhrzeigersinn entlang der aktuellen Form zum nächsten Punkt und prüfen Sie, ob sich eine oder mehrere Linien schneiden.
    • Wenn sich irgendwelche Linien schneiden, suchen Sie den ersten Schnittpunkt und fügen Sie diesen zu Ihrer neuen Form hinzu. Wechseln Sie zu der anderen Form.
    • Wenn sich keine Linien kreuzen, bewegen Sie sich auf den nächsten Punkt in Form A und fügen diesen als Punkt in Ihrer neuen Form hinzu. Wickeln Sie weiter entlang der aktuellen Form.
  3. Wiederholen Sie Schritt 2.

Ich denke, wenn du dich immer weiter winden solltest, egal welche Form aktuell ist, suche nach Kreuzungen, das sollte tun, was du willst. Ich denke, dass sollte auch mit konkaven Formen zurechtkommen ...

Ich bin sicher, dass es viele Optimierungen gibt, die Sie hinzufügen können, sobald Sie mit den Grundlagen arbeiten.

    
Jon Cage 26.01.2010 17:22
quelle
1

Es scheint auch eine Javascript-API zu geben:

Ссылка

scheint den jts-Standard zu implementieren und hat mehrere verschiedene Implementierungen:

Ссылка

alle von ihnen sollten in der Lage sein, Union usw. durchzuführen:

Ссылка

Aber csg.js ist das beeindruckendste Projekt IMO

Ссылка

    
Karussell 05.02.2012 22:59
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Windows-Benutzernamen in asp.net mvc-Anfrage erfassen