Можем ли мы применить Quad-Tree к не квадратному прямоугольнику?

Question

Я пытаюсь реализовать двумерное быстрое обнаружение столкновений с помощью Quad-Tree.

AFAIK, Quad-Tree делит регион на 4 субрегиона: северо-запад, северо-восток, югвосток и юго-запад.Это деление отлично работает с квадратом .Но что, если регион представляет собой не квадратный прямоугольник ?В этом случае мы не можем равномерно разделить длинный край и короткий край, и короткий край определяет, как далеко мы можем разделить.

Прав ли я в этом?Это должно быть?

Answer 1

Просто возьмите максимальную ширину и высоту ограничительной рамки интересующей области в качестве длины стороны четырехугольного дерева.

Другое решение: использует две реализации четырехъядерных деревьев, которые я виделвнутренний прямоугольник, так что он выпал бы из коробки, даже если предоставленные корневые границы не квадратные.Они делят ширину и высоту границ на каждом шаге подразделения.
Но учтите, что существует более 10 различных типов Quadtree.Я говорю о Rectangle Quadtrees.

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

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