Quadtrees: общий метод пересечения, не справляющийся с простым случаем

Question

Я пишу простую графическую библиотеку и использую квадранты, чтобы определить, с какими объектами взаимодействуют во время события мыши. Я просматривал несколько библиотек quadtree на github, и все они содержали метод добавления прямоугольного объекта в квадрант. метода, во всех случаях, просто проверить, чтобы увидеть, если прямоугольник пересекается с заданным квадрадеревом:

return quadtree.x2 >= rect.x1 
    and quadtree.x1 <= rect.x2 
    and quadtree.y2 >= rect.y1 
    and quadtree.y1 <= rect.y2 

Однако это дает нежелательный результат в одном из простейших случаев: Представьте 100x100 квадратную область. Я помещаю в площадь четыре квадратных поля размером 50x50 с координатами (0,0), (0,50), (50,0) и (50,50). Если бы эти объекты были помещены в квадратику 100x100 с максимальной пропускной способностью одного объекта, я бы (визуально) ожидал, что первый слой квадранта разделится и что четыре результирующих дерева будут точно содержать один из квадратов.

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

Единственный способ я вижу, чтобы избежать этого является использование двух проверок:.

return (quadtree.x2 > rect.x1 
    and quadtree.x1 < rect.x2 
    and quadtree.y2 > rect.y1 
    and quadtree.y1 < rect.y2) 
    or (quadtree.x2 == rect.x1 
    and quadtree.x1 == rect.x2 
    and quadtree.y2 == rect.y1 
    and quadtree.y1 == rect.y2) 

(в простейшем случае крупные объекты должны рассматриваться в ограничительной рамке, так как, Например, объект с координатами (0,0), w = 100, h = 100 также будет принадлежать и в верхнем левом квадтри.)

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

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

Answer 1

Я бы не назвал это идеальной ситуацией, потому что четыре прямоугольника перекрываются дробной суммой. Например, если мы предположим, что (пунктирная) плавающая точность 10^(- 10), каждая «точка» на самом деле представляет собой маленький прямоугольник с длиной 10^(- 10), и, следовательно, прямоугольники перекрываются на 10^(- 10) , Вот почему вы получаете глубокое дерево.

Но я также думаю, что дерево можно улучшить с помощью слегка модифицированной проверки перекрытия. С вашим кодом суб-узлы все перекрываются крошечной суммой. Было бы лучше работать с исключением минимального (или максимального значения), например:

return quadtree.x2 >= rect.x1 
    and quadtree.x1 < rect.x2 
    and quadtree.y2 >= rect.y1 
    and quadtree.y1 < rect.y2 

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