How to check if polygon is concave or convex?

/* Return whether a polygon in 2D is concave or convex return 0 if failure 1 if CONVEX -1 if CONCAVE */ function Convex($polygon) { $flag = 0; $NumPoints = count($polygon); if($polygon[$NumPoints-1] == $polygon[0]){ $NumPoints--; }else{ //Add the first point at the end of the array. $polygon[$NumPoints] = $polygon[0]; } if ($NumPoints < 3) return 0; for ($i=0;$i<$NumPoints;$i++) { $j = ($i + 1) % $NumPoints; $k = ($i + 2) % $NumPoints; $z = ($polygon[$j][0] - $polygon[$i][0]) * ($polygon[$k][1] - $polygon[$j][1]); $z -= ($polygon[$j][1] - $polygon[$i][1]) * ($polygon[$k][0] - $polygon[$j][0]); if ($z < 0) $flag |= 1; else if ($z > 0) $flag |= 2; if ($flag == 3) return -1; } if ($flag != 0) return 1; else return 0; }

Note: It is assumed that the polygon is simple (does not intersect itself or have holes)

$polygon = array( array(0,6), array(4,6), array(2,3), array(4,0), array(0,0), ); var_dump(Convex($polygon));

Result:

int(-1)

The algorithm is built on base of the cross product of 2 vectors:

We know that the cross product of 2 vectors:

\(\bigg[\overrightarrow{a},\overrightarrow{b}\bigg]=\Bigg(\begin{vmatrix}

y_{1} & z_{1} \\

y_{2} & z_{2}

\end{vmatrix};\begin{vmatrix}

z_{1} & x_{1} \\

z_{2} & x_{2}

\end{vmatrix};\begin{vmatrix}

x_{1} & y_{1} \\

x_{2} & y_{2}

\end{vmatrix}\Bigg)\)

In the special case, 2 vectors are both in the Oxy plan, we have:

\(z_{1} = z_{2} = 0;\)

So,

\(\bigg[\overrightarrow{a},\overrightarrow{b}\bigg]=\Bigg(0;0;\begin{vmatrix}

x_{1} & y_{1} \\

x_{2} & y_{2}

\end{vmatrix}\Bigg)\)

\(\Rightarrow \Bigg|\bigg[\overrightarrow{a},\overrightarrow{b}\bigg]\Bigg| = x_{1}y_{2}-x_{2}y_{1};\)

Furthermore:

\(\Bigg|\bigg[\overrightarrow{a},\overrightarrow{b}\bigg]\Bigg| = |\overrightarrow{a}|.|\overrightarrow{b}|.sin(\overrightarrow{a},\overrightarrow{b})\)

Therefore:

\(sin(\overrightarrow{a},\overrightarrow{b}) = \frac{x_{1}y_{2}-x_{2}y_{1}}{|\overrightarrow{a}|.|\overrightarrow{b}|}\)

Because of: \(|\overrightarrow{a}|.|\overrightarrow{b}| > 0\) are non-zero vectors.

## No comments yet.