10

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.

enter image description here

  • Can you share the code that you have used so far? – Cushen Mar 6 '18 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? – Simbamangu Mar 10 '18 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. – Nicolas Boisteault Mar 12 '18 at 9:04
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?

  • To anwser your last question. Yes, as said in my last comment : "Points have to be at a minimum distance from each other on the whole grid". Thank you for your help. – Nicolas Boisteault Apr 24 '18 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.