1
$\begingroup$

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.

Two MBRs with different rotation angles

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.

$\endgroup$
1
$\begingroup$

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.

enter image description here

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thanks for this detailed answer, it's really helpful! $\endgroup$ – Xudong Gong Apr 21 '14 at 5:23
0
$\begingroup$

Updated: (Skipped a step.)

Compute the convex hull of the set of points. If $p$ is inside the convex hull, then all rectangles containing the points contain $p$ and the distance is zero.

The convex hull can be viewed as the intersection of several half-planes (one per boundary segment). For each of these segments whose half-plane does not include $p$, compute the (perpendicular) distance from $p$ to the extension of the segment to a line. Pick the two segments with greatest positive distance from $p$. (There can be one or two of these.) If there is one such, that segment is at the angle of the rectangle. If there are two, they are incident on one vertex and the line segment from $p$ to that point is perpendicular to the angle you want.

Why these choices at the end? If there is only one such segment, any relaxation of its associated inequality necessarily moves it closer to $p$, decreasing its distance. If there are two segments, then each can be relaxed by pivoting on the one vertex, sliding the perpendicular to $p$ along -- the length of that perpendicular is maximized when it ends at the one vertex.

$\endgroup$
  • $\begingroup$ Computing the convex hull is inspiring, thanks! $\endgroup$ – Xudong Gong Apr 21 '14 at 5:23

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.