Tenemos un protocolo de tierra donde recibimos una red de celdas de 1x1 km. Algunas celdas se eligen al azar. Necesitamos poner 4 puntos en cada celda y estos puntos también deben estar en una carretera. La distancia mínima entre puntos debe ser de 500 m para cada punto de cada celda SI ES POSIBLE o si no es así, queremos la máxima distancia posible.
En un primer intento, dividimos cada celda en cuatro celdas de 500x500 m con ST_CreateFishnet, luego colocamos puntos en el centroide de las subceldas y luego en la carretera más cercana (ST_ClosestPoint). Obtenemos algunos buenos resultados, pero en el siguiente ejemplo puede ver que el punto 5 está demasiado cerca de 6 y podría moverse en el camino de la izquierda.
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
Si quieres probarlo, pongo las 3 capas (red con celdas aleatorias, subredes y carreteras) en un archivo que puedes encontrar aquí .
Supongo que no podemos evitar un algoritmo recursivo que pruebe muchas posibilidades, pero no estoy seguro.
fuente
Respuestas:
¿Está dispuesto a hacer esto en R o python vinculando a su base de datos PostGIS? Si usó ST_DumpPoints en todas las líneas en cada celda de 1x1 km, debería poder usar uno de los muchos algoritmos disponibles para seleccionar 4 puntos con la distancia entre cada> 500m, o lo más lejos posible.
Quizás uno de los algoritmos mencionados en Wikipedia para el problema de la mochila, https://en.wikipedia.org/wiki/Knapsack_problem , le dará algunas ideas. O, creo que un algoritmo MCMC funcionaría bien.
Si dos cuadrículas se topan, ¿importa la distancia entre los puntos en las cuadrículas adyacentes?
fuente