Crie pontos a uma distância especificada um do outro nas células aleatórias da rede de pesca enquanto estiver em cadeias de linhas

Temos um protocolo terrestre onde recebemos uma rede de pesca de células de 1x1 km. Algumas células são escolhidas aleatoriamente. Precisamos colocar 4 pontos em cada célula e esses pontos também precisam estar em uma estrada. A distância mínima entre os pontos deve ser de 500m para todos os pontos de todas as células, SE POSSÍVEL, ou, se não for, queremos a maior distância possível.

Em uma primeira tentativa, dividimos cada célula em quatro células de 500x500 m com ST_CreateFishnet e, em seguida, colocamos pontos no centróide das subcélulas e depois na estrada mais próxima (ST_ClosestPoint). Temos bons resultados, mas no exemplo abaixo, você pode ver que o ponto 5 está muito próximo do 6 e pode ser movido na estrada esquerda.

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

Se você quiser tentar, coloquei as 3 camadas (rede de pesca com células aleatórias, sub-rede e estradas) em um arquivo que você pode encontrar aqui .

Acho que não podemos evitar um algoritmo recursivo que tente muitas possibilidades, mas não tenho certeza.

Você está disposto a fazer isso em R ou python, vinculando ao seu banco de dados PostGIS? Se você usou ST_DumpPoints em todas as linhas em cada célula de 1 x 1 km, poderá usar um dos muitos algoritmos disponíveis para selecionar 4 pontos com a distância entre cada> 500m ou o mais distante possível.

Talvez um dos algoritmos mencionados na Wikipedia para o problema da mochila, https://en.wikipedia.org/wiki/Knapsack_problem , dê algumas idéias. Ou, acho que um algoritmo MCMC funcionaria bem.

Se duas grades se encostam, a distância entre os pontos nas grades adjacentes é importante?