Free Online Tutorials

How to check if a Polygon is self-intersect?

class vertice{
    static function multiple($v1, $v2){
        return $v1[0]*$v2[0] + $v1[1]*$v2[1];
    }
    static function add($v1, $v2){
        return array($v1[0]+$v2[0] , $v1[1]+$v2[1]);
    }
    static function sub($v1, $v2){
        return array($v1[0]-$v2[0] , $v1[1]-$v2[1]);
    }
}

function SelfIntersect($polygon)
{
    $NumPoints = count($polygon);
    
    if($polygon[$NumPoints-1] == $polygon[0]){
        unset($polygon[$NumPoints-1]);
        $NumPoints--;
    }
    
    for ($i = 0; $i < $NumPoints; ++$i)
    {
        if ($i < $NumPoints - 1)
        {
            for ($h = $i + 1; $h < $NumPoints; ++$h)
            {
                // Do two vertices lie on top of one another?
                if ($polygon[$i] == $polygon[$h])
                {
                    return true;
                }
            }
        }

        $j = ($i + 1) % $NumPoints;
        $iToj = vertice::sub($polygon[$j] , $polygon[$i]);
        $iTojNormal = array($iToj[1], -$iToj[0]);
        // i is the first vertex and j is the second
        $startK = ($j + 1) % $NumPoints;
        $endK = ($i - 1 + $NumPoints) % $NumPoints;
        $endK += $startK < $endK ? 0 : $startK + 1;
        $k = $startK;
        $iTok = vertice::sub($polygon[$k], $polygon[$i]);
        $onLeftSide = (vertice::multiple($iTok, $iTojNormal) >= 0);
        $prevK = $polygon[$k];
        ++$k;
        for (; $k <= $endK; ++$k)
        {
            $modK = $k % $NumPoints;
            $iTok = vertice::sub($polygon[$modK], $polygon[$i]);
            if ($onLeftSide != vertice::multiple($iTok, $iTojNormal) >= 0)
            {
                $prevKtoK = vertice::sub($polygon[$modK], $prevK);
                $prevKtoKNormal = array($prevKtoK[1], -$prevKtoK[0]);
                if ((vertice::multiple(vertice::sub($polygon[$i], $prevK), $prevKtoKNormal) >= 0) != (vertice::multiple(vertice::sub($polygon[$j], $prevK), $prevKtoKNormal) >= 0))
                {
                    return true;
                }
            }
            $onLeftSide = (vertice::multiple($iTok, $iTojNormal) > 0);
            $prevK = $polygon[$modK];
        }
    }
    return false;
}

Example 1:

$polygon = array(
    array(0,3),
    array(4,4),
    array(3,0),
    array(4,-4),
    array(0,-3),
    array(-4,-4),
    array(-3,0),
    array(-4,4),
    //array(0,3),
);

var_dump(SelfIntersect($polygon));

Result:

bool(false)

Example 2:

$polygon = array(
    array(0,5),
    array(3,5),
    array(3,0),
    array(4,3),
    array(0,5),
);
 
var_dump(SelfIntersect($polygon));

Result:

bool(true)