Konstruieren Sie Polygone Aus der Vereinigung Vieler Polygone

Soll, dass ich viele Polygone, was ist der beste Algorithmus zum konstruieren eines Polygons--vielleicht mit Löchern - aus der union-all jene Polygone?

Für meine Zwecke, man kann sich vorstellen, jedes Stück ein polygon, wie ein puzzle-Stück, wenn Sie Sie erhalten Sie ein schönes Bild. Aber der Haken ist, dass ein kleiner Teil ( sagen <5%) des Puzzles fehlt, und Sie sind immer noch benötigen, um ein Bild so vollständig wie möglich; das ist das polygon ( oder Polygone) - vielleicht mit Löcher-- das will ich-form.

Meine naive Ansatz ist, zwei Polygone, union Ihnen, und nehmen Sie ein anderes polygon, union es mit der Vereinigung der beiden Polygone, und wiederholen Sie diesen Vorgang, bis jedes einzelne Stück wird union. Dann werde ich führen Sie durch die union-polygon-Liste und überprüfen, ob es noch einige Polygone, die kombiniert werden können, und ich werde diesen Vorgang wiederholen, bis ein zufriedenstellendes Ergebnis erreicht wird.

Aber dies scheint wie eine extrem naive Ansatz. Ich Frage mich nur, gibt es andere besseren Algorithmus?

InformationsquelleAutor Graviton | 2010-12-24
  1. 1

    Das ist brute force, was Ihr tut. Eine bessere Weise des Tuns brute-force ist branch-and-bound. Aber noch Skalen schrecklich.

    Den nächsten Schritt zu versuchen, metaheuristic algorithmen (tabu search, simulated annealing, ...) oder einfach nur die Wiederverwendung eines Frameworks wie Drools Planner (open source, java) implementiert diese für Sie.

    • irgendwelche Hinweise, wie die metaheuristic Algorithmus kann helfen? Ich sehe das wiki, aber es hat nur wenig Bezug auf das problem, das ich oben beschrieben.
    • Metaheuristiken gesteuert über "beweglichen Sachen", also in deinem Fall "verschieben Polygone; oder-hinzufügen oder entfernen eines polygon". Werfen Sie einen Blick auf tabu search, das ist ziemlich einfach zu implementieren.
    • Wenn Sie nur suchen, in der Berechnung der Vereinigung der Polygone und nicht irgendeine alternative Lösung, um die zugrunde liegende problem, dann ist das der richtige Ansatz wäre, nur union alle Polygone auf einmal und nicht in Paaren. Zum Beispiel ein sweep-line-Algorithmus für die Berechnung der union angepasst werden kann, um der union das ganze set, anstatt ein paar. Die clipper Antwort, die unten erwähnt werden klingt gut.
    • Der OP fragte auch die Frage auf Mathe, und ich denke, die Antworten sind besser (viel konkreter). math.stackexchange.com/questions/15815/...
    InformationsquelleAutor Geoffrey De Smet
  2. 7

    Benötigen Sie ein polygon clipping library - und ich werde meine plug-eigenen Clipper Bibliothek, denn es ist geschrieben in C# (und C++ und Delphi) es ist open source, freeware, und es werde genau das tun, was Sie wollen.

    Meine naive Ansatz ist, zwei Polygone, union Ihnen, und nehmen Sie ein anderes polygon, union es mit der Vereinigung der beiden Polygone, und wiederholen Sie diesen Vorgang, bis jedes einzelne Stück wird union

    Dass wäre eine sehr ineffiziente Vorgehensweise. Ein viel besserer Weg wäre, um 'union' Sie alle in einem Betrieb ...

    using ClipperLib;
using Polygon = List<IntPoint>;
using Polygons = List<List<IntPoint>>;
...

//precondition: all your polygons have the same orientation 
//(ie either clockwise or counter clockwise)
Polygons polys = new Polygons(PolyCnt);
for (int i = 0; i < PolyCnt; i++)
    polys.Add(loadPolyFromFile(String.Format("poly{0}.txt", i +1)));

Polygons solution = new Polygons();
Clipper c = new Clipper();
c.AddPolygons(polys, PolyType.ptSubject);
c.Execute(ClipType.ctUnion, solution, 
    PolyFillType.pftNonZero, PolyFillType.pftNonZero);

//code to display solution here.
    • Ihre precondition Kommentar nur ein problem habe ich Schwierigkeiten mit den ganzen morgen. Ich war mit einem union-Ergebnis in form von Unterschied und ich konnte nicht herausfinden, was zum Teufel ich falsch machte. Es stellt sich heraus, dass ich geschrieben hatte, in einer gegen den Uhrzeigersinn polygon mit einer Reihe von im Uhrzeigersinn Polygone. Ich bin sicher, dies ist in der Dokumentation irgendwo, aber ich vermisste es. Ihre Dokumente sind so ziemlich gut im Allgemeinen, also gute Arbeit. Ich war sehr zufrieden mit dem portierten gehen.clipper-Bibliothek so weit.
    InformationsquelleAutor Angus Johnson
Schreibe einen Kommentar