Raumfüllung zwischen zufälligen 2D-Linien

23

Betrachten Sie einen Bereich (2D), der zufällig mit Linien gefüllt ist (folgende Abbildung). Wir sind daran interessiert, die Leerstellen zwischen den Zeilen einschließlich der vier Begrenzungskanten auf eine Art und Weise zu füllen:

0- Maximierung der Paketgröße;
Die Form der Füllpakete ist quadratisch, horizontal oder vertikal ausgerichtet.
2- Form der Füllpakete ist quadratisch, dh entspannte Ausrichtung ;
3- Form der Füllpakete ist ein beliebiges Viereck. unsere ursprüngliche Frage

Im Moment gibt es also drei verschiedene Szenarien.
Beachten Sie, dass die Linien die Form eines [x1,y1,x2,y2]Punktes haben, dh reelle Zahlen.

[* * *] Ideen für mögliche Lösungen / Algorithmen / Code-Schnipsel / etc sind mehr als willkommen.

Bildbeschreibung hier eingeben


Update 1: Wir könnten eine Lösung für den ersten Fall verwalten:
Bildbeschreibung hier eingeben
Schritte sind:
1 - Zeilen
2 - Rastern von Zeilen in eine Bitmap
3 - Suchen in der Nähe befindlicher Zellen für jede Zelle der gewünschten Farbe (dh der gleichen Farbe) mit einer Zielfunktion zum Maximieren die Fläche, dh die Anzahl der Zellen.

Es funktioniert gut, deckt jedoch nur das erste Szenario ab und ist auch langsam.


Update 2:
Wir gingen davon aus, dass der Leser mit dem Konzept der raumfüllenden Kacheln vertraut ist. Sie können dem Link folgen, um sich inspirieren zu lassen. Beachten Sie jedoch, dass unser Problem anders ist. Da wir den leeren Raum nicht zufällig füllen und die Größe nicht zufällig wählen. Die Lösung sollte iterativ sein. In allen Fällen gibt es keine Begrenzung für die Anzahl der einzusetzenden Pakete. Es ist in der Tat Sache des Benutzers, die Iterationszahl zu begrenzen, indem er beispielsweise einen Mindestbereich für Pakete auswählt. Dies ist in dem oben angegebenen Beispiel offensichtlich, in dem wir Zeilen in Pixel mit der angegebenen Größe diskretisiert haben. Das heißt, die Prozedur sollte so lange ausgeführt werden, bis der gesamte leere Bereich unter Berücksichtigung des Kriteriums, z. B. der maximalen Fläche der Pakete, gefüllt ist.


Update 3:
Zusammenfassung:
Eine Anwendung besteht darin, die Verteilung von extrahierbaren, intakten "Gesteinsblöcken" in einer stark zerbrochenen "Mine" herauszufinden. Dies kann unter vielen Aspekten, einschließlich der Bohrplanung, der finanziellen Bewertung usw., sehr hilfreich sein.
Beschreibung:
Bei einer Mine aus dekorativem Gestein (Stein) ist der Preis stark von der Größe der Steine ​​abhängig Block. Die Extraktion eines Blocks aus einem geeigneten Bereich, dh ohne größeren Bruch, ist erwünscht, wenn die Menge der verbleibenden Teile so gering wie möglich ist. In der Regel haben die kleinen Gesteinsstücke keinen relativen wirtschaftlichen Wert und werden daher als Abfall betrachtet.
Die Frage in diesem Beitrag untersucht Lösungen für diese Art von Problem.

Eine mathematische Ansicht für das Problem kann wie folgt angegeben werden:
2D: Finden Sie alle Rechtecke, die aus einem bestimmten 2D-Bereich extrahiert werden könnten, wobei einige Linien für eine möglichst große Rechteckgröße optimiert sind.
3D: Finden Sie alle rechteckigen Würfel, die aus einem bestimmten 3D-Bereich mit einigen Unterebenen (besser: Polygone) extrahiert werden können, die für eine möglichst große Blockgröße optimiert sind.


Da dies Teil einer laufenden Forschung ist, haben einige der in den Kommentaren unten gestellten Fragen keine bestimmten Antworten, die wir bereitstellen können. Wir sind der Meinung, dass die hier bisher zur Verfügung gestellten Informationen tatsächlich ausreichen, um ein Gesamtbild des Problems zu erhalten. Trotzdem stellen wir einige Details zur Verfügung, die wir für die Allgemeinheit nutzen können.
Sie können die Lösung für die letzte Frage einschränken, obwohl wir glauben, dass es immer möglich ist, später mehr hinzuzufügen. Beispielsweise folgendermaßen: {} 2D - Fall
die beste Größe eines Blockes (wirtschaftlich optimales Rechteck) unter den Bedingungen extrahiert wird oben erwähnt, wird 1x1 mangegeben 10x10 mfür die Region in dem Beispiel. Dies ist eine Einschränkung, die basierend auf dem wirtschaftlichen Wert definiert wird. Die minimal bearbeitbare Größe zum Schneiden etc, sei0.15x0.15 m; also dies ist die zweite größenbeschränkung.
Bildbeschreibung hier eingeben
Die obige Abbildung zeigt die ökonomische Wertfunktion in Abhängigkeit von der Blockgröße. Für diesen speziellen Fall ist also jedes Steinstück, das kleiner ist als 0.15x0.15 mnur Abfall. Es gibt keine Blockgröße, die größer ist als 1.7x1.7 maufgrund von Betriebsgrenzen.

Entwickler
quelle
3
@RK - Ich bin anderer Meinung. Er / sie hat bereits sehr deutlich erklärt, wonach sie suchen. Sicher gibt es mehrere mögliche Lösungen, aber nichts kann sie davon abhalten, nützlich zu sein und dafür zu stimmen.
GIS-Jonathan
1
Da dies eine algorithmische Frage ist, die sehr mathematisch ist, sollten Sie versuchen, - math.stackexchange.com
GIS-Jonathan
1
Eng verbunden: gis.stackexchange.com/questions/27303 . Die vorliegende Frage hat, wie @RK feststellt, keine eindeutige Antwort, da sie nicht ausreichend gut gestellt ist. Wie viele Rechtecke sind erlaubt? Was bedeutet es, die Größe zu maximieren? Beachten Sie auch, dass dies kein "zufälliges Kacheln" -Problem ist: Die Linien bestimmen lediglich über ihr Komplement die Bereiche, die belegt werden können; Die Lösungen werden definitiv nicht zufällig sein. Beachten Sie auch, dass eine einfache Vereinfachung sofort verfügbar ist: Das Problem kann innerhalb jeder Komponente der Ergänzung separat gelöst werden.
whuber
1
@whuber: Nun, eine Anwendung, die uns interessiert, ist es, die Verteilung von extrahierbaren intakten "Gesteinsblöcken" in einer stark zerbrochenen "Mine" herauszufinden. Nun, GIS scheint für dieses Problem vielversprechend zu sein, denken wir. Dies haben wir auch der Frage hinzugefügt. Wir vermuten, dass die GIS-Community von der Idee für ihre verwandten anderen speziellen Probleme profitieren kann. Wie auch immer, es liegt an Ihnen, ob Sie es migrieren;)
Entwickler
4
Wie @whuber andeutet, handelt es sich nicht wirklich um eine GIS-Frage (obwohl ich nicht beleidigt bin, dass sie hier gestellt wird.) In einem Forum für Computergeometrie oder -optimierung haben Sie viel mehr Glück, eine Antwort zu erhalten.
Llaves

Antworten:

2

Ich habe eine Idee, wie Sie iterativ mit FME von großen Blöcken zu kleineren Blöcken arbeiten (von Safe Software). Ich arbeite nicht für sie, aber ich scheine ihr Werkzeug genug zu loben ...

  1. Verwenden Sie "BoundingBoxReplacer" für den gewünschten Bereich.
  2. Projizieren Sie es erneut in ein lokales Koordinatensystem (für später, wenn Sie in Fuß / Metern "kacheln" müssen).
  3. Puffern Sie die Leitungen mit dem Transformator "Bufferer". Sie benötigen nur eine beliebige Größe, z. B. 0,01 Fuß / Meter. Was wir hier suchen, ist ein Polygon der Linie für den nächsten Schritt.
  4. Fügen Sie einen "Fliesenleger" -Transformator hinzu. Geben Sie eine große (geschätzte oder sonstige) Kachelgröße in Fuß oder Metern an. Was wir hier tun, ist das Aufteilen des interessierenden Bereichs in quadratische Blöcke. Je nach Datensatz fangen Sie groß an, um die großen Ausreißer wirklich zu bekommen.
  5. Fügen Sie einen "Clipper" -Transformator hinzu. Was wir hier tun, ist im Wesentlichen das Aufteilen des Datensatzes, um zu sehen, welche Kacheln gut / schlecht sind. Auf der Ausgabe sind Kacheln, die "Inside" sind, zu groß. Fliesen, die "draussen" sind, sind jedoch groß genug und bereit zum Schneiden ...
  6. Hier wird es kompliziert, aber nicht schwierig ... Wir werden den Transformator so schleifen, dass wir die ursprüngliche BoundingBox wiederverwenden, aber Bereiche ausschneiden, die bereits zum Schneiden bereit sind. Fügen Sie also einen Clipper hinzu und routen Sie den Clipper als "Ausgabe" -Kacheln auf der früheren Clipper-Ausgabe. Jetzt haben wir ein einziges Polygon, das wieder einsatzbereit ist.
  7. Verwenden Sie den Fliesenleger erneut, und geben Sie diesmal eine kleinere Fliese an. Wenn Sie beispielsweise früher 100-Meter-Kacheln verwendet haben, versuchen Sie es mit 90-Meter-Kacheln.
  8. Fügen Sie einen weiteren Clipper hinzu, wobei der Eingabe-Clipper die gepufferten Zeilen und der Eingabe-Clippee die kleineren Kacheln als Eingabe sind.

Spülen Sie und wiederholen Sie so oft wie nötig mit jeweils kleineren Fliesen. Ich habe den Start einer Workbench angehängt, die ich als einen Ansatz verwenden würde.

Basierend auf Ihrer (sehr detaillierten) Beschreibung funktioniert dies vorerst nur mit Ihrer Option 1. Ohne gerade noch zu viel Zeit aufzuwenden.

Jedenfalls ist dies nur ein Ansatz, mit dem ich anfangen würde, um zumindest die Spreu vom Weizen zu filtern.

FME Tile Beispiel

Matthew Brucker
quelle