[Math] Maximize the distance between a point and a bounding rectangle

Question

There are $n$ random points in the $x-y$ plane, whose coordinates are known beforehand. We can use a minimum bounding rectangle (MBR) to bound these points. In this scenario, the MBR can be rotated, and I want to maximize the distance between a certain point $p$ (denoted by the red triangle) and the MBR.

It's clear that the distance varies with different rotation angles. For example, if we use the solid blue MBR to bound these points, then $p$ is inside this MBR, thus the distance is $0$. On the other hand, if we take the dashed green rectangle as MBR, the distance increases.

I want to know how to compute the optimal rotation angle that maximizes the distance between $p$ and the corresponding MBR, or is this possible in the first place? Since, intuitively, as the MBR rotates, those points on the boundary will also change in a rather random manner, it's hard to predict how the distance will vary.

Answer 1

First you want to find the convex hull for your set of points. That is the set of points that would be touched if you wrapped all your points with a rubber band.

In the picture I drew the convex hull points in pink, the outer green line is the "rubber band" edge.

Here are some algorithms for finding the convex hull. Hopefully you can find one already implemented. You want the planar case.

Second, you want to enumerate the possible rectangles that can be formed with the convex hull. In your example, there are 7 green line segments, so there are 7 rectangles to be considered. To find the rectangle R for a given linesegment S, you want to find the four points of the convex hull that are the furthest "up", "down", "left", and "right" relative to the rotation of S. It's a lot of trig but basically just a lot of work rather than any complicated idea. I drew arrow to the four points that make up the example rectangle.

Finally, you need to be able to compute the distance from a point to a line segment. If the edges of the line segment are points a and b , and your point is x, then:

• If angle $\angle XAB$ is obtuse, then $|XA|$ is the distance to the linesegment
• If angle $\angle XBA$ is obtuse, then $|XB|$ is the distance to the linesegment
• If both are acute, then the distance from X to the line formed by AB is the distance to calculate

To check if angle $\angle PQR$ is obtuse, use a dot product, $\angle PQR$ is obtuse iff $(P - Q) \circ (R - Q) < 0$.

Each rectangle contributes 4 line segments to check, so the final part of your problem is to compute 28 line segment distances.