SHARE

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)

Example:

$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.

SHARE