Wir haben ein Landprotokoll, in dem wir ein Fischnetz von 1x1 km Zellen erhalten. Einige Zellen werden zufällig ausgewählt. Wir müssen 4 Punkte in jede Zelle setzen und diese Punkte müssen sich auch auf einer Straße befinden. Der Mindestabstand zwischen Punkten muss 500 m für jeden Punkt jeder Zelle betragen , WENN MÖGLICH, oder wenn dies nicht der Fall ist, möchten wir den maximal möglichen Abstand.
In einem ersten Versuch haben wir jede Zelle mit ST_CreateFishnet in vier 500 x 500 m große Zellen aufgeteilt und dann Punkte auf den Schwerpunkt der Unterzellen und dann auf die nächste Straße (ST_ClosestPoint) gesetzt. Wir erhalten einige gute Ergebnisse, aber im folgenden Beispiel sehen Sie, dass Punkt 5 von 6 zu nahe ist und auf der linken Straße verschoben werden könnte.
WITH
r1 AS ( -- only sub-cells which intersects random cells
SELECT id_maille, ROW_NUMBER() OVER() AS id_grille, fishnet_500.geomgrille
FROM fishnet_500
JOIN t_mailles
ON ST_Intersects(ST_Buffer(t_mailles.geom,-200), fishnet_500.geomgrille) -- buffer < 0 to not select neightbours
)
,
r2 AS ( -- cut roads in every cells
SELECT id_maille, id_grille, ST_Intersection((ST_Dump(roads.geom)).geom, r1.geomgrille) as geomroute
FROM roads
JOIN r1
ON ST_Intersects(roads.geom, r1.geomgrille)
)
-- select point on each road the closest to cell centroid
SELECT r2.id_maille, r2.id_grille, ST_ClosestPoint(ST_Union(r2.geomroute),ST_Centroid(r1.geomgrille)) as geomipa
FROM r2
JOIN r1
ON r2.id_grille = r1.id_grille
GROUP BY r2.id_maille, r2.id_grille, r1.geomgrille
ORDER BY r2.id_maille, r2.id_grille
Wenn Sie es versuchen möchten, habe ich die 3 Ebenen (Fischnetz mit zufälligen Zellen, Sub-Fisnet und Straßen) in ein Archiv gestellt, das Sie hier finden .
Ich denke, wir können einen rekursiven Algorithmus nicht vermeiden, der viele Möglichkeiten ausprobiert, aber ich bin mir nicht sicher.
quelle
Antworten:
Sind Sie bereit, dies in R oder Python zu tun, indem Sie eine Verknüpfung zu Ihrer PostGIS-Datenbank herstellen? Wenn Sie ST_DumpPoints auf allen Linien in jeder 1x1 km-Zelle verwendet haben, sollten Sie in der Lage sein, einen von vielen verfügbaren Algorithmen zu verwenden, um 4 Punkte mit einem Abstand zwischen jeweils> 500 m oder so weit wie möglich voneinander entfernt auszuwählen.
Vielleicht gibt Ihnen einer der auf Wikipedia erwähnten Algorithmen für das Rucksackproblem, https://en.wikipedia.org/wiki/Knapsack_problem , einige Ideen. Oder ich denke, ein MCMC-Algorithmus würde gut funktionieren.
Wenn zwei Gitter aneinander stoßen, spielt dann der Abstand zwischen den Punkten in den benachbarten Gittern eine Rolle?
quelle