Нахождение оптимальной глубины / диапазонов в наборе четырехугольных деревьев для оптимизации поиска точек в ограничительной рамке
Если бы у меня был набор четырех деревьев (скажем, по кривой Гильберта), что было бы хорошим способом приблизиться к поиску оптимального (или достаточно хорошего) набора диапазонов на определенной глубине.
Например, если я ищу точки между ограничительной рамкой 0,0 и 1,3, тогда я могу применить следующие наивные диапазоны:
- Глубина 1 - диапазон 0,0-1,0 (~33% пространства поиска)
- Глубина 2 - диапазоны 0,0-1,0 и 1,0-0,1 (~13% пространства поиска)
- Глубина 3 - диапазоны 0,0-1,0 и 1,3-0,3 (~9,8% пространства поиска)
Очевидно, что глубина 3 для этого поиска является оптимальной, но уменьшенное пространство поиска уменьшилось лишь на небольшое количество по сравнению с падением с глубины 1 на глубину 2.
При (значительно) больших глубинах или при поисках, которые пересекают границы, существует хороший алгоритм (ы) для оценки разницы между различными глубинами или для идеального выбора комбинации диапазонов на разных глубинах, которые в идеале покрывают ограничивающий прямоугольник.
Меня не интересуют конкретно полигоны, а бонусные баллы, если есть решение, которое работает для полигонов.
2 ответа
Хотя ваш вопрос требует более подробной информации, некоторые ответы:
Вы можете оценить глубину четырехугольника по log4 (N).
(Возьмите логарифм основания 4 числа элементов N.)
В зависимости от типа дерева квадрантов вы можете ограничить максимальную глубину до этого числа.
Порядок вставки элементов влияет на структуру квадрата. Предварительная сортировка данных перед вставкой может немного улучшить структуру квадрата. Тип предварительной сортировки зависит от четырехугольника. если вы используете четырехугольник с резервным копированием Гильберта, вы можете предварительно отсортировать данные по индексу Гильберта.
Когда вы используете кривую Гильберта, это пространственный индекс, а не квадродерево. У квадродерева также есть некоторые ограничения, например, сколько точек вы можете хранить. Таким образом, на кривой Гильберта лучше использовать маленькие плитки, чтобы ограничивающая рамка могла хорошо вписаться.