Créez des points à une distance spécifiée les uns des autres dans des cellules de résille aléatoires tout en étant sur des chaînes de lignes

Nous avons un protocole terrestre où nous recevons une résille de cellules de 1x1 km. Certaines cellules sont choisies au hasard. Nous devons mettre 4 points dans chaque cellule et ces points doivent également être sur une route. La distance minimale entre les points doit être de 500 m pour chaque point de chaque cellule SI POSSIBLE ou si ce n'est pas le cas, nous voulons la distance maximale possible.

Dans un premier essai, nous avons divisé chaque cellule en quatre cellules de 500x500 m avec ST_CreateFishnet puis nous avons mis des points au centre de gravité des sous-cellules puis sur la route la plus proche (ST_ClosestPoint). Nous obtenons de bons résultats mais dans l'exemple ci-dessous, vous pouvez voir que le point 5 est trop proche de 6 et pourrait être déplacé sur la route de gauche.

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 vous voulez l'essayer, je mets les 3 couches (résille avec des cellules aléatoires, sous-réseau et routes) dans une archive que vous pouvez trouver ici .

Je suppose que nous ne pouvons pas éviter un algorithme récursif qui essaie de nombreuses possibilités mais je ne suis pas sûr.

Êtes-vous prêt à le faire en R ou en python en vous connectant à votre base de données PostGIS? Si vous avez utilisé ST_DumpPoints sur toutes les lignes de chaque cellule de 1x1 km, vous devriez pouvoir utiliser l'un des nombreux algorithmes disponibles pour sélectionner 4 points avec la distance entre chacun> 500 m, ou aussi éloignés que possible.

Peut-être que l'un des algorithmes mentionnés sur Wikipedia pour le problème du sac à dos, https://en.wikipedia.org/wiki/Knapsack_problem , vous donnera quelques idées. Ou, je pense qu'un algorithme MCMC fonctionnerait bien.

Si deux grilles se touchent, la distance entre les points des grilles adjacentes est-elle importante?