Twórz punkty w określonej odległości od siebie w losowych komórkach kabaretki podczas przebywania na liniach

10

Mamy protokół lądowy, w którym otrzymujemy kabaretkę z komórkami 1x1 km. Niektóre komórki są wybierane losowo. Musimy umieścić 4 punkty w każdej komórce i te punkty też muszą być na drodze. Minimalna odległość między punktami musi wynosić 500 m dla każdego punktu każdej komórki JEŚLI MOŻLIWE, a jeśli nie, chcemy maksymalnej możliwej odległości.

W pierwszej próbie podzieliliśmy każdą komórkę na cztery komórki 500 x 500 m za pomocą ST_CreateFishnet, a następnie umieściliśmy punkty na środku subkomórek, a następnie na najbliższej drodze (ST_ClosestPoint). Mamy dobre wyniki, ale w poniższym przykładzie widać, że punkt 5 jest zbyt blisko od 6 i można go przenieść na lewą drogę.

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

Jeśli chcesz spróbować, umieściłem 3 warstwy (kabaretki z losowymi komórkami, sub-fisnet i drogi) w archiwum, które możesz znaleźć tutaj .

Chyba nie możemy uniknąć algorytmu rekurencyjnego, który próbuje wielu możliwości, ale nie jestem pewien.

wprowadź opis zdjęcia tutaj

postgis geoprocessing qgis-processing algorithm vector-grid Nicolas Boisteault
źródło
Czy możesz udostępnić kod, którego użyłeś do tej pory?
Cushen
Czy są jakieś inne ograniczenia? Ułatwiłoby to na przykład rozpoczęcie od punktu w najdalszym rogu podkomórki, co zmniejszyłoby prawdopodobieństwo odrzucenia innych punktów, ponieważ znajdują się zbyt blisko?
Simbamangu,
Tak, dobrze jest zacząć od punktów w rogach, gdy żadna inna komórka nie dotyka komórki w rozważanym rogu. Punkty muszą znajdować się w minimalnej odległości od siebie na całej siatce.
Nicolas Boisteault,

Odpowiedzi:

1

Czy chcesz to zrobić w języku R lub python, łącząc się z bazą danych PostGIS? Jeśli użyłeś ST_DumpPoints na wszystkich liniach w każdej komórce 1 x 1 km, powinieneś być w stanie użyć jednego z wielu dostępnych algorytmów, aby wybrać 4 punkty z odległością między każdym z nich> 500 m lub jak najdalej od siebie.

Być może jeden z algorytmów wymienionych w Wikipedii dla problemu plecaka, https://en.wikipedia.org/wiki/Knapsack_problem , da ci kilka pomysłów. Lub myślę, że algorytm MCMC działałby dobrze.

Jeśli dwie siatki przylegają do siebie, czy odległość między punktami w sąsiednich siatkach ma znaczenie?

jgm_GIS
źródło
Aby odpowiedzieć na twoje ostatnie pytanie. Tak, jak powiedziałem w moim ostatnim komentarzu: „Punkty muszą znajdować się w minimalnej odległości od siebie na całej siatce”. Dziękuję za pomoc
Nicolas Boisteault