Generieren Sie gleich große Bereiche im Polygon

8

Ich suche nach einer Pseudocode-Logik, die ngleich große Bereiche in einem bestimmten Polygon findet. Zwischen oder außerhalb der übereinstimmenden Bereiche darf kein Platz sein. Die erste gültige Übereinstimmung der Bereiche sollte zurückgegeben werden.

Angenommen, folgendes Polygon [2,2, 3,1, 5,1, 5,4, 4,5, 2,3]als Eingabe:

Geben Sie hier die Bildbeschreibung ein

... und 3als Parameter könnte eine gültige Ausgabe sein [ [2,2, 3,2, 3,3, 4,3, 4,5, 2,3], [2,2, 3,1, 5,1, 4,2, 4,3, 3,3, 3,2], [4,5, 4,2, 5,1, 5,4] ]:

Geben Sie hier die Bildbeschreibung ein

Eine weitere gültige Ausgabe mit Parameter 3ist [ [3,4, 3,3, 4,3, 4,2, 3,2, 3,1, 2,2, 2,3], [4,3, 4,2, 3,2, 3,1, 5,1, 5,3], [3,4, 3,3, 5,3, 5,4, 4,5] ]:

Geben Sie hier die Bildbeschreibung ein

Bitte beachten Sie, dass Bereiche nicht denselben Mittelpunkt haben müssen. Ein oder mehrere Bereiche können zufällig genau zwischen andere Bereiche innerhalb des Polygons fallen.

Hier ist ein weiteres Beispiel für die Eingabe / Ausgabe von Beispielen.

Angenommen, folgendes Polygon [1,3, 1,1, 7,1, 7,2, 8,2, 8,3, 5,6, 4,6]als Eingabe:

Geben Sie hier die Bildbeschreibung ein

..und 5als Parameter könnte eine gültige Ausgabe sein [ [1,3, 1,1, 3,1, 3,2, 4,3, 3,4, 3,3], [3,2, 3,1, 7,1, 7,2, 6,2, 6,3, 5,3, 5,2], [6,2, 8,2, 8,3, 6,5, 5,5, 5,4, 6,4], [1,3, 3,3, 3,4, 5,5, 6,4, 6,5, 7,5, 6,6, 5,6], [3,4, 4,3, 3,2, 5,2, 5,3, 6,3, 6,4, 5,4, 4,5] ]:

Geben Sie hier die Bildbeschreibung ein

Folgende Annahmen werden getroffen:

  • Die Richtung aller Grenzen ist durch 45 teilbar

  • Ganzzahlige Koordinaten werden für alle Polygone verwendet

  • Der ganzzahlige Bereich des Eingabepolygons ist immer durch teilbar n

  • Alle Polygone können entweder konvex oder konkav sein

  • lösbar, dh nBereiche können richtig in das angegebene Polygon passen

Sergey Lukin
quelle
1
Das Teilen Ihrer Forschung hilft allen . Sagen Sie uns, was Sie versucht haben und warum es Ihren Anforderungen nicht entsprach. Dies zeigt, dass Sie sich die Zeit genommen haben, um sich selbst zu helfen, es erspart uns, offensichtliche Antworten zu wiederholen, und vor allem hilft es Ihnen, eine spezifischere und relevantere Antwort zu erhalten. Siehe auch Fragen
Mücke
Du meinst "gleich große" Gebiete, nicht "gleich verteilt", denke ich?
Doc Brown
@ DocBrown du hast so recht, ich wusste ich werde hier etwas falsch machen. Ich meinte definitiv gleich groß. Behoben
Sergey Lukin
Sind Ihre Eingabepolygone wie in Ihrem Beispiel immer konvex?
Doc Brown
@DocBrown Jedes Format wird wirklich funktionieren. Ich habe dieses Format nur gewählt, weil ich es irgendwo gesehen habe und vermutet habe, dass es das wichtigste ist, aber ich würde gerne korrigiert werden.
Sergey Lukin

Antworten:

6

Nicht lösbar. Ich habe eine Reihe von Methoden ausprobiert, bis mir klar wurde, dass dies nicht möglich war.

Nehmen Sie eine Form mit Bereich 4 an, die in 2 Teile mit jeweils Bereich 2 unterteilt werden sollte:

Quadrate

Das am weitesten links stehende Dreieck und Quadrat muss Teil von Form 1 sein, benötigt jedoch ein anderes Dreieck. Der einzige Ort, von dem aus genommen werden könnte, ist das Quadrat rechts, aber der Rest wird in zwei Regionen aufgeteilt.

NiklasJ
quelle
2
Im Allgemeinen natürlich nicht lösbar , aber ich denke, das OP könnte an einem Algorithmus interessiert sein, der das Problem für jeden Fall löst, in dem es gelöst werden kann, und ansonsten ausgibt, dass es nicht gelöst werden kann ;-) Hat Ihnen auch eine Gegenstimme gegeben.
Doc Brown
Guter Fang. Ich habe nicht darüber nachgedacht. Wir könnten entweder die Annahme hinzufügen, dass der Bereich gültig ist, solange er aus Pfadkoordinaten besteht, die nicht von anderen Bereichen abgefangen werden. Dies würde dazu führen [ [0,1, 2,1, 2,2, 3,2, 2,3, 2,2 1,2], [2,2, 2,0, 3,0, 3,2] ] , dass entweder die Tatsache akzeptiert wird, dass eine Ausnahme ausgelöst wird, falls die Funktion über alle Varianten iteriert und nicht gefunden wird eine Übereinstimmung. Was denken Sie?
Sergey Lukin
Der Einfachheit halber habe ich die Annahme hinzugefügt, dass nur lösbare Variationen des Polygons und der Anzahl der Bereiche als Eingabe übergeben werden. Siehe meine Bearbeitung. Vielen Dank
Sergey Lukin
6

Wie ich in meinem Kommentar zur Antwort von Doc Browns (ansonsten ausgezeichnet) sagte, gibt es eine Frage der Wahl der Quadrat-> Dreiecksteilung, die es etwas schwieriger macht, einen Algorithmus zu entwickeln. Sie müssen es auch nicht seriell erstellen, sondern können es parallel ausführen, wie einige meiner Vorschläge zeigen.

Ich habe zuerst mehrere heuristische Ansätze gemacht.

Voronoi: Wählen Sie N Punkte (nicht ganzzahlige Koordinaten) in der Form und erstellen Sie eine Voronoi-Karte. Lassen Sie die Punkte sich in Bezug auf ihre Fläche anziehen und abstoßen (zu große Anziehungskräfte, zu kleine Abstoßungen).

Nützlich für große A / N, leicht in lokale Maxima zu fallen.

Kreismethode: Ziel ist es, problematische Bereiche zu entfernen und dann eine andere Methode anzuwenden.

Wählen Sie einen Punkt (nicht ganzzahlig) im Inneren und einen Radius r. Das Innere abzüglich des Kreises erzeugt k getrennte Unterregionen. Wenn eine der Unterregionen die Größe A / n hat, entfernen Sie sie. Wenn einer 2 * A / n ist, sollte es einfach sein, ihn zu teilen und auch zu entfernen. Verringern Sie den Radius leicht und fahren Sie fort (verwenden Sie möglicherweise eine binäre Suche).

Problematisches Punktwachstum: Beginnen Sie mit der von Doc Brown erwähnten Methode. Da es jedoch an den meisten Kanten zwei Möglichkeiten gibt, überspringen Sie das Diagramm und vergrößern Sie jeden Bereich am Rand so, dass möglichst wenige neue problematische Punkte erstellt werden (problematische Punkte = nur Dreiecke) eine Kante mit dem Rest der Form teilen). Fügen Sie beispielsweise bei der Auswahl neuer Nachbarn diese in der Reihenfolge ihrer Konvexität hinzu (konkav = negative Konvexität).

Bandwachstum: Für fast konvexe oder konvexe Bereiche. Wählen Sie einen Punkt an der Außenkante aus, lassen Sie ein Band mit Einheitsbreite der Außenkante folgen, bis es die richtige Länge hat, und stellen Sie sicher, dass niemals ein neuer getrennter Punkt erstellt wird. Überspringen Sie gegebenenfalls die letzten Dreiecke und lassen Sie sie leicht breiter werden. Lassen Sie das nächste Band dort folgen, wo das letzte endete, bis der letzte Bereich die richtige Größe hat.

Spielartig oder organisch: Erstelle N "Länder". Platziere sie an zufälligen Stellen. Lass sie organisch wachsen. Wenn sie sich treffen, ist derjenige mit der kleinsten aktuellen Fläche am stärksten und gewinnt das Dreieck. Wahrscheinlich anfällig für lokale Maxima?

NiklasJ
quelle
3

Die allgemeine Strategie sollte darin bestehen, das erste Stück der Fläche A / n aus Ihrem Polygon P0 zu entfernen (wobei A die Gesamtfläche ist), sodass Sie ein neues Polygon P1 der Fläche AA / n erhalten. Wiederholen Sie dies und erzeugen Sie ein Polygon P2, dann P3. Nach n Wiederholungen haben Sie Ihre Lösung. Beachten Sie, dass es bei jedem Schritt möglich ist, dass Sie kein solches neues Teil finden, bei dem die verbleibenden Teile noch ein verbundenes Polygon bilden, in dem Sie einen Schritt zurückgehen und versuchen müssen, ein anderes Teil zu finden, oder den Algorithmus ohne Ergebnis stoppen müssen .

Um ein solches Stück der Größe A / n zu konstruieren, teilen Sie zunächst Ihr Polygon in "Gitterstücke" auf. Jedes Gitterquadrat innerhalb des Polygons bildet ein solches Stück sowie jedes dreieckige Halbquadrat, bei dem der Rand des Polygons das Quadrat in zwei Hälften teilt. Sie können hierfür einen Punkt-in-Polygon-Test verwenden , alle Halbquadrate innerhalb des Begrenzungsrahmens des Polygons durchlaufen und testen, ob ihr Mittelpunkt innerhalb des angegebenen Polygons liegt (wenn beide Hälften eines Quadrats enthalten sind, können Sie den verwenden volles Quadrat stattdessen). Als Nächstes erstellen Sie ein planares Diagramm, wobei jedes der Teile einen Eckpunkt definiert (mit einer "Fläche" oder einem "Gewicht" von entweder 1 oder 1/2). Die Kanten dieses Diagramms werden durch die benachbarten Teile angegeben. Dies reduziert Ihr geometrisches Problem auf ein Diagrammproblem, bei dem Sie nach einem verbundenen Unterdiagramm mit Scheitelpunkten des Gesamtgewichts A / n suchen und das verbleibende Diagramm weiterhin verbunden ist .

Das letztere Problem könnte durch ein Backtracking gelöst werdenAnsatz. Beginnen Sie mit einem Scheitelpunkt, der aus dem Diagramm entfernt werden kann, ohne die Verbindung zu trennen. Sie können den Scheitelpunkt nach dem Zufallsprinzip auswählen oder die Liste aller Scheitelpunkte nach dem Zufallsprinzip einmal mischen, um sie in den folgenden Schritten wiederzuverwenden. Versuchen Sie nun, einen zweiten Scheitelpunkt zu finden, der mit dem ersten verbunden ist und aus dem verbleibenden Diagramm entfernt werden kann, ohne auch dessen Verbindung zu zerstören. Wenn es mehrere Möglichkeiten gibt, wählen Sie eine zufällig aus. Für Scheitelpunkte, die ein Quadrat darstellen, können Sie auch eine Diagrammoperation zulassen, bei der Sie das Quadrat auf die eine oder andere Weise in zwei Dreiecke aufteilen (dies erzeugt neue Scheitelpunkte mit dem Gewicht 1/2). Dies ist nur ein bisschen komplizierter als nur das Verschieben eines Scheitelpunkts vom ursprünglichen Diagramm zum Unterdiagramm, aber es sollte überhaupt nicht zu schwierig sein.

Wiederholen Sie diesen Vorgang, bis Ihr Untergraph ein Gesamtgewicht von A / n erreicht hat oder Sie keinen anderen Scheitelpunkt mehr finden. Wenn dies der Fall ist, "gehen" Sie eine Ebene zurück und versuchen Sie zuerst einen anderen Scheitelpunkt.

Es gibt verschiedene Möglichkeiten, dies zu optimieren. Sie müssen beispielsweise einen schnellen Konnektivitätstest für Diagramme auswählen. Ich denke, Sie werden viele Algorithmen für dieses Unterproblem finden, Google verwenden oder hier beginnen . Es kann sich lohnen, nach einem Algorithmus zu suchen, mit dem schnell überprüft werden kann, ob ein verbundener Graph noch verbunden ist, wenn ein Scheitelpunkt entfernt wird.

Hoffe das hilft.

Doc Brown
quelle
Das klingt genau das, was ich brauchte. Ich habe mir diese Strategie theoretisch vorgestellt und alles macht für mich bisher Sinn. Jetzt ist es Zeit für mich, sie in die Praxis umzusetzen. Ich melde mich zurück, wenn ich etwas zu zeigen habe. Ich danke dir sehr!
Sergey Lukin
Ich denke, es gibt ein kleines Problem mit diesem Ansatz. Für jedes Quadrat gibt es zwei mögliche Auswahlmöglichkeiten für Dreiecke. Um tatsächlich alle zu überprüfen und eine Lösung zu garantieren, falls es eine gibt, müssten Sie dies wahrscheinlich für alle 2 ^ n-Auswahlmöglichkeiten tun.
NiklasJ
@NiklasJ: Sie haben Recht, siehe meine verbesserte Antwort, die dies berücksichtigt.
Doc Brown
@SergeyLukin: Ich habe meine Antwort ein wenig geändert, um NiklasJs Kommentar zu berücksichtigen.
Doc Brown