Какой метод предпочтителен для хранения больших геометрических объектов в дереве квадрантов?

15

Размещая геометрические объекты в квадри (или октодереве), вы можете разместить объекты, размер которых превышает один узел, несколькими способами:

  1. Размещение ссылки на объект в каждом листе, для которого он содержится
  2. Размещение ссылки на объект в самом глубоком узле, для которого он полностью содержится
  3. И № 1, и № 2

Например:

введите описание изображения здесь

На этом изображении вы можете разместить круг во всех четырех конечных узлах (метод № 1) или только в корневом узле (метод № 2) или в обоих (метод № 3).

Для целей опроса quadtree какой метод более распространен и почему?

nsantorello
источник
1
Конечно, это должна быть ссылка. Я намереваюсь спросить, должны ли в целях запроса к дереву ссылки быть в листьях, не листьях, или в обоих.
nsantorello
PS Отредактировано, чтобы, надеюсь, прояснить намерения вопроса.
nsantorello
Какой запрос вы пытаетесь поддержать?
Джо
@Joe Я особенно заинтересован в обнаружении столкновений, пространственной индексации и отбраковке областей / усечений.
nsantorello
1
@nsantorello Правило может отличаться в зависимости от того, какие из этих запросов вы хотите поддерживать, но это кажется очень важным для обнаружения коллизий: stackoverflow.com/questions/4434335/…
Джо

Ответы:

8

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

Например, если вы вычисляете столкновения с этим (сплошным) кругом, и столкновение происходит в левом нижнем углу, было бы проще, если бы у вас был доступ ко всей геометрии в этом листе непосредственно из этого листа (метод № 3) (без необходимости обходить дерево вверх и определять унаследованную геометрию). Но, скажем, вы просто использовали квадри для рисования геометрии, вам нужно использовать метод № 1, потому что имеет смысл рисовать что-то только в узле, для которого оно полностью содержится (было бы сложнее выяснить, какая часть нарисовать для каждого листа узла и где).

Что касается того, что более распространено, мой единственный опыт работы с квадриами - это написание симуляции n-тела, где геометрические объекты были просто точками, которые не имели площади, поэтому я не могу однозначно ответить на это.

Рэйф Кеттлер
источник
Спасибо Rafe, я думаю, что вы правы, что это зависит от приложения.
nsantorello
6

Одним из преимуществ Quadtree является то, что вам не нужно разбивать узел на его дочерние узлы, если все дочерние узлы будут содержать одинаковую информацию. Это может сэкономить вам много памяти и ускорить обработку.

Следуя этому принципу, я думаю, что имеет смысл хранить его только в корневом узле (метод № 2). Это может сэкономить вам много памяти, и я думаю, что также облегчит обработку. Например, если вы попытались найти пересечения окружности с линией, проходящей через три листовых узла, вам нужно будет либо вычислить пересечение отдельно для каждого листового узла, либо помнить, что вы уже пересекались с этим кружком.

С другой стороны, если у вас есть объекты в конечных узлах, это может помочь вам исключить ложные срабатывания (объекты, которые вы должны проверить на предмет пересечения, поскольку они находятся в правильном узле, но на самом деле не пересекаются).

Итак, я думаю, что оба подхода имеют свое применение, и я не уверен, как выбрать, какой использовать.

Я, вероятно, не использовал бы подход № 3, потому что я не вижу в этом ничего положительного.

svick
источник