LINUX.ORG.RU

Линейный алгоритм деления узла для r-дерева

 


1

3

Пытаюсь тут написать на C++ R-дерево для хранения графических (2d) элементов.

Столкнулась с самой неприятной проблемой - понимания написанного. На википедии в разделе «Функция linearSplit» имеется описание алгоритма, но после первой строчки мой мозг начинает кричать «я не хочу программировать, я хочу варить борщ!»

Предположим, что мы храним в дереве элементы со свойством boundingRect (x, y, width, height). Максимальное количество элементов в узле - 4, минимальное - 2. Имеем дерево:

Изображение дерева.

  • R - корень дерева
  • V1, V2, V3 - внутренние узлы, имеющие по четыре потомка (для
  • V1, V2 и V3 не отобразила для экономии места)
  • V5, V6, V7, V8 - листовые узлы имеющие по черыте элемента (для V5, V6, V7 так не отобразила для экономии места).
  • O1, O2, O3, O4 - элементы.

Все описанные выше сущности имеют mbr.

Предположим, что мы вставляем элемент O5. Самый подходящая листовая вершина для него - V8 (изменение mbr минимально).

1) Правильно ли я понимаю, что этом случае будет создана новая вершина (V’) и в функцию линейного разделения будут переданы вершины V7 и V’, в которой будет произведено рапределение элементов (O1, O2, O3, O4, O5) в соответствии с их mbr между этими вершинами (V7, V’)?

2) Правильно ли я понимаю, что так как в нашем случае происходит раскол до корня дерева, функция линейного разделения будет вызвана и для вершин V4, V’’, в которой будет произведено распределение листовых вершин (V5, V6, V7, V8, V’) по тому же алгоритму? И так далее пока не дойдем до корня?

Теперь что касается самого алгорима распределения. Вот что написано в вики:

По каждой координате…

Имеется ввиду измерение? В нашем случае x и y?

...для всего набора разделяемых вершин...

В случае, если мы добавляем O5 и производим деление узла V8 что тут является разделяемыми вершинами? Смущает фраза “для всего набора разделяемых верших”, ибо как бы говорит, что их может быть больше двух. Значит это не невршины V8, V’, а (в данном случае), элементы O1-O5?

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

Как я понимаю выбирается максимальный (left/x+w) (bottom/y+h) и минимальный (right) (top) и вычисляется разница... Но ведь это по сути ширина и высота mbr для этой группы объектов?

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

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

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


Как так, упоминание борща в ОП-посте есть, а ФП- или лисповброса нет?

anonymous ()

ты вику нерусскую читай. Гуглотранслятор адекватнее будет.

emulek ()
Ответ на: комментарий от true_admin

вот:

Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, как географические данные с двумерными координатами (широтой и долготой). Типичным запросом с использованием R-деревьев мог бы быть такой: «Найти все музеи в пределах 2 километров от моего текущего местоположения».

это последний разумный абзац. Дальше у переводчика сорвало планку,

Вам нужен новый гуртовщик мыши. Если вы пользователь Microsoft мыши посетите Microsoft Слугу Паутины, где в особом подвале вы сможете опустить-загрузить самого текущего гуртовщика Microsoft мыши. Если производитель вашей мыши другой, узнайте о ее гуртовщике. Все основные производители мыши уже имеют гуртовщиков мыши для Окон 95.

emulek ()
Ответ на: комментарий от true_admin

мне как-то тут практическая попалась. Няня я у них поел.

emulek ()

Пойду-ка я борщ варить.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.