C. General Algorithm for Polygon-Biasing

The situation for biasing a polygon is sketched in Figure C.1. A polygon is defined as a sequence of points which are given in a counterclockwise order by oriented segments (vectors). A general algorithm to calculate a new ``shrinked'' or ``grown'' polygon based on shifting its segments parallel by a certain amount (the bias) has to be applied. This shift is equivalent to the movement of the points of the polygon by a normal vector $\vec{e}_n$ calculated from the normal vectors of the two segments $g_{12}$ and $g_{23}$ times the bias.
This algorithm is only valid for convex polygons. For concave polygons (polygons where at least one point has an internal angle $>180^\circ$) this algorithm may fail because of point collisions or generation of loops. However, for small bias and suitable geometries the following simple algorithm is applicable.

Figure C.1: Geometrical situation when biasing a polygon with a given distance

The line segment $\vec{g}$ can be described by the general parametric line equation:

$$A x+B y+C = 0$$ (C.1)

Furthermore, the normal vector $\vec{e}_n$ is given by

$$\vec{e}_n = A \vec{x}_n + B \vec{y}_n$$ (C.2)

and thus the second equation

$$A^2 + B^2 = 1$$ (C.3)

must be fulfilled too. Substituting the start and end coordinates of the vector $\vec{g}_{12}$, $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ into (C.1) and (C.3) gives three equations which have to be solved to get the parameters $A,B$ of the line segment.

$$C + A x_1 + B y_1 = 0$$ (C.4)

$$C + A x_2 + B y_2 = 0$$ (C.5)

$$A^2 + B^2 = 1$$ (C.6)

with the solutions

$$A = \pm \frac{\vert x_1-x_2\vert (y_2-y_1)}{(x_1-x_2)\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$$ (C.7)

$$B = \pm \frac{\vert x_1-x_2\vert}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$$ (C.8)

Per definition the normal vector $\vec{e}_n$ is positive if the line segment $\vec{g}$ is rotated $90^\circ$ counterclockwise into the normal vector. This means

$$\frac{\vec{g} \times \vec{e}_n}{\vert\vec{g}\vert} > 0 \Rightarro... ...end{array} \right) > \left( \begin{array}{c} 0 0 0 \end{array} \right)$$ (C.9)

which yields the criteria

$$B \frac{x_2 - x_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}} - A \frac{y_2 - y_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}} > 0$$ (C.10)

The relation (C.11) is only fulfilled with the solution

$$A = -\frac{y_2-y_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$$ (C.11)

$$B = \frac{x_2-x_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$$ (C.12)

of the (C.8),(C.9). To determine the vector by which each point is shifted during biasing (by the distance d), the two line segments $\vec{g}_{12}$ and $\vec{g}_{23}$ attached to the point are moved parallel and thus form the new intersection point $P'_2$. The normal vectors remain the same, but the parameters $C$ of the general line equations change accordingly to the parallel shift. The initial intersection point $P_2=(x_2,y_2)$ is moved by the vector $\Delta\vec{x}_2$ to the point $P'_2=(x'_2,y'_2)$ (see Figure C.1). The parameters $C_{12},C_{23}$ of the shifted line equations are calculated from their respective line equations and the unchanged line parameters $A_{12},A_{23},B_{12},B_{23}$.

$$C_{12}=-(A_{12} x +B_{12} y + A^2_{12} d + B^2_{12})$$ (C.13)

$$C_{23}=-(A_{23} x +B_{23} y + A^2_{23} d + B^2_{23})$$ (C.14)

The new intersection point $P'_2=(x'_2,y'_2)$ must satisfy both line equations and thus by solving the equations the new intersection point coordinates yield

$$x'_2=\frac{\left( A_{23}^2 B_{12} - \left( A_{12}^2 + B_{12} \lef... ... - B_{23} \right) \right) B_{23} \right) d} {A_{23}B_{12} - A_{12}B_{23}} + x_2$$ (C.15)

$$y'_2=\frac{\left( {A_{12}}^2A_{23} + A_{23} {B_{12}}^2 - A_{12}\... ..._{23}}^2 + {B_{23}}^2 \right) \right) d} {A_{23} B_{12} - A_{12} B_{23}} + y_2$$ (C.16)

Substituting (C.12),(C.13) in (C.17),(C.18) and using the substitutions $g_{12}=\vert\vec{g}_{12}\vert$, $g_{23}=\vert\vec{g}_{23}\vert$, $\Delta x_{21}=x_2-x_1$, $\Delta x_{32}=x_3-x_2$, $\Delta y_{21}=y_2-y_1$ and $\Delta y_{32}=y_3-y_2$ gives finally

$$x'_2=\frac{d\left( -g_{23} \Delta x_{21} + g_{12} \Delta x_{32} \right) } {-x_3 \Delta y_{21} - x_1 \Delta y_{32} + x_2 \Delta y_{31} } + x_2$$ (C.17)

$$y'_2=\frac{d\left( -g_{23} \Delta y_{21} + g_{12} \Delta y_{32} \right) } {-x_3 \Delta y_{21} - x_1 \Delta y_{32} + x_2 \Delta y_{31} } + y_2$$ (C.18)