2

I have a list of rectangles that don't have to be parallel to the axes. I also have a master rectangle that is parallel to the axes.
I need an algorithm that can tell which rectangle is a point closest to(the point must be in the master rectangle). the list of rectangles and master rectangle won't change during the algorithm and will be called with many points so some data structure should be created to make the lookup faster.
To be clear: distance from a rectangle to a point is the distance between the closest point in the rectangle to the point.
What algorithm/data structure can be used for this? memory is on higher priority on this, n log n is ok but n^2 is not.

Nemo
  • 70,042
  • 10
  • 116
  • 153
Daniel
  • 30,896
  • 18
  • 85
  • 139

4 Answers4

2

You should be able to do this with a Voronoi diagram with O(n log n) preprocessing time with O(log n) time queries. Because the objects are rectangles, not points, the cells may be curved. Nevertheless, a Voronoi diagram should work fine for your purposes. (See http://en.wikipedia.org/wiki/Voronoi_diagram)

For a quick and dirty solution that you could actually get working within a day, you could do something inspired by locality sensitive hashing. For example, if the rectangles are somewhat well-spaced, you could hash them into square buckets with a few different offsets, and then for each query examine each rectangle that falls in one of the handful of buckets that contain the query point.

jonderry
  • 23,013
  • 32
  • 104
  • 171
  • The Voronoi diagram looks promising but I didn't understand anything from the algorithm (http://en.wikipedia.org/wiki/Fortune%27s_algorithm). Do you know of any link for a easy description of the algorithm? – Daniel May 30 '11 at 12:22
  • This applet might help you visualize it, though it only shows the case of building a Voronoi diagram for points. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/Voronoi/Fortune/fortune.htm – jonderry May 30 '11 at 15:40
  • This visualization uses delta time system and not event based system. delta time system is inaccurate. – Daniel May 30 '11 at 15:43
  • I'm not sure what you mean by that. It's just processing the events from left to right. You can turn the animation off and just step through the events one by one. – jonderry May 30 '11 at 17:56
2

You should be able to do this in O(n) time and O(n) memory.

  1. Calculate the closest point on each edge of each rectangle to the point in question. To do this, see my detailed answer in the this question. Even though the question has to do with a point inside of the polygon (rather than outside of it), the algorithm still can be applied here.
  2. Calculate the distance between each of these closest points on the edges, and find the closest point on the entire rectangle (for each rectangle) to the point in question. See the link above for more details.
  3. Find the minimum distance between all of the rectangles. The rectangle corresponding with your minimum distance is the winner.
Community
  • 1
  • 1
Jason Moore
  • 3,294
  • 15
  • 18
1

If memory is more valuable than speed, use brute force: for a given point S, compute the distance from S to each edge. Choose the rectangle with the shortest distance.

This solution requires no additional memory, while its execution time is in O(n).

Depending on your exact problem specification, you may have to adjust this solution if the rectangles are allowed to overlap with the master rectangle.

Philip
  • 5,795
  • 3
  • 33
  • 68
0

As you described, a distance between one point to a rectangle is the minimum length of all lines through that point which is perpendicular with all four edges of a rectangle and all lines connect that point with one of four vertices of the rectangle.
(My English is not good at describing a math solution, so I think you should think more deeply for understanding my explanation).
For each rectangle, you should save four vertices and four edges function for fast calculation distance between them with the specific point.

coolkid
  • 543
  • 8
  • 21
  • One wrinkle is that the perpendicular distance between a query point and a line corresponding to a rectangle edge could lie outside (before the start or after the end) of the edge itself. So you need to test for that. – j_random_hacker Jun 04 '11 at 07:04
  • Yeas, In the post I said that there's some cases that the distance is not the perpendicular distance but a line connect the query point with one vertex of the rectangle. – coolkid Jun 04 '11 at 11:07
  • The way you have worded it implies that the minimum of the two cases (perpendicular-distance-to-line, and distance-to-vertex) is the right answer, when that's not true -- it may be that the minimum is the perpendicular distance, but the intersection point for this distance lies outside the line segment. In that case, a (larger) distance to a vertex is the right answer. – j_random_hacker Jun 05 '11 at 12:43
  • Yes, because my explanation is not clear. Thanks for suggestion. – coolkid Jun 05 '11 at 16:05