Find all bounding boxes intersecting with a given point (using a tree structure)

1k Views Asked by At

I've created a function that loops through a list of 2d bounding boxes and finds those that contain the given 2d point. Unfortunately this is quite slow so I was looking for a way to optimise it using some kind of tree structure.

I've seen lots of questions based on finding points within boxes but none for finding boxes from a point. I know how to do the intersection so it's just the tree structure I'm interested in. I thought a quadtree might suit but I'm not sure how it would handle having bounding boxes duplicated in different nodes.

Would it be best to use some kind of binary search tree where I split the x and y axes recursively (like a median cut)?

1

There are 1 best solutions below

1
On BEST ANSWER

I would suggest you to use a segment tree.

Have a look at these slides:

http://algo.kaust.edu.sa/Documents/cs372l07.pdf

you are particularly looking for a solution to stabbing queries in higher dimensions (slide 25)