4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can the rectangles intersect? If not, then you can reduce the problem to finding the closest line segment. $\endgroup$ – Craig Gidney Jul 24 '14 at 15:50
  • $\begingroup$ @Strilanc Yes they may intersect, please see my edit. $\endgroup$ – Erratum Jul 25 '14 at 3:45
  • 1
    $\begingroup$ There's only five? Just test every point against all five! A clever algorithm will only be worth it when there's lots of rectangles, not five. Using a spatial index will just add cache pressure and hurt performance. $\endgroup$ – Craig Gidney Jul 25 '14 at 3:58
  • $\begingroup$ @Strilanc That's what I'm doing right now...I'm not sure whether it's possible to further improve the efficiency. IMHO, if some index structure supports fast retrieval of such rectangle (ideally in O(1)), then even if the building process is costly, the amortized overhead is still negligible since there are so many points. In this case, I'm not expecting to achieve orders of magnitudes improvement, I know this is simply impossible, however an improvement in the constant factor is still desirable. $\endgroup$ – Erratum Jul 25 '14 at 4:29
  • $\begingroup$ @Strilanc According to my experiment, if for each point we only need one distance computation, then it'll be 7-8 times faster. $\endgroup$ – Erratum Jul 25 '14 at 4:30
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks! I agree that some kind of spatial index will be helpful, however since the number of rectangles are relatively small (please see my edit), I'm afraid the speedup may not pay off the extra overhead on the index...I was trying to come up with an index structure dedicated to this specific problem, unluckily I made little progress so far. $\endgroup$ – Erratum Jul 25 '14 at 3:52
1
$\begingroup$

Here's another approach:

The rectangles basically form a generalized Voronoi diagram where the seeds are rectangles instead of points. Each cell in this diagram forms a polygon. The algorithm for computing these polygons is basically the same as that of the regular Voronoi diagram: compute the boundary cutting the plane in to two half-spaces for each pair of rectangles, and intersect the resulting half-spaces over all pairs to find the correct polygon. The polygons (unfortunately) are not necessarily convex, but you can split each polygon into a set of convex polygons

Once you have this list of convex polygons, partitioning the plane, each mapping to a rectangle, all you have to do for a given point is to find which polygon it's in. This can be done by computing the dot product for each side of the polygon, to find which side of the line it's on.

If you do this straightforwardly, you end up with $O(nm)$ dot product computations for $n$ polygons with $m$ sides each, which is probably not better than computing the distance to the rectangles normally. However, each test for the point against a line segment basically eliminates all polygons on one side of the line. You can use this to find a binary tree where each node represents a choice of line segment in the diagram against which you compute the dot product, and the leaves contain a ginle polygon. This suggests that if you have $n$ convex polygons, you can decide the correct polygon in $\log_2 n$ computations of a single inproduct. I expect this will be efficient, but you might be unlucky and get lots of non-convex polygons that have to be split into many convex ones.

It's quite a job to work all this out into an actual algorithm, and I'm sure I've overlooked some things, but the literature on generalized Voronoi diagrams seems to be quite extensive, so with a little reading you should be able to work it out (if the speedup is worth the effort).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.