R * Дерево перекрытия вычислений

Я читал эта реализация дерева R *, и я заметил, что они рассчитывают перекрытие по-разному от того, как бумага определяет это.

В статье перекрытие определяется так:

Для данного узла / прямоугольника К, вычислить сумму площади пересечения между К и каждый брат К (не включая К).

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

Что-то вроде этого:

childOverlapEnlargement(Node child, item r)
{
childEnlarged = child.union(r);
sum = 0;
for(each sibling s of child which isn't node)
{
sum += area(childEnlarged.intersect(s)) - area(child.intersect(s));
}
return sum;
}

В другой реализации они сортируют по области пересечения данного узла с вставляемым элементом. Что-то вроде этого:

childOverlapEnlargement(Node node, item r)
{
return area(node.intersect(r));
}

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

Итак, мои вопросы:

  1. Всегда ли в обоих вычислениях выбираются одни и те же поддеревья? Зачем?
  2. Если они приводят к выбору разных поддеревьев, результаты лучше или близки к определению статьи? Или выбор был сделан по ошибке?

редактировать: перечитать их реализацию, и я понял, что они сравнивали не пересечение двух братьев и сестер, а пересечение каждого потенциального листа и вставляемого элемента. Как ни странно, они выбирают родного брата, который меньше всего пересекается со вставленным предметом. Разве вы не хотите вставлять в узел, который больше всего перекрывается с вставляемым элементом?

1

Решение

Возможно, реализация, на которую вы смотрите, имеет ошибки или неверна. Никто не совершенен.

Обратите внимание, что R * -дерево пытается минимизировать увеличение перекрытия, не перекрывать себя.

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

Что касается соображений производительности, проверьте, нужно ли вам на самом деле вычислять прямоугольники пересечения. Попробуй вместо вычислений area(intersection()) сделать функцию intersectionSize(), это делает Сделать разницу. Например, если A.maxX = 1 а также B.minX = 2 Я могу сразу дать размер пересечения 0, не глядя ни на какие другие измерения.

Избегайте заранее рассчитывать все пересечения и т. Д., Которые могут вам понадобиться. Вместо этого вычисляйте только те, которые вам действительно нужны. Профиль ваш код, и посмотрите, можете ли вы оптимизировать критические пути кода. Там обычно есть какие-то низко висящие фрукты.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]