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?
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.
|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.
Commented
Jan 19, 2014 at 22:11
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.
