Рисуете линию между точками на определенном расстоянии в PostGIS?

У меня есть данные точек на улицах, я хотел бы превратить эти точки в простые цветные линии. Любые указатели, как эта проблема может быть названа или какие-либо алгоритмы, которые могут помочь мне решить эту проблему?

Я надеялся использовать PostGISфункции для этого, но я открыт для предложений, это данные из .shpфайла.

Edit1: обновил изображение, чтобы продемонстрировать идеальное решение этой проблемы.

Рисование линии будет основано исключительно на расстоянии между этими точками, и я ничего не смогу использовать для их группировки. В идеале это были бы точки на максимально указанном расстоянии вдоль проектируемой линии? И под проекционной линией я имею в виду найти 1-ю точку, затем следующую, ближайшую к ней, затем спроецировать линию и проверить, есть ли какие-либо точки на этой линии на максимальном расстоянии от любой из тех, которые уже находятся на линии.

​

Вы можете использовать рекурсивный запрос для исследования ближайшего соседа каждой точки, начиная с каждого обнаруженного конца линий, которые вы хотите построить.

Предварительные условия : подготовьте слой postgis с вашими точками, а другой - с одним объектом с несколькими линиями, содержащим ваши дороги. Два слоя должны быть на одном CRS. Вот код для созданного тестового набора данных, пожалуйста, измените его при необходимости. (Проверено на postgres 9.2 и postgis 2.1)

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

Вот шаги :

1. Создайте для каждой точки список всех соседей и их расстояния, которые соответствуют трем критериям.

   • Расстояние не должно превышать определенный пользователем порог (это позволит избежать привязки к изолированной точке)

     graph_full as (
     SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
     FROM points a
     LEFT JOIN points b ON a.id<>b.id
     WHERE st_distance(a.geom,b.geom) <= 15
     ),
     

   • Прямой путь не должен переходить дорогу

     graph as (
     SELECt graph_full.*
     FROM graph_full RIGHT JOIN
     roads ON st_intersects(graph_full.geom,roads.geom) = false
     ),
     

   • Расстояние не должно превышать определяемое пользователем отношение расстояния от ближайшего соседа (это должно лучше соответствовать нерегулярной оцифровке, чем фиксированное расстояние) Эта часть была на самом деле слишком трудна для реализации, привязана к фиксированному радиусу поиска

   Давайте назовем эту таблицу "граф"

2. Выберите точку конца линии, присоединившись к графику и сохранив только ту точку, которая имеет ровно одну запись на графике.

   eol as (
   SELECT points.* FROM
   points  JOIN
   (SELECT id, count(*) FROM graph 
   GROUP BY id
   HAVING count(*)= 1) sel
   ON points.id = sel.id),
   

   Давайте назовем эту таблицу "eol" (конец строки)
   легко? что награда за создание отличного графика, но на следующем шаге сумасшедшие вещи сойдут с ума

3. Настройте рекурсивный запрос, который будет циклически переходить от соседей к соседям, начиная с каждого eol

   • Инициализируйте рекурсивный запрос, используя таблицу eol и добавив счетчик для глубины, агрегатор для пути и геометрический конструктор для построения линий.
   • Переходите к следующей итерации, переключаясь на ближайшего соседа с помощью графика и проверяя, что вы никогда не вернетесь назад, используя путь
   • После завершения итерации сохраните только самый длинный путь для каждой начальной точки (если ваш набор данных включает потенциальное пересечение между ожидаемыми линиями, для этой части потребуется больше условий)

   recurse_eol (id, link_id, depth, path, start_id, geom) AS (--initialisation
   SELECT id, link_id, depth, path, start_id, geom FROM (
       SELECT eol.id, graph.link_id,1 as depth,
       ARRAY[eol.id, graph.link_id] as path,
       eol.id as start_id,
       graph.geom as geom,
       (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
       FROM eol JOIn graph ON eol.id = graph.id 
       ) foo
   WHERE test = true
   
   UNION ALL ---here start the recursive part
   
   SELECT id, link_id, depth, path, start_id, geom  FROM (
       SELECT graph.id, graph.link_id, r.depth+1 as depth,
       path || graph.link_id as path,
       r.start_id,
       ST_union(r.geom,graph.geom) as geom,
       (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
       FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
   WHERE test = true AND depth < 1000), --this last line is a safe guard to stop recurring after 1000 run adapt it as needed
   

   Давайте назовем эту таблицу "recurse_eol"

4. Оставьте только самую длинную линию для каждой начальной точки и удалите каждый точный повторяющийся путь. Пример: пути 1,2,3,5 И 5,3,2,1 - это одна и та же линия, обнаруженная с помощью двух разных «концов линии»

   result as (SELECT start_id, path, depth, geom FROM
   (SELECT *,
   row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
   (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
   FROM recurse_eol) foo
   WHERE  test_depth = true AND test_duplicate = true)
   
   SELECT * FROM result

5. Вручную проверяет оставшиеся ошибки (изолированные точки, перекрывающиеся линии, странные улицы)

Обновленный, как и было обещано, я до сих пор не могу понять, почему иногда рекурсивный запрос не дает точно такой же результат при запуске с противоположного eol той же строки, поэтому некоторый дубликат может остаться в результирующем слое на данный момент.

Не стесняйтесь спрашивать, я полностью понимаю, что этот код нуждается в большем количестве комментариев. Вот полный запрос:

WITH RECURSIVE
points as (SELECT id, st_transform((st_dump(wkb_geometry)).geom,2154) as geom, my_comment as com FROM mypoints),
roads as (SELECT st_transform(ST_union(wkb_geometry),2154) as geom from highway),

graph_full as (
    SELECT a.id, b.id as link_id, a.com, st_makeline(a.geom,b.geom) as geom, st_distance(a.geom,b.geom) as distance
    FROM points a
    LEFT JOIN points b ON a.id<>b.id
    WHERE st_distance(a.geom,b.geom) <= 15
    ),

graph as (
    SELECt graph_full.*
    FROM graph_full RIGHT JOIN
    roads ON st_intersects(graph_full.geom,roads.geom) = false
    ),

eol as (
    SELECT points.* FROM
    points  JOIN
        (SELECT id, count(*) FROM graph 
        GROUP BY id
        HAVING count(*)= 1) sel
    ON points.id = sel.id),


recurse_eol (id, link_id, depth, path, start_id, geom) AS (
    SELECT id, link_id, depth, path, start_id, geom FROM (
        SELECT eol.id, graph.link_id,1 as depth,
        ARRAY[eol.id, graph.link_id] as path,
        eol.id as start_id,
        graph.geom as geom,
        (row_number() OVER (PARTITION BY eol.id ORDER BY distance asc))=1 as test
        FROM eol JOIn graph ON eol.id = graph.id 
        ) foo
    WHERE test = true

UNION ALL
    SELECT id, link_id, depth, path, start_id, geom  FROM (
        SELECT graph.id, graph.link_id, r.depth+1 as depth,
        path || graph.link_id as path,
        r.start_id,
        ST_union(r.geom,graph.geom) as geom,
        (row_number() OVER (PARTITION BY r.id ORDER BY distance asc))=1 as test
        FROM recurse_eol r JOIN graph ON r.link_id = graph.id AND NOT graph.link_id = ANY(path)) foo
    WHERE test = true AND depth < 1000),

result as (SELECT start_id, path, depth, geom FROM
    (SELECT *,
    row_number() OVER (PARTITION BY array(SELECT * FROM unnest(path) ORDER BY 1))=1 as test_duplicate,
    (max(depth) OVER (PARTITION BY start_id))=depth as test_depth
    FROM recurse_eol) foo
WHERE  test_depth = true AND test_duplicate = true)

SELECT * FROM result

Как указывает @FelixIP, первый шаг - найти точки, которые будут составлять каждую линию. Вы можете сделать это, вызвав ST_ClusterWithin с вашим максимальным разделительным расстоянием:

SELECT
  row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom 
FROM (
  SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
  FROM inputs) sq

Затем вам нужно будет использовать некоторую эвристику, чтобы построить линию через все точки в каждом кластере. Например, если вы можете предположить, что нужные линии являются Y-монотонными, вы можете отсортировать точки в каждом кластере и передать их в ST_MakeLine . Объединяя все это, выглядело бы так:

SELECT 
  ST_MakeLine(geom ORDER BY ST_Y(geom)) AS geom
FROM (
  SELECT row_number() OVER () AS cid, 
  (ST_Dump(geom)).geom FROM (
    SELECT unnest(st_clusterwithin(geom, 0.05)) AS geom 
    FROM inputs) sq) ssq 
GROUP BY cid