Какой самый эффективный способ определить, находится ли точка в любом количестве ящиков

Question

Я знаю, как проверить, является ли точка X, Y одной прямоугольной областью, но, скажем, у меня есть несколько областей, которые потенциально могут перекрываться (области будут иметь X, Y, Ширина, Высота, Z-индекс (или x1, y1, x2, y2, если это проще - меня не волнует, как я это храню, если это уместно)

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

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

Спасибо!

Answer 1

Вы можете сохранить свои регионы в Quadtree (или в Octree, если 3D). Это поможет вам отклонить большинство регионов, прежде чем приступить к настоящему испытанию на столкновение.

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

Answer 2

Объемные кд-деревья ?