Page 1 of 1

Vertex ordering on concave polygons

Posted: Thu Dec 08, 2005 8:40 pm
by josh
Should work :wink:

Code: Select all

 
$polygon = array(
 
    array(
 
        "x" => 1,
        "y" => 1
 
    ),
 
    array(
 
        "x" => 5,
        "y" => 1
 
    ),
    
    array(
        
        "x" => 5,
        "y" => 5
    
    ),
    
    
    array(
    
        "x" => 1,
        "y" => 5
    
    ),
    
    array(
    
        "x" => 1,
        "y" => 1
    
    )
 
);
 
function direction($polygon) {
   /*************************
   If the area of an arbitrary
   non-self-intersecting closed
   polygon is positive the points
   were ordered in a non clockwise
   fashion, respectively clockwise
   polygons have negative areas.
   This is why the area algorithm usually
   returns absolute values.   
   *************************/
   
   $area = 0;
   $n = count($polygon)-1;
   
   for ($i=0;$i<$n;$i++) {
      $j = ($i + 1);
      $area += $polygon[$i]['x'] * $polygon[$j]['y'];
      $area -= $polygon[$i]['y'] * $polygon[$j]['x'];
   }
 
   $area /= 2;
   if ($area==0) {
       return(false);
   } elseif ($area > 0) {
       return(1);
   } elseif ($area < 0) {
       return(2);
   }
}
 
 
switch (direction($polygon) ) {
 
    case false:
        echo 'Your polygon foobar\'d';
    break;
    
    case 2:
        echo 'CW';
    break;
    
    case 1:
        echo 'CCW';
    break;
}

Posted: Fri Dec 09, 2005 10:51 am
by Chris Corbyn
I wonder what you're working on 8O Didn't you post some other geometrical stuff a while back? :D

Posted: Fri Dec 09, 2005 11:06 am
by onion2k
Hmm.. that could come in quite handy actually.