Я видел, что октреи часто используются для таких вещей, как отбраковка усеченного конуса и обнаружение столкновений в 3D. Но я просто не уверен, как работает алгоритм вообще. Конечно, весь принцип октодерева нарушается, когда вы пытаетесь использовать ограничивающие блоки, потому что любой данный блок может храниться в одном узле, но фактически перекрывать пространство, представленное другим узлом. Кроме того, я не уверен, как это может сработать при поиске ограничивающих рамок, а не точек, потому что, опять же, вы можете застрять, просматривая практически все узлы, побеждая цель.
Так как же октреи справляются с ограничивающими рамками?
источник
n-деревья - самая известная, но не единственная доступная система пространственного разбиения. Есть много, много других. Немного больше информации о данных, которые у вас есть, во многом поможет найти лучший выбор. Ваши коробки меняют размер или передвигаются? Насколько они большие? Сколько их там? У вас много вставок / удалений?
источник