Vertex ordering on concave polygons

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Vertex ordering on concave polygons

Post 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;
}
Last edited by josh on Tue Nov 04, 2008 7:35 pm, edited 1 time in total.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

I wonder what you're working on 8O Didn't you post some other geometrical stuff a while back? :D
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Post by onion2k »

Hmm.. that could come in quite handy actually.
Post Reply