Размещая геометрические объекты в квадри (или октодереве), вы можете разместить объекты, размер которых превышает один узел, несколькими способами:
- Размещение ссылки на объект в каждом листе, для которого он содержится
- Размещение ссылки на объект в самом глубоком узле, для которого он полностью содержится
- И № 1, и № 2
Например:
На этом изображении вы можете разместить круг во всех четырех конечных узлах (метод № 1) или только в корневом узле (метод № 2) или в обоих (метод № 3).
Для целей опроса quadtree какой метод более распространен и почему?
graphics
data-structures
computational-geometry
nsantorello
источник
источник
Ответы:
Предполагая, что вы храните ссылку, а не сам объект, может иметь смысл сделать это по-разному в зависимости от вашего приложения.
Например, если вы вычисляете столкновения с этим (сплошным) кругом, и столкновение происходит в левом нижнем углу, было бы проще, если бы у вас был доступ ко всей геометрии в этом листе непосредственно из этого листа (метод № 3) (без необходимости обходить дерево вверх и определять унаследованную геометрию). Но, скажем, вы просто использовали квадри для рисования геометрии, вам нужно использовать метод № 1, потому что имеет смысл рисовать что-то только в узле, для которого оно полностью содержится (было бы сложнее выяснить, какая часть нарисовать для каждого листа узла и где).
Что касается того, что более распространено, мой единственный опыт работы с квадриами - это написание симуляции n-тела, где геометрические объекты были просто точками, которые не имели площади, поэтому я не могу однозначно ответить на это.
источник
Одним из преимуществ Quadtree является то, что вам не нужно разбивать узел на его дочерние узлы, если все дочерние узлы будут содержать одинаковую информацию. Это может сэкономить вам много памяти и ускорить обработку.
Следуя этому принципу, я думаю, что имеет смысл хранить его только в корневом узле (метод № 2). Это может сэкономить вам много памяти, и я думаю, что также облегчит обработку. Например, если вы попытались найти пересечения окружности с линией, проходящей через три листовых узла, вам нужно будет либо вычислить пересечение отдельно для каждого листового узла, либо помнить, что вы уже пересекались с этим кружком.
С другой стороны, если у вас есть объекты в конечных узлах, это может помочь вам исключить ложные срабатывания (объекты, которые вы должны проверить на предмет пересечения, поскольку они находятся в правильном узле, но на самом деле не пересекаются).
Итак, я думаю, что оба подхода имеют свое применение, и я не уверен, как выбрать, какой использовать.
Я, вероятно, не использовал бы подход № 3, потому что я не вижу в этом ничего положительного.
источник