Алгоритм построения r-tree с использованием многоугольника mbr

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

for p1 in polygons: # O(n)
    for p2 in polygons: # O(n)
        if p2 is not p1: # O(1)
            if p2.intersects(p1): # O(1); computed using DeMorgans law on vertices
                # do stuff

Есть ли у кого-нибудь ссылка, которая обозначает методы определения разбиения прямоугольников, охватывающих MBR многоугольников в наборе?

То же, что и для очков. Потому что на следующем уровне дерева каждая страница является MBR.

Has QUIT--Anony-Mousse 11.08.2018 16:13

@ Anony-Mousse. Как и в моем комментарии к ответу ниже, моя реальная проблема заключается в том, чтобы определить, какие прямоугольники следует сгруппировать. У меня проблемы с осмыслением этой детали.

pstatix 13.08.2018 17:27

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

Has QUIT--Anony-Mousse 13.08.2018 17:59
0
3
381
1

Ответы 1

Существует множество алгоритмов разделения R-Tree, по моему опыту, лучший из них - R * Tree (R-Star-Tree) от Beckmann et al. Просто найдите «R * -дерево: эффективный и надежный метод доступа для точек и прямоугольников».

Если вы предпочитаете читать код, существует также множество реализаций с открытым исходным кодом, включая мой собственный на Java. Однако будьте осторожны, алгоритм R * Tree нетривиален.

Если вы ищете что-то попроще, попробуйте квадродеревья или октодеревья. Если скорость вставки и обновления является наивысшим приоритетом, взгляните на PH-дерево (снова моя собственная реализация), но он также более сложен, чем квадродеревья.

Еще одно более простое решение - AABB-дерево, оно похоже на R-Tree, но только с двумя ограничивающими прямоугольниками на узел. Думаю, он часто используется в компьютерной графике, но я мало о нем знаю, за исключением того, что это относительно просто для R-Tree.

РЕДАКТИРОВАТЬ (обновить, чтобы ответить на комментарий)

Если вы ищете стратегию массовой загрузки, такую ​​как STR, здесь - это исходная бумага. Вы можете взглянуть на мою реализацию R-Tree, поскольку она также предоставляет реализация STR-загрузчика, который может обрабатывать точки и прямоугольники.

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

Я хотел бы отметить, что массовая загрузка (например, STR-загрузка) - это самый быстрый способ загрузки R-Tree. Однако в моих собственных экспериментах (см. Рисунок 3 здесь) это все еще в 2-3 раза медленнее, чем хорошее дерево квадрантов или PH-дерево.

Я искал реализации массовой загрузки или упаковки R-Tree; например, Nearest-X или STR, мне не нужно динамическое дерево.

pstatix 11.08.2018 01:18

Спасибо за обновление. Прочитав предоставленные документы, я полагаю, я не понимаю, как устроены «страницы». Вы должны указать максимальное количество страниц на лист, и каждая страница указывает на новую страницу. Итак, почему в вики некоторые листы имеют только 2 страницы, а некоторые - 3?

pstatix 12.08.2018 23:47

AABB-Tree, наверное, для меня хорошее начало. Проблема, которую я не могу понять, заключается в том, как решить, какие прямоугольники сгруппированы вместе. В примере AABB-Tree, очевидно, 1 и 3 идут вместе, но как это решено?

pstatix 13.08.2018 17:01

В примере с вики 2 - это минимальное количество записей на страницу / узел (страницы такие же, как и узлы), максимальное - 3. Если у вас их больше 3, вам нужно разделить. Если у вас меньше 2 (после удаления) вы сливаетесь.

TilmannZ 13.08.2018 22:31

На странице AABB говорится: «Общая эвристика, используемая здесь, состоит в том, чтобы назначить стоимость площади поверхности левого и правого узлов, скорректированной для добавления AABB нового листа, и спуститься в направлении самого дешевого узла, пока вы не найдете себя на листе. ". Другими словами, при вставке нового элемента вы вычисляете, насколько должна вырасти поверхность AABB каждого узла, чтобы охватить новый элемент. Затем вы вставляете элемент в узел, который должен расти меньше всего.

TilmannZ 13.08.2018 22:32

Как определить максимальное количество записей на страницу / узел в R-дереве?

pstatix 28.08.2019 01:46

Если вы храните дерево на жестком диске, вы должны выбрать количество записей так, чтобы они помещались в сектор / страницу. Что касается оперативной памяти, я бы определил ее экспериментально, чтобы увидеть, что дает лучшую производительность. Я обнаружил, что значения от 5 до 10 дают неплохие результаты.

TilmannZ 23.09.2019 21:57

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

pstatix 24.09.2019 20:36

Другие вопросы по теме