CODEWITHSUNDEEP
intersectionrectanglesquadtree
ms4000kb
ms4000kb

Reputation: 73

Quadtrees: a common intersect method failing to handle a simple case

I am writing a simple GUI library and am using quadtrees to determine which, if any, objects are interacted with during a mouse event. I was looking through a number of quadtree libraries on github and they all contained a method for adding a rectangular object to a quadtree. The method, in all cases, simply checked to see if the rectangle intersected with the given quadtree:

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

However, this gives an unwanted result in one of the simplest cases: Imagine a 100x100 square area. I place four 50x50 square objects into the area with coordinates (0,0), (0,50), (50,0), and (50,50). If these objects had been placed into a 100x100 quadtree with a maximum capacity of one object, I would (visually) expect that the first layer of the quadtree would split and that the four resulting trees would each exactly contain one of the squares.

What should happen

If I use the above method to determine which tree the squares are placed into, though, I find that each object intersects with all four trees. This would cause each of the trees to rapidly split until the maximum depth is reached.

What does happen

The only way I see to avoid this is to use two checks:

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)

(in the simplest case. Larger objects would have to be viewed within a bounding box since, for example, an object with coordinates (0,0), w=100, h=100 would belong in the upper-left quadtree as well.)

I could also calculate the overlap between the rectangles and the quadtrees to see if it's non-zero.

Am I missing something? It seems like this should be an ideal situation for a quadtree, yet, in most implementations, it's a huge mess.

Upvotes: 1

Views: 1070

Answers (1)

TilmannZ
TilmannZ

Reputation: 1899

I wouldn't call this an ideal situation, because the four rectangles overlap by a fractional amount. For example, if we assume a (fictional) floating precision of 10^(-10), every 'point' is actually a small rectangle with 10^(-10) length, and thus the rectangles overlap by 10^(-10). This is why you get the deep tree.

But I also think the tree could be improved with a slightly modified overlap checking. With your code, the sub-nodes all overlap by a tiny amount. It would work better with excluding the minimum (or maximum values), for example: 

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

So the lower left coordinate of a node is actually outside of that node. This would at least avoid points turning up in several nodes (such as the point (50,50)), and the lower left rectangle would be stored in only one node.

Upvotes: 0

Related Questions