PHP: How to check if the vertices of polygon are in clockwise or counter-clockwise order?


How to check if the vertices of polygon are in clockwise or counter-clockwise order?

There are many of method to check this. We offer some method below:

Method 1: Use ComputeArea function:

//true if counter-clockwise, false if clockwise
function CCW($polygon){
    $area = ComputeArea($polygon);
    return $area>0;
}

Method 2:

/* 
return 0 if failure
       1 if CCW
       -1 if CW
*/
function CCW2($polygon)
{
    $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;
    
    $count = 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)
            $count--;
        else if ($z > 0)
            $count++;
    }
    if ($count > 0)
        return 1;
    else if ($count < 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(CCW2($polygon));

Result:

int(-1)

Related Post

, , ,

No comments yet.

Leave a Reply