Как рассчитать расстояние до ближайшего соседа для 10000 точек в таблице

Я использую PostgreSQL, и я использую расширение PostGIS.

Я могу сравнить одну точку с этим запросом:

SELECT st_distance(geom, 'SRID=4326;POINT(12.601828337172 50.5173393068512)'::geometry) as d
FROM pointst1
ORDER BY d

но я хочу сравнивать не одну фиксированную точку, а столбец точек. И я хочу сделать это с помощью какой-то индексации, чтобы это было дешево с вычислительной точки зрения, а не 10000x10000, как перекрестное соединение в этой таблице.

Создать таблицу:

create table pointst1
(
  id   integer not null
    constraint pointst1_id_pk
    primary key,
  geom geometry(Point, 4325)
);

create unique index pointst1_id_uindex
  on pointst1 (id);

create index geomidx
  on pointst1 (geom);

Изменить: уточненный запрос (сравнение 10000 точек с их ближайшим соседом, но получение результата самой точки, которая равна 0, а не следующей ближайшей точки:

select points.*,
  p1.id as p1_id,
  ST_Distance(geography(p1.geom), geography(points.geom)) as distance
from
  (select distinct on(p2.geom)*
  from pointst1 p2
  where p2.id is not null) as points
cross join lateral
  (select id, geom
  from pointst1
  order  by points.geom <-> geom
           limit 1) as p1;

postgresql postgis knn spatial spatial-query
person luftgekuhltlover    schedule 22.06.2018    source источник
comment
Вы можете добавить заявление create table?   -  person Jim Jones    schedule 22.06.2018
comment
@JimJones да, конечно! Я отредактировал свой первоначальный пост   -  person luftgekuhltlover    schedule 22.06.2018
comment
Я не уверен, что вы пытаетесь получить - некоторые примеры входных данных и соответствующие им выходные данные могут быть полезны?   -  person Tanktalus    schedule 22.06.2018
comment
Есть ли у вас причина использовать другую SRS? (4326 и 4325). Я считаю, что ваш запрос уже выполняет то, что вы хотите, просто индекс не подходит ... Я добавлю его в ответ.   -  person Jim Jones    schedule 22.06.2018
comment
@JimJones нет, он должен быть таким же, просто опечатка.   -  person luftgekuhltlover    schedule 23.06.2018
comment
@Gentsview Я тоже так думал. В своем ответе я рассматривал все геометрические формы как 4326   -  person Jim Jones    schedule 23.06.2018

Ответы (1)


arrow_upward
1
arrow_downward

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

Учитывая эти ценности ..

INSERT INTO pointst1 VALUES (1,'SRID=4326;POINT(16.19 48.21)'),
                            (2,'SRID=4326;POINT(18.96 47.50)'),
                            (3,'SRID=4326;POINT(13.47 52.52)'),
                            (4,'SRID=4326;POINT(-3.70 40.39)');

... если вы запустите свой запрос, он уже вычислит расстояние от всех точек в таблице:

SELECT ST_Distance(geom, 'SRID=4326;POINT(12.6018 50.5173)'::geometry) as d
FROM pointst1
ORDER BY d

        d         
------------------
  2.1827914536208
 4.26600662563949
 7.03781262396208
 19.1914274750473
(4 Zeilen)

Измените свой индекс на GIST, который больше всего подходит для геометрических данных:

create index geomidx on pointst1 using GIST (geom);

Просто обратите внимание, что индекс не ускорит этот ваш запрос, поскольку вы выполняете полное сканирование. Но как только вы начнете больше играть в предложении where, вы можете увидеть некоторые улучшения.

РЕДАКТИРОВАТЬ:

WITH j AS (SELECT id AS id2, geom AS geom2 FROM pointst1) 
SELECT id,j.id2,ST_Distance(geom, j.geom2) AS d
FROM pointst1,j
WHERE id <> j.id2
ORDER BY id,id2  

 id | id2 |        d         
----+-----+------------------
  1 |   2 | 2.85954541841881
  1 |   3 |  5.0965184194703
  1 |   4 | 21.3720495039666
  2 |   1 | 2.85954541841881
  2 |   3 | 7.43911957156222
  2 |   4 | 23.7492673571207
  3 |   1 |  5.0965184194703
  3 |   2 | 7.43911957156222
  3 |   4 | 21.0225069865609
  4 |   1 | 21.3720495039666
  4 |   2 | 23.7492673571207
  4 |   3 | 21.0225069865609
(12 rows)

Удаление повторяющихся расстояний:

SELECT DISTINCT ON(d) * FROM (
WITH j AS (SELECT id AS id2, geom AS geom2 FROM pointst1) 
SELECT id,j.id2,ST_Distance(geom, j.geom2) AS d
FROM pointst1,j
WHERE id <> j.id2
ORDER BY id,id2) AS j

 id | id2 |        d         
----+-----+------------------
  1 |   2 | 2.85954541841881
  3 |   1 |  5.0965184194703
  3 |   2 | 7.43911957156222
  4 |   3 | 21.0225069865609
  4 |   1 | 21.3720495039666
  2 |   4 | 23.7492673571207
(6 rows)
person Jim Jones    schedule 22.06.2018
comment
да, мой запрос вычисляет расстояние от заданной геометрии, которая является одной точкой для всех записей в таблице, но мне нужно, чтобы рассчитать расстояние между всеми точками в этой таблице. - person luftgekuhltlover; 23.06.2018
comment
вы имеете в виду, вам нужно расстояние от каждой точки в этой таблице до всех остальных записей? например а-б, а-в, а-г, а-д, ... а-я - person Jim Jones; 23.06.2018
comment
да, точно, но поскольку расстояние такое же, как a-b и b-a, мы можем пропустить b-a. - person luftgekuhltlover; 23.06.2018
comment
@Gentsview Я только что добавил к своему ответу еще один вопрос. Это то, что вы имели ввиду? Он по-прежнему повторяет перевернутые пары ... но его также можно улучшить. Просто чтобы убедиться, что это то, чего вы хотите достичь - person Jim Jones; 23.06.2018
comment
это выглядит хорошо, но мне нужно найти только 1-NN для каждой из этих 10000 точек: скажем, мы сравниваем id: 1 со всеми другими точками и выводим только наименьшее расстояние, конечным результатом снова будет 10000 строк. - person luftgekuhltlover; 23.06.2018
comment
Я придумал запрос, который мне нужен для этих 10000 точек, но теперь проблема в том, что он берет расстояние с самой точкой, которое равно 0, и мне нужна следующая ближайшая точка. Я добавлю запрос в свой первоначальный пост. - person luftgekuhltlover; 23.06.2018