Пытаюсь тут написать на 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? И почему речь идет о полученной виличине, если мы получили две величины?
Дальше рассматривать алгоритм смысла не было, без понимания первой части. Альтернативных описаний алгоритма я не нашла. Может кто-нибудь подскажет?
