How to get the closest Axis-Aligned Bounding Box to a point?

Question

I have a large array of Axis-Aligned Bounding Boxes, I'm trying to get the euclidean distance from a point to the closest one, I have tried manhattan distance but it doesn't seem to match the "brute force" result by iterating over all of them with euclidean distance. Any efficient approaches? Cheers

Answer 1

I propose the following solution. You have the 5 rectagles as below and your point P is at (7,4)

If you build two sorted lists which are ordered by the horizontal edges and the vertical edges you will get:

List1 (Horizontal)
0  ((4,0),(8,0))->Rec5       index 0
1  ((4,1),(8,1))->Rec5       index 1
2  ((4,2),(6,2))->Rec1       index 2
3  ((8,3),(9,3))->Rec3       index 3
4  ((4,4),(6,4))->Rec1       index 4
4  ((10,4),(13,4))->Rec4     index 5
5  ((1,5),(6,5))->Rec2       index 6
6  ((10,6),(13,6))->Rec4     index 7
7  ((8,7),(9,7))->Rec3       index 8
8  ((1,8),(6,8))->Rec2       index 9

List2 (Vertical)
1  ((1,5),(1,8))->Rec2       index 0
4  ((4,0),(4,1))->Rec5       index 1
4  ((4,2),(4,4))->Rec4       index 2
6  ((6,2),(6,4))->Rec1       index 3
6  ((6,5),(6,8))->Rec2       index 4
8  ((8,0),(8,1))->Rec5       index 5
8  ((8,3),(8,7))->Rec3       index 6
9  ((9,3),(9,7))->Rec3       index 7
10 ((10,4,(10,6))->Rec4      index 8
13 ((13,4,(13,6))->Rec4      index 9

Now you can do a binary search on the Horizontal list on Py = 4. This is your starting index to work outwards in both directions. The same for Px = 7.

On your Horizontal list, you find H_index = 4 (Rec1)

On your Vertical list, you find V-Index = 4 (Rec2)

No match yet, move one out of centre in all directions (this step is repeated until one match)

H_index = 3 (Rec3)
H_index = 5 (Rec4)
V_index = 3 (Rec1)
V_index = 5 (Rec5)

We have a match->Rec1 (H_index = 4, V_index = 3)

If you want to find all equals, you are not done yet.

The x-distance between Px & rec1 = 1. you will need to include all Rectangles within this limit.

UpperLimit = 7 + 1 = 8
LowerLimit = 7 - 1 = 6

this gives V_index 3 to 8. For each of them check if Py is between or equal to the y values of the line.

6  ((6,2),(6,4))->Rec1       index 3      YES
6  ((6,5),(6,8))->Rec2       index 4      NO
8  ((8,0),(8,1))->Rec5       index 5      NO
8  ((8,3),(8,7))->Rec3       index 6      YES

So Rec3 is also found as a solution

The y-distance between Py & rec1 = 0. you wll need to include all Rectangles within this limit.

UpperLimit = 4 + 0 = 4
LowerLimit = 4 - 0 = 4

this gives H_index 4 to 5. For each of them check if Px is between or equal to the x values of the line.

4  ((4,4),(6,4))->Rec1       index 4     NO
4  ((10,4),(13,4))->Rec4     index 5     NO

No Other solutions found, we are done: Rec1 & Rec3 are closest.

This solution will be fast enough for up to 100.000 Rectangles. When you talk about milj. of Rectangles, you will need to use a Segment Tree.

Answer 2

• Build a BVH (bounding volume hierarchy) over your input boxes.
• recursively traverse a point through this BVH: in each step
  • if node is a leaf:
    • compute distance of point to box in this leaf
    • keep track of closest intersection found
  • else
    • compute distance of point to each of the children
    • (optional but recommended:) sort the children by distance
    • if child distance > closest already found distance: cull it;
    • otherwise: recurse into that child

To compute (euclidean) distance between point P and box B:

• compute point PB in box that's closest to P: PB = min(max(P,B.lower),B.upper)
• return euclidean length of P to PB : return length(P-PB)

To build a BVH over those boxes: just one of the options: Embree does have a interface to build BVHes over boxes, and query the result.