Find closest point between 2D Point and 2D Area

Question

This is a mathematics problem with the application in computer science. Basically I have a rotated 2D box (black) and I need to find the closest point (red) on its' bounds towards a point (green) in 2D Space.

The box is defined by center (x/y) size (x,y) and rotation (y euler angles). Approximations which are performance efficient are welcome as well.

Answer 1

Ok so I have found the best way is to treat the box as 4 linear functions and calculate the closest distance between the point and each line (orthogonal function) and then take the closest one.

Answer 2

When the box is centered at the origin, and at angle $0$ (box-reference-system coincident with the basic cartesian system) then what is the red point nearest to green point $(x,y)$ is determined by a set of inequalities, easy to specify.
When the box is translated, it is not difficult to translate that set as well. Instead it is quite complicated to rotate the inequalities.
Since the translation and rotation of a point is instead much easier to achieve, I would approach your problem by :

• first applying a counter-translation and counter- rotation on the green $(x,y)$ point,
• then applying the conditions in the box reference system to find the red point as expressed in that reference,
• and finally applying to that the translation+rotation.

Answer 3

Method 1 - General Polygon Shape

Here are the steps:

1. Form each edge of the box as a line equation $A x+B y + C =0$ $$\begin{aligned} A &= y_1-y_2 \\ B & = x_2-x_1 \\ C &= x_1 y_2 - x_2 y_1 \end{aligned}$$
2. The point on the line closest to the green point $(p_x,p_y)$ is $$\begin{aligned} x &= \frac{B^2 p_x -A (B p_y+C)}{A^2+B^2} \\ y &= \frac{A^2 p_y -B (B p_x+C)}{A^2+B^2} \end{aligned} $$
3. The lever ratio $\alpha=0 \ldots 1$ describes where along the two end-points of the edge the point $(x,y)$ is $$\alpha = \frac{A (p_y-y_1) + B (x_1-p_x)}{A^2+B^2}$$
4. The distance of the point to the line is $$ d = \frac{ | A p_x + B p_y + C | }{A^2+B^2} $$
5. Repeat for all 4 edges and find the closest edge that has $0 \leq \alpha \leq 1$.

Method 2 - Rectangle

Implement Axis Aligned Bounding Box

Answer 4

First assuming that the rectangle is horizontal, the solution is found by dividing the plane in nine regions. One of the regions is the inside of the rectangle. Four are such that the closest point is on a side, and the four remaining are such that the closest point is a corner.

To obtain the projected point, it suffices to clamp the coordinates so that they don't exceed the rectangle:

$$\begin{cases}x^*=\min(\max(x,x_l),x_r),\\y^*=\min(\max(y,y_b),y_t).\end{cases}$$

This leaves the point inside the rectangle unchanged.

For a rectangle with general orientation, say at angle $\theta$, you first rotate the whole plane by $-\theta$, find the projection as above, then rotate back by $\theta$. You just have to rotate the point, as the values of $x_l,x_r,y_b,y_t$ are easy to compute from the given ($x_c\pm w/2, y_c\pm h/2$).

The formulas for rotation around the center are

$$\begin{cases}x'=C(x-x_c)-S(y-y_c)+x_c,\\ y'=S(x-x_c)+C(y-y_c)+y_c.\end{cases}$$

where $C=\cos\theta,S=\sin\theta$.

---

Just for fun, the fully developed formula:

$$\begin{cases}x^*=C\min(\max(C(x-x_c)+S(y-y_c),-\frac w2),\frac w2)\\-S\min(\max(-S(x-x_c)+C(y-y_c),-\frac h2),\frac h2)+x_c,\\ y^*=S\min(\max(C(x-x_c)+S(y-y_c),-\frac w2),\frac w2)\\ +C\min(\max(-S(x-x_c)+C(y-y_c),-\frac h2),\frac h2)+y_c. \end{cases}$$

(Of course in programming you will use intermediate variables.)