Quickly locating nearest rectangle from a point

The problem is as follows:


There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the nearest rectangle from $p$? The distance from a point $p$ to a rectangle $R$ is defined as the Euclidean distance between $p$ and its nearest counterpart $q \in R$. If $p$ is inside the rectangle, then the distance is $0$.

Actually what I want is the distance between $p$ and its nearest rectangle, so if we can directly get this distance, it's even better.

The naive solution is to compute the distance between $p$ and each rectangle, however this is time consuming in my case, so I want to know if there exists such a data structure.

Edit:

These rectangles may intersect, and the total number is very likely less than 20 (typically around 5). It is trivial if we only want to know this minimal distance for a few points, linear scan will do the work. However when the number of such points becomes very large, the overall computation overhead cannot be ignored, that's why I want to quickly find the nearest rectangle.

I expect the best option is to use some kind of spatial index. Here's a first suggestion, but I'm sure there are better solutions.

• Create a quad tree with a maximum bucket capacity of $m$.

• For each new rectangle, traverse the tree, and store a pointer to the rectangle at each bucket that intersects the rectangle.

Now to find the nearest rectangle for a point $p$:

• Find the bucket $B$ the point falls in.

• Find the distance $d$ to the nearest rectangle $B$.

• Check all surrounding buckets for rectangles that might be closer than $d$.

The last step might still be expensive if you're unlucky, but you can effectively eliminate all buckets that are itself further from $p$ than $d$.

StackExchange Computer Science Q#28691, answer score: 2