How to get a rectangle around a polygon?

Question

I have a polygon with all coordinates known. I want to draw a rectangle around it making $(x_1,y_1)$ and $(x_2,y_2)$ as it's base. How can I get new coordinates forming rectangle around polygon?

(x1,y1) = (8.375, 127.5258)
(x2,y2) = (26.1326, 127.5258)   
(x3,y3) = (26.375,  130.5258)   
(x4,y4) = (23.6995, 141.2277)   
(x5,y5) = (8.375,   137.3966)

Answer 1

I will denote $v_{ij}=\begin{bmatrix} x_j \\ y_j \end{bmatrix} - \begin{bmatrix} x_i \\ y_i \end{bmatrix}$, that is the vector from $i$-point to $j$-point.

$$ \begin{bmatrix} x_2 \\ y_2 \end{bmatrix} +\frac{v_{12} \cdot v_{23}}{\Vert{v_{12}}\Vert} \Big(\frac{v_{12}}{{\Vert{v_{12}}\Vert}}\Big) = \text{ coordinates of lower-right vertex}. $$

$$ \begin{bmatrix} x_1 \\ y_1 \end{bmatrix} +\frac{v_{12} \cdot v_{15}}{\Vert{v_{12}}\Vert} \Big(\frac{v_{12}}{{\Vert{v_{12}}\Vert}}\Big)= \text{ coordinates of lower-left vertex}. $$

$$ \begin{bmatrix} x_4 \\ y_4 \end{bmatrix} +\frac{v_{12} \cdot v_{43}}{\Vert{v_{12}}\Vert}\Big(\frac{v_{12}}{{\Vert{v_{12}}\Vert}}\Big) = \text{ coordinates of upper-right vertex}. $$

$$ \begin{bmatrix} x_4 \\ y_4 \end{bmatrix} +\frac{v_{12} \cdot v_{45}}{\Vert{v_{12}}\Vert} \Big(\frac{v_{12}}{{\Vert{v_{12}}\Vert}}\Big)= \text{ coordinates of upper-left vertex}. $$

Fractions like $\frac{v_{12} \cdot v_{45}}{\Vert{v_{12}}\Vert}$ are the projections of sides of the polygon onto the direction of the base, while $\Big(\frac{v_{12}}{{\Vert{v_{12}}\Vert}}\Big)$ is a unit vector of the base direction.

Answer 2

Rotate the figure by angle $-\arctan\dfrac{y_2-y_1}{x_2-x_1}$ so that the side $12$ becomes horizontal, and determine the axis-aligned bounding box (which is trivial).

Then rotate the four corners back in place (if needed).

Answer 3

This can be done by fixing the direction of a side of the rectangle in any way (it need not be one of the sides of the polygon).

So let $(x_1, y_1), ..., (x_n, y_n)$ be the vertices of the polygon, and let $(a,b)$ be a vector which is parallel to a side of the desired rectangle.

You need to find the line equation of the sides of the rectangle. As $(a,b)$ is a normal to two of them and parallel to the other two, two of the line equations have the form:

$$ax+by+c=0$$

and the other two have the form:

$$bx-ay+c=0$$.

I show you how to find the first two, the other two is analogous ($c$ is the unknown). Let $\ell$ be the line that consists of the endpoints of the multiples of the vector $(a,b)$. So $\ell$ consists of the points $(at, bt)$, $t\in \mathbb{R}$.

So we are looking for two line equations of the form $ax+by+c=0$, with $c$ being unknown. By altering $c$, we are shifting a line perpendicular to the vector $(a,b)$. The projection of the polygon to the line $\ell$ is a segment, and the extreme positions where the shifted line touches the polygon are those vertices of the polygon whose projection to $\ell$ are the endpoints of this segment. So you are looking for the vertices $(x_i, y_i)$ such that the projection of $(x_i, y_i)$ to $\ell$ are "leftmost" and "rightmost" on $\ell$, that is, $ax_i+by_i$ are minimal or maximal. (The projections to $\ell$ are the points corresponding to the scalar product if you view $\ell$ as the real line.) So find i such that $ax_i+by_i$ is minimal, and let this minimum be $c_1$. Also find i such that $ax_i+by_i$ is maximal, and let this maximum be $c_2$. Then the two line equations we were looking for are $ax+by-c_1=0$ and $ax+by-c_2=0$.