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

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
JOIN r1
)
-- 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.

• Can you share the code that you have used so far? Mar 6, 2018 at 3:35
• Are there any other constraints? It would make it easier, for example, to start with a point in the furthest corner of sub-cell, making it less likely you'll have to discard other points for being too close? Mar 10, 2018 at 14:16
• Yes it is good to start with points in corners when there are no other cells touching the cell on the considered corner. Points have to be at a minimum distance from each other on the whole grid. Mar 12, 2018 at 9:04