Reputation: 4329
What is the most efficient way to determine if a point is in any number of boxes
I know how to check if a X,Y point is a single rectangular region, but say I have multiple regions that can potentially overlap ( the regions would have X,Y,Width,Height,Z-index ( or x1,y1,x2,y2 if that's easier -- I am not fussed on how I store that, if it's relevant )
Are there any efficient algorithms to determine if the point is inside one of the regions without having to iterate over every region.
I would prefer something without a long recalculation time when a region is added or removed, however that will be rarer then lookups.
Thank you!
Upvotes: 3
Views: 136
Answers (2)
Reputation: 28541
You could store your regions into a Quadtree (or Octree if 3D). This would help you to reject most of the regions before getting into the real collision-test.
If you have multiple layers, simply have a quadtree per layer and use the relevant one according to the layer in which your point lies.
Upvotes: 3
Related Questions
- Determining if a set of points are inside or outside a square
- Is there a more efficient way of checking if an element is inside given intervals?
- How can I find a box that encompasses all given boxes?
- Check if point inside random boxes
- Area of the nearest boxes
- Fastest way to determine whether elements of a vector y occur in a vector x
- Efficient way to find set of objects inside or intersecting bounding box?
- I have a large list of bounding boxes, how can I calculate duplicates?
- Find out if point is inside one of N (possibly overlapping) rectangles in less than O(N)
- checking if a point is already in a vector/list -- performance