Suchen Sie einen Algorithmus, um die maximale Anzahl von Punkten innerhalb des eingeschränkten Bereichs in einem minimalen Abstand zu platzieren?

17

Ich habe eine Polygonebene, die eine Einschränkung beschreibt. Ich möchte Punkte in diesem Bereich hinzufügen. Ich möchte so viele Punkte wie möglich hinzufügen, aber sie müssen einen Mindestabstand zwischen ihnen haben. Ist das mit GIS möglich?

Zur Verdeutlichung wäre es am besten, ein geordnetes Raster zu generieren, da dies die meisten Punkte garantieren würde. Die Einschränkung würde dies jedoch selten zulassen, und es kann vorzuziehen sein, Punkte zu entfernen, damit ein Versatz besser in die Einschränkung passt.

algorithm point Matthew Snape
quelle
1. ja 2. Wollen Sie zufällig oder sortiert (Gitter)?
Brad Nesom
Scheint zwei Fragen zu sein. Möchten Sie, dass ein Algorithmus dies außerhalb der Software ausführt? Oder möchten Sie wissen, welches GIS-System dies kann?
Brad Nesom
1
Sind die Punkte so eingeschränkt, dass sie> = der Mindestabstand von der Polygongrenze sein müssen? Wenn ja, könnte die Frage klarer formuliert werden als: Wie kann ich die maximale Anzahl von Kreisen in ein Polygon packen?
Kirk Kuykendall
Irgendwie verwandt: gis.stackexchange.com/q/4927/162
Julien
1
@qva Nein, gibt es nicht, denn die genauen Lösungen, die gefunden werden können, sind asymmetrisch und selbst für einfache Formen wie Rechtecke schwer zu erhalten. Die besten Berechnungsmethoden, die ich gefunden habe, basieren auf räumlichem simuliertem Tempern (und sie funktionieren sehr gut, obwohl sie viel Berechnung erfordern). Mit ihnen habe ich Lösungen für viele Polygone unterschiedlicher Formen gesucht. Es ist klar, dass die Polygongrenzen die Lösungen in der Nähe der Grenzen steuern. Tief im Inneren tendieren sie dazu, sich hexagonalen Packungen von Scheiben anzunähern.
Whuber

Antworten:

5

Ich denke, das könnte man sich als "Packproblem" vorstellen.

In diesem Fall möchten Sie vielleicht einen genetischen Algorithmus ausprobieren, der dem in Über genetische Algorithmen zum Packen von Polygonen ähnlichen ähnelt .

Kirk Kuykendall
quelle
Interessante Referenz, danke. Ein kurzer Blick deutet darauf hin, dass der Algorithmus des Papiers die Polygone als Rechtecke benötigt. Wissen Sie, ob es auf beliebige Polygone verallgemeinert werden kann?
whuber
9

Ich kenne kein GIS-Tool, um das zu tun, aber ich habe eine Idee über den Algorithmus.

Erstens kann eine Annäherung der maximalen Punktzahl mit dieser Formel erhalten werden:

Nb = 4.A / Pi.d^2

(Wo Aist die Polygonfläche und dder Mindestabstand).

Um zu versuchen, diese Punkte im Polygon zu lokalisieren, ist das beste Muster nicht das Quadratgitter, sondern das Sechseckgitter. Sehen:

Quadrat gegen sechseckiges Gitter

Schließlich könnten einige Optimierungstechniken unter Verwendung von Kraftmodellen verwendet werden, um die relative Positionierung der Punkte zu verfeinern.

NB: Es ist ein bekanntes Problem in der Kristallographie .

julien
quelle
GIS - Tool, um das zu tun ... ian-ko.com Geo-Wizard zufälliger Punkt im Polygon.
Brad Nesom
1
Vielen Dank! Aber die Frage ist nicht genau über zufällige Punkte im Polygon, oder?
Julien
In erster Linie funktioniert die hexagonale Packung einwandfrei. Es ist jedoch fast nie optimal. Ich würde erwarten, dass die potenzielle Verbesserung proportional zur Länge des Umfangs des Polygons ist. Für nicht gewundene Polygone mit vielen Punkten ist dies also kein schlechter Ansatz.
whuber
6

Siehe den Thread unter /math/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . Beachten Sie insbesondere den Verweis (in einem Kommentar) auf "Poisson disk process" und führen Sie eine Websuche durch. Der Zusammenhang mit der aktuellen Frage besteht darin, dass Sie, wenn Sie eine bestimmte Anzahl von Punkten gleichmäßig verteilen können, diese Anzahl systematisch erhöhen können, bis keine Punkte mehr in das Polygon eingefügt werden können, und damit das Problem der Maximierung der Anzahl von Punkten, die a unterliegen, gelöst ist Mindestabstand erforderlich. (Technisch gesehen handelt es sich bei den beiden Problemen um doppelte Optimierungsprobleme, bei denen die Ziele und Einschränkungen vertauscht sind.)

whuber
quelle
0

Die Lösung muss aus gleichseitigen Dreiecken bestehen, http://en.wikipedia.org/wiki/Equilateral_triangle . Die einzige Frage ist die Länge der Seiten und der "xy-Versatz" in Bezug auf Ihr Polygon.

(wie das unten erwähnte sechseckige Gitter)

Uffe Kousgaard
quelle
1
Dies gilt nur innerhalb einer unendlichen Ebene. Die Grenze eines endlichen Polygons schränkt die Konfiguration stark ein. Wenn es viele Punkte gibt, bilden sie ungefähr gleichseitige Dreiecke.
whuber