Free Online Tutorials

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.