Python kdtree найти "n" ближайших соседних групп (координат) - PullRequest
Новая
       43

Python kdtree найти "n" ближайших соседних групп (координат)

0 голосов
/ 27 августа 2018

Цель : По координате X найти «n» ближайшую прямую-многоугольник для координаты X, а не только «n» ближайших точек.Пример: https://i.imgur.com/qyxV2MF.png

У меня есть группа пространственных многоугольников, которые могут иметь более 2 координат.Их координаты хранятся в (scipy) KDtree, чтобы включить поиск по NN.

Сначала я запросю число ближайших координат "i", а затем отыскиваю соответствующие координаты line-polygons-> "i", не обязательнопроизводим строки "i".

Чтобы достичь "n" ближайших строк, мне нужно будет увеличить "i".Моя проблема в том, что «я» может быть непредсказуемым, потому что число координат варьируется между каждым полигоном линии.Например, линия-многоугольник может быть представлена ​​2-мя координатами, а другая может быть представлена ​​с помощью 10-ти координат.В большинстве случаев мне нужно только 2 ближайших соседних линейных полигона из точки X.

В примере изображения мне нужны линии A и B в качестве результата.Даже если «i» = 3, будет найдена только строка A, поскольку A1, A2, A3 являются ближайшими соседями к X.

Вопрос : есть ли способ группировкикоординаты фигуры вместе, а затем выполнить поиск NN, чтобы получить "n" уникальных фигур?(кроме грубой форсировки «i» для обеспечения «n» уникальных форм)

Текущий псевдокод обхода: 

found = []
while True:
    if first_loop:
        result = look up N nearest coords
    else:
        result = look up Nth nearest coord

    look up shapes using result and append to found
    perform de-duplication of found

    if len(found) >= required:
         return found
    else:
         N = N+1 # to check the Nth neighbor next iteration

Ответы [ 2 ]

0 голосов
/ 27 августа 2018

Я вижу два способа сделать это эффективно:

  1. Индексировать полные "полигоны линии": для этого вы можете связать каждый полигон линии минимальным ограничительным прямоугольником.Затем индексируйте все прямоугольники с соответствующей структурой индекса, например, R-Tree .Вместо точек у вас будут линейные полигоны на самом низком уровне, поэтому вам придется адаптировать расстояние для этого случая.
  2. Использовать Просмотр расстояния : Идея заключается в том, чтобы прикрепить ккаждая точка указывает идентификатор своего многоугольника и индексирует точки в структуре индекса (например, KD-Tree).Затем вы последовательно извлекаете следующую ближайшую точку вашего запроса, используя дистанционный просмотр.Вы продолжаете это, пока не найдете точки из n различных многоугольников.
0 голосов
/ 27 августа 2018

Если я правильно понял ваш вопрос, это проблема правильных структур данных.

Давайте иметь следующие структуры данных: 1. Словарь от многоугольников до точек 2. Другой словарьот точек к линейным полигонам (или эквивалентно одной двунаправленной карте из двунаправленного текста вместо пары словарей) 3. логический массив посещенный с размером, равным количеству точек

Теперь следующееАлгоритм должен решить вашу проблему (может быть эффективно реализован с помощью вышеуказанных структур данных):

  1. Для всех точек инициализируйте посещаемый массив как False.

  2. Найдите ближайшую точку к точке запроса сначала из дерева kd, отметьте совпадающую точку и все точки из соответствующего многоугольника, которому совпадающая точка принадлежит как посещенная, и верните этот конкретный многоугольник (id) как ближайший многоугольник(если таких многоугольников несколько, верните их все).

  3. Повторшаг 2, пока не будут возвращены n таких (разных) полигонов.Рассмотрим новую точку, возвращаемую из kd-дерева, как совпадающую с точкой запроса, если она еще не посещена (если сопоставленная точка, возвращенная kd-деревом, уже посещена, отбросьте ее и запросите следующую ближайшую сопоставленную точку).Когда точка посещена, отметьте точку и все точки из соответствующего многоугольника (ей) как посещенные и верните многоугольник (ы).

...