У нас есть земельный протокол, в котором мы получаем сетку размером 1х1 км. Некоторые клетки выбираются случайным образом. Нам нужно поставить 4 очка в каждую ячейку, и эти точки тоже должны быть на дороге. Минимальное расстояние между точками должно быть 500 м для каждой точки каждой ячейки, ЕСЛИ ВОЗМОЖНО, а если нет, мы хотим максимально возможное расстояние.
В первой попытке мы разделили каждую ячейку на четыре ячейки размером 500x500 м с помощью ST_CreateFishnet, затем поместили точки в центр тяжести подэлементов, а затем на ближайшую дорогу (ST_ClosestPoint). Мы получаем хорошие результаты, но в приведенном ниже примере вы видите, что точка 5 находится слишком близко от 6 и может быть перемещена по левой дороге.
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
Если вы хотите попробовать, я поместил 3 слоя (сеть со случайными ячейками, подсеть и дороги) в архив, который вы можете найти здесь .
Я думаю, мы не можем избежать рекурсивного алгоритма, который пробует много возможностей, но я не уверен.
источник
Ответы:
Готовы ли вы сделать это в R или Python, связавшись с вашей базой данных PostGIS? Если вы использовали ST_DumpPoints на всех линиях в каждой ячейке 1x1 км, вы сможете использовать один из множества доступных алгоритмов для выбора 4 точек с расстоянием между каждым> 500 м или как можно дальше друг от друга.
Возможно, один из алгоритмов, упомянутых в Википедии для решения проблемы ранца, https://en.wikipedia.org/wiki/Knapsack_problem , даст вам некоторые идеи. Или, я думаю, алгоритм MCMC будет работать хорошо.
Если две сетки примыкают друг к другу, имеет ли значение расстояние между точками в соседних сетках?
источник