Create points at specified distance from each other in random fishnet's cells while being on linestrings

Question

We have a land protocol where we receive a fishnet of 1x1 km cells. Some cells are randomly choosed. We need to put 4 points in each cell and these points have to be on a road too. The minimum distance between points have to be 500m for every points of every cells IF POSSIBLE or if it is not, we want the maximum possible distance.

In a first try we divided every cell in four 500x500 m cells with ST_CreateFishnet then we put points at the centroid of the sub-cells then on the closest road (ST_ClosestPoint). We get some good results but in the example below you can see than point 5 is too close from 6 and could be moved on the left road.

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

If you want to give it a try I put the 3 layers (fishnet with random cells, sub-fisnet and roads) in an archive that you can find here.

I guess we can't avoid a recursive algorithm that tries many possibilities but i'm not sure.

Answer 1

Are you willing to do this in R or python by linking to your PostGIS database? If you used ST_DumpPoints on all the lines in each 1x1 km cell, you should be able to use one of many available algorithms to select 4 points with the distance between each > 500m, or as far apart as possible.

Perhaps one of the algorithms mentioned on Wikipedia for the knapsack problem, https://en.wikipedia.org/wiki/Knapsack_problem, will give you some ideas. Or, I think an MCMC algorithm would work well.

If two grids abut each other, does the distance between points in the adjacent grids matter?