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

Question

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)?

will do, it's my first question so didn't realise!

LoweredTone
– LoweredTone

2014-11-21 15:49:13 +00:00
Commented Nov 21, 2014 at 15:49 — LoweredTone
– LoweredTone, Commented Nov 21, 2014 at 15:49

Juan Leni · Accepted Answer · 2014-11-21 10:45:33Z

1

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)

edited Nov 21, 2014 at 10:45

answered Nov 20, 2014 at 17:35

Juan Leni

7,7488 gold badges62 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

LoweredTone Over a year ago

Thanks, that looks ideal for bounding box searching as it deals well with overlaps and has a binary search speed

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related