4

On a 2D plane, I have 2 rectangles. I want to find the closest pair of points (one on each rectangle), which are closest to each other. By points I mean the corners of the rectangles. And no, they do not overlap.

Is there any way to do that other than checking all the distances between all the combinations of points and finding the smallest one?

  • Maybe Math.SE would be the best place. Is there a chance those rectangles overlap? In any casethere should be two sides closer to each other than any other two sides so you could already reduce search to those. (btw are you talking about corners of those rectangles, points on the sides or any point anywhere within?) In any case either the corners or sides are the only relevant. Unless they overlap on which case you have zero distance in that region. – thorsten müller Jan 19 '14 at 12:41
  • What do you do when they are parallel to one another? – JeffO Jan 19 '14 at 12:47
  • @JeffO Does it matter if they are parallel? – shoham Jan 19 '14 at 12:52
  • 3
    @shoham in such case there can be more than one correct answer – Konrad Morawski Jan 19 '14 at 12:53
  • 4
    What makes you believe the nearest points are always corners on both rectangles? One of the points could be in the middle of an edge (I assume the rectangles can be oriented arbitrarly in the 2D plance, since you did not include any restriction on that in your question). So your "brute force" solution won't work for that case. – Doc Brown Jan 19 '14 at 18:26
1

How you do it depends on what your "business" requirements are.

If simplicity of source code (maintainability) is your primary concern, then brute force calculation of all of the point to point distances will be a simple and effective method. If you have to optimize for processing speed, then you may want to find an optimized algorithm. I suspect that brute force will be nearly optimal in any case since there are only 16 point-to-point distances to calculate.

  • I need it to be as efficient as possible. How can I optimize it? – shoham Jan 19 '14 at 12:56
  • @shoham - trying to optimise risks slowing it down. A more sophisticated approach means more complex code, working more slowly per item checked. This is only worthwhile when you can avoid checking large numbers of items. In this case, you might be able to use some kind of nearest-neighbour data structure to help "optimise" your search, but I'm betting it would end up slower. If you really need an optimised approach, you'll need to try several alternatives (including this simple brute force) and measure to see how they work out. – Steve314 Jan 19 '14 at 13:00
  • 1
    @shoham - one quick example - if you could eliminate "back-facing" corners, you'd only need to check 9 combinations of corners rather than 16. Given that the rectangles don't overlap, that's not so difficult. For each rectangle, calculate a center point. For each edge, calculate (using IIRC a cross product) which direction faces out. Dot products between cross products and other-rectangle centers yada yada - a lot like backface elimination for 3D games. A corner that has both it's edges as "back facing" cannot be a nearest corner and is eliminated. Trouble is, that's more work than you save. – Steve314 Jan 19 '14 at 13:09
  • 1
    @shoham - or you're focussing on the wrong element of a larger problem, perhaps. If you're concerned about the performance, presumably you'll be doing it a lot - meaning there's a larger problem that might have some exploitable structure to reduce how much you do it. Or maybe within that larger problem there's something to gain by building a data structure with all the rectangles. – Steve314 Jan 19 '14 at 13:15
  • 3
    @shoham the standard way to calculate distance between two points is to use Pythagorean theorem of course, but when you have to compare two distances (say A-B and A-C), you can do a quick check because if |Ax - Bx| > |Ax - Cx| and |Ay - By| > |Ay - Cy| then you're 100% guaranteed that A and B are further away than A and C and you don't need to calculate square roots to verify that (square roots are many times more expensive computationally than simple arithmetics!). This by itself would optimize your calculations by a few times. – Konrad Morawski Jan 19 '14 at 22:11
1

You could take the "center of mass" average of all corners on the plane (a new point which is at average x and the average y coordinate of all corners), then take the corner of each rectangle that is closest to that center of mass point. After your initial calculation of the center of mass, you would only need to run a single calculation for each corner.

If either rectangles happen to have more than one point that are equally distant from the overall center of mass then you would need to ensure you choose from among the tied points the two (one from each rectangle) that are closest to each other, and in this case you could just do the n^2'ed thing (although if we are dealing with convex polygons, such as rectangles, there could only be a max of 2 ties per polygon, so at this step there would only ever be an additional 2 or 4 calculations - depending on if one or both polygons contained ties).

This algorithm would scale very well (O(n)) for any two convex polygons each containing any number of corners (and their own center of mass equally distant from each corner they contain, like rectangles and all regular polygons), if that matters.

Ultimately, if you are always dealing with rectangles then you would need to decide whether or not the reduced computation time is worth the extra coding and testing of whatever optimized algorithm you go with.

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.