Шаг до RTree: разделите набор точек на прямоугольные области, каждая из которых содержит одну точку - PullRequest
Новая
       25

Шаг до RTree: разделите набор точек на прямоугольные области, каждая из которых содержит одну точку

6 голосов
/ 16 февраля 2009

учитывая мою текущую позицию (широта, лонг), я хочу быстро найти ближайшего соседа в задаче интереса. Таким образом, я намереваюсь использовать базу данных R-Tree, которая обеспечивает быстрый поиск. Однако сначала необходимо заполнить базу данных - конечно. Поэтому мне нужно определить прямоугольные области, которые покрывают область, где каждая область содержит одну точку интереса.

Мой вопрос заключается в том, как мне предварительно обработать данные, т.е. как я делю область на эти прямоугольные субрегионы? (Я хочу прямоугольные области, потому что они легко добавляются в RTree - в отличие от более общих областей Вороного).

/ John

Ответы [ 3 ]

2 голосов
/ 16 февраля 2009

Редактировать: Приведенный ниже подход работает, но игнорирует критическую особенность R-деревьев - способность расщепления узлов R-дерева хорошо определена и поддерживает сбалансированное дерево (через B-дерево свойства). Так что на самом деле все, что вам нужно сделать, это:

  1. Выберите максимальное количество прямоугольников на странице
  2. Создайте начальные прямоугольники (используйте точки, наиболее удаленные друг от друга, центроиды, что угодно).
  3. Для каждой точки выберите прямоугольник, чтобы поместить его в
    1. Если он уже упал в один прямоугольник, поместите его туда
    2. Если этого не произойдет, вытяните прямоугольник, который должен быть как минимум расширен (разные способы измерения «наименьших» выходов - область работает)
    3. Если применимо несколько прямоугольников - выберите один из них на основе его заполненности или другой эвристический
  4. Если происходит переполнение - используйте квадратное разбиение для перемещения ...
  5. И так далее, используя алгоритмы R-дерева прямо из учебника.

Я думаю, что метод ниже подходит для поиска ваших начальных прямоугольников семян; но вы не хотите заполнять все ваше R-дерево таким образом. Выполнение разделения и повторной балансировки все время может быть немного дорогостоящим, поэтому вы, вероятно, захотите выполнить приличную часть работы с подходом KD ниже; просто не вся работа.

Подход KD: заключите все в прямоугольник.

Если количество точек в прямоугольнике> пороговое, поворачивайте в направлении D, пока не закроете половину точек.

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

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

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

2 голосов
/ 16 февраля 2009

Oracle Spatial Cartridge Документация описывает алгоритм тесселяции, который может делать то, что вы хотите. Короче говоря:

  • заключите все свои точки в квадрат
  • если квадрат содержит 1 точку - индексный квадрат
  • если квадрат не содержит точек - игнорируйте его
  • если квадрат содержит более 1 пункта
    • разделите квадрат на 4 равных квадрата и повторите анализ для каждого нового квадрата

Результат должен выглядеть примерно так:
альтернативный текст http://download -uk.oracle.com / docs / cd / A64702_01 / doc / cartridg.805 / a53264 / sdo_ina5.gif

0 голосов
/ 16 февраля 2009

Я думаю, что вы что-то упустили в постановке задачи. Предположим, у вас есть N точек (x, y), таких что каждая точка имеет уникальные координаты x и y. Вы можете разделить свою область на N прямоугольников, просто разделив ее на N вертикальных столбцов. Но это не поможет вам легко решить ближайшую проблему POI, не так ли? Поэтому я думаю, что вы думаете о структуре прямоугольника, которую вы еще не сформулировали.

Иллюстрация: 

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

Цифрами являются POI, а вертикальные линии показывают подразделение на 7 прямоугольных областей. Но очевидно, что в подразделении не так много «интересной» информации. Есть ли какой-то дополнительный критерий для подразделения, о котором вы не упомянули?

...