polygon union ohne Löcher
Ich Suche für einige ziemlich einfach (ich weiß, polygon union ist NICHT eine einfache Bedienung, aber vielleicht könnte jemand mich in die richtige Richtung mit einer relativ leichten) Algorithmus auf die Zusammenführung zweier sich schneidenden Polygonen. Polygone werden könnte, konkav, ohne Löcher und auch die Ausgabe-polygon sollte nicht Löcher in Sie. Polygone dargestellt werden, in gegen-Uhrzeigersinn. Was ich meine ist, stellte auf einem Bild. Wie Sie sehen können, selbst wenn es ein Loch in der Vereinigung der Polygone, die ich brauche es nicht in der Ausgabe. Eingang Polygone sind sicher und ohne Löcher. Ich denke, ohne Löcher sollte es einfacher sein zu tun, aber noch habe ich nicht eine Idee.
- Ich gepostet, Antwort auf die gleiche Frage hier: stackoverflow.com/a/19475433/904679
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie wie folgt vorzugehen:
ersten hinzufügen, um Ihre Punkte alle Punkte der Schnittmenge Ihrer Polygone.
dann würde ich Vorgehen wie graham-scan-Algorithmus aber mit einer Einschränkung.
Statt der Auswahl den Punkt, dass die höchsten Winkel mit der vorherigen Zeile (haben Sie einen Blick auf graham-scan, um zu sehen, was ich meine (*)), die wählen, die mit th höchsten Winkel, das war Teil eins der vorhergehenden polygon.
erhalten Sie eine envellope (nicht konvex), die beschreiben, Ihre Form.
Hinweis:
es ist ähnlich wie das finden der konvexen Hülle von Punkten.
Beispielsweise graham-scan-Algorithmus helfen, finden Sie die konvexe Hülle der Menge der Punkte in O(N*ln(N)), wobei N die Anzahl der Punkte.
sich bis zum konvexe Hülle algorithmen, und finden Sie einige Ideen.
Hoffe, es hilft.
remarques:
(*)aus wikipedia:
In der konvex-hull-Algorithmus wählt man den Punkt des Winkels, der macht den größten Winkel mit der vorherigen Seite.
Zu "kleben" Sie mit Ihrem bisherigen polygon, nur hinzufügen der Einschränkung, dass Sie müssen wählen Sie eine Seite, die bereits existiert.
und Sie nehmen Sie die Einschränkung der haveing Winkel von weniger als 180°
hoffe, ich bin klar
Habe ich nicht eine vollständige Antwort, aber ich bin zu begeben Sie sich auf eine ähnliches problem. Ich denke, es gibt zwei Schritt, die relativ wichtig. Erstmal wäre ein Punkt zu finden, auf einige polygon liegt auf dem äußeren Rand. Zweite wäre eine Liste von bounding-Boxen für alle vertices und zu sehen, welche diese überschneiden. Dies bedeutet, dass beim Durchlaufen der Eckpunkte, die Sie nicht haben, um tests für alle von Ihnen, nur diejenigen, die Sie kennen, haben eine chance, sich kreuzenden (bounding-box-Probleme sind leicht).
Da haben Sie jetzt einen Punkt außerhalb, können Sie jetzt Durchlaufen, verbunden, Punkte, bis Sie erkennen eine Kreuzung. Wenn Sie wissen, welche Seite innen und welche aussen (Sie benötigen können, um einige Arbeit zu tun auf den ersten Eckpunkt zu wissen), Sie wissen, welchen Weg zu gehen, auf der Kreuzung. Dann ist es nur eine Frage der Schalt-Polygone.
Bekommt dieser ein wenig interessanter, wenn Sie wollen, zu behaupten, dass Loch (was ich tun), in dem Fall, ich würde wahrscheinlich stellen Sie sicher, dass ich verwendet hatte, alle meine kreuzenden bounding-Boxen. Sie auch nicht angeben, was passieren soll, wenn deine Polygone nicht schneiden überhaupt. Aber entweder werde Sie in Ruhe lassen (die möglicherweise ein problem, wenn Sie erwarten, dass ein polygon-out) oder wird ein Fehler zurückgegeben.