Offset polygon lines in the opposite direction of the polygon (inflation)

Question

Let's say a convex polygon is given as a set of coordinates. We need to offset all the lines (to which edges belong) by $h$ in the direction of their perpendicular lines and in the opposite direction of the polygon.

More simply put, the polygon should be sort of inflated. If one of the lines given satisfies the equation $y=kx+b_1$ then we just need to find the coordinate $b_2$ for the shifted line using the formula $ |b_2-b_1|=h\sqrt{k^2+1}$.

I am not sure how to choose the right direction. I know that we can check the orientation of a point relative to a line but in this case, I need to make sure that the new line moved away from all the polygon points.

Thanks in advance!

Answer 1

You know that you are convex, so you can find points inside your polygon. I have no paper to check, but I believe that the center, ie. mean of the vertices of your polygon, should be a viable candidate. Then you can formalize inside and outside as at the same resp. opposite side of the boundary with respect to the center.

I wonder, whether you can solve this problem by choosing a specific point and scaling the polygon up (using the point as center of scaling).

Answer 2

Usually we save the polygon's points ($\mathbf{p}_{ix}, \mathbf{p}_{iy}$) in clockwise (or anti-clockwise ) order. The signed area tells whether it is clockwise:

$ a=\frac{1}{2}\sum_{i=0}^n (\mathbf{p}_{ix} \mathbf{p}_{jy} -\mathbf{p}_{jx} \mathbf{p}_{iy}), \quad j=(i+1)\%n$

Go through every edge to obtain the normalized direction: $$ \mathbf{v}_i=\frac{\mathbf{p}_j - \mathbf{p}_i }{|\mathbf{p}_j - \mathbf{p}_i|} $$ where $j=(i+1)\%n$

there are two vectors orthogonal $\mathbf{v}$: $$ \begin{bmatrix} -\mathbf{v}_{iy}\\ \mathbf{v}_{ix} \end {bmatrix} $$ and $$ \begin{bmatrix} \mathbf{v}_{iy}\\ -\mathbf{v}_{ix} \end {bmatrix} $$ both are marked in green in the figure. Your question is which one inflate the polygon, you may used the signed area: $$ sgn(a) L \begin{bmatrix} -\mathbf{v}_{iy}\\ \mathbf{v}_{ix} \end {bmatrix} $$ to ensure the direction of offset is desirable. $L$ is the distance you want to offset.

Finally one needs to computer the intersection points of the offset lines, a fast and robust algorithm can be find in Schneider's Geometric Tools for Computer Graphics (an underestimated masterpiece in my opinion). One should avoid using division (if possible) which may cause numerical exceptions.

Anyway, you are lucky to have a convex.