What assumptions can you make about the collection of vertices? Is the geometric figure always convex? Can edges cross?

The vector cross product of a pair of successive edges in the x-y plane will be negative if the lines break right (clockwise), positive if they break left (counterclockwise). Given vertices at ($x1,$y1), ($x2,$y2), and ($x3,$y3),

my ($dx1, $dy1) = ($x2 - $x1, $y2 - $y1);
my ($dx2, $dy2) = ($x3 - $x2, $y3 - $y2);
my $cross = $dx1*$dy2 - $dy1*$dx2;
print $cross < 0
      ? "clockwise"
      :   $cross == 0
          ? "collinear"
          : "counterclockwise";
[download]

The numeric tags on those variables look like a shout for arrays, but they are just labels. The natural place to use arrays here is to group x and y for each vertex.

After Compline,
Zaxo

sub GreenTheoremTest {
   my ($poly) = @_;
   my $n = $poly->getSize;
   my $i;
   my $asum = 0.0;
   for ($i = 0; $i < $n; $i++) {
      my $i1 = ($i + 1) % $n;
      my $x = $poly->getPoint($i)->x;
      my $y = $poly->getPoint($i)->y;
      my $x1 = $poly->getPoint($i1)->x;
      my $y1 = $poly->getPoint($i1)->y;
      $asum += $x*$y1 - $x1*$y;
   }
   return $asum;
}
[download]

Update:It will work even for concave and self-crossing polygons. But because the test does not work for colinear points and other zero-area polygons, I use it like this:

my $EPSILON = 1e-20;
my $asum = GreenTheoremTest($poly);
if (abs($asum) < $EPSILON) {
   print "Polygon area is too small to be sure of direction!\n";
} elsif ($asum < 0.0) {
   print "Polygon is clockwise\n";
} else {
   print "Polygon is counterclockwise\n";
}
[download]

sub direction{
     local $_;
     push @_, $_[0];
     $_ += $a->[0] * $b->[1] 
         - $a->[1] * $b->[0] 
           while ($a,$b)=(shift,$_[0]), @_;
     $_ < 0;
}
my @unitCubeAnti = ([0,0],[0,1],[1,1],[1,0]);
print direction(@unitCubeAnti) ? 'Anticlockwise' : 'Clockwise';
my @unitCubeClock = reverse @unitCubeAnti;
print direction(@unitCubeClock) ? 'Anticlockwise' : 'Clockwise';
[download]

Your example will not run as given because it destroys the @unitCubeAnti within the direction subroutine. I suggest copying the input list to a local variable first:

sub direction{
     local $_;
     my (@poly) = @_;
     push @poly, $poly[0];
     $_ += $a->[0] * $b->[1] 
         - $a->[1] * $b->[0] 
           while ($a,$b)=(shift @poly,$poly[0]), @poly;
     print "result is $_\n";
     $_ < 0;
}
my @unitCubeAnti = ([0,1],[1,1],[0,0],[1,0]);
print direction(@unitCubeAnti) ? 'Anticlockwise' : 'Clockwise';
print "\n";
my @unitCubeClock = reverse @unitCubeAnti;
print direction(@unitCubeClock) ? 'Anticlockwise' : 'Clockwise';
print "\n";
[download]

I tested a self-crossing unit "cube" in the input instead of a straight one, and got the result "0". This refutes my idea that self-crossing polygons will work with this algorithm.

Two points could be (X1,Y1) and (X2,Y2). There are a *lot* of possible circles that can go through these two points. You need some more information.

Doing geometry with numbers is called "Computational Geometry". It is a challenging but fun kind of programming and is often the source of many bugs in ordinary applications. For example, say you decide to use a third point to help define your circle and compute a radius. If all the points lie on a straight line, the radius will be infinite. So you will need some extra code to check for this.

Since so many problems are often found in geometric code, many people strive to use only the most well-tested algorithms. Even then, lots of testing is required, and many times problems will be found later.

To evaluate clockwise and counter-clockwise, take a look at the atan2 function.

It should work perfectly the first time! - toma

To have a concept of clockwise, there needs to be a circle somewhere. The circle needs a center and a radius. The center needs two points, call them X and Y. Call the radius R. So somehow you need three values, X, Y and R.

+---+---+    +---+---+
| 1 | 2 |    | 1 | 4 |
+---+---+    +---+---+
| 4 | 3 |    | 2 | 3 |
+---+---+    +---+---+
[download]

No circles, or radii, but most people would recognise the first as being "numbered clockwise from top left" and the second as "numbered anit-clockwise from top left".

Likewise these two sets of points describe the same irregular polyon

my @clockwise = ( [0,3],[3,0],[5,2],[4,3],[3,2],[2,3],[3,4],[2,5] );
my @anticlockwise = ( [2,5],[3,4],[2,3],[3,2],[4,3],[5,2],[3,0],[0,3] 
+);
[download]

which given the limitations of the medium looks something like this.

 | /\
 |/ /
 |\ \/\
 | \  /
 |  \/
-+------
[download]

---

Examine what is said, not who speaks.

The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.

There's still a circle in your examples. The center is in the middle, where your squares meet. The radius is arbitrary so long as you can establish a direction around your center.

My point is that even though the objects of interest might not comprise a circle (they could be scattered marbles, for example), a circle is still used to determine their relative positions -- therefore clockwise/counterclockwise orientations.

This is a subjective projection of the circle. If you run the same problem while looking up from underneath your grid you will get different answers -- or looking at your grid sideways, for that matter. :)

Update: Just to clarify a bit. What we're really talking about is angular motion around an axis. A circle is just the projection straight down this axis.

Matt

If your polygon is convex (which, IIRC, it isn't -- that would be too easy), you could just test two adjacent edges: if they form a left turn, you're going counterclockwise, if a right turn, you're going clockwise.

Here's a completely untested idea: take the vertex with the highest y coordinate in your data set. It has to be on the convex hull, right? Then it won't be part of a concave section (although one of its adjacent edges may be), and you can test the orientation of its adjacent edges to determine whether the polygon's going clockwise or counterclockwise. In (admittedly vague) code:

sub is_clockwise
{
  # $verts and $edges are arrayrefs
  my ($verts, $edges) = @_;

  my @sorted  = sort {$a->{y} > $b->{y}} @$verts;
  my $highest = $sorted->[0];

  my ($edge_1, $edge_2) = &get_adjacent($edges, $highest);

  if(&right_turn($edge_1, $edge_2)) {
    return true; # clockwise!
  } else {
    return false; # counterclockwise?
  }
}
[download]

This code breaks if $edge_1 and $edge_2 are collinear; it will return false (they don't form a right turn), whereas you don't really know anything about the polygon's orientation. That should be pretty straightforward to fix, though. I'll let you do it. :-)

As far as a proof of correctness goes, I don't really have one. :-( Provided that the only way the orientation test can screw up is if you do it on a concave section, it should be fairly obvious: the two edges on the highest point (or any guaranteed exterior point) are goinig to be relatively convex (they'll have the same arc as the convex hull) to the polygon, and once you have that you're golden. But if the orientation test fails in other circumstances, I dunno....

At any rate, it's cheap and easy to implement, so if it's broken you probably won't have lost that much time. :-)

--
F o x t r o t U n i f o r m
Found a typo in this node? /msg me
The hell with paco, vote for Erudil!

Given 3 2d non-colinear points in sequence, create the 3d vectors v₁ = p₁->p₂ and v₂ = p₁->p₃ on the z₀ plane. calculate v₃ = v₁ X v₂. if v₃ has positive z then they are in counter-clockwise order, negative z then clockwise.

this is the right-hand rule, place your right hand on p₁->p₂ and curl your fingers onto p₂->p₃, if your thumb points up they go counter clockwise, if it points down they go clockwise.

i really need to look for an HTML equation editor...

Given 3 2d non-colinear points in sequence, create the 3d vectors v1 = p1->p2 and v2 = p1->p3 on the z0 plane. calculate v3 = v1 X v2. if v3 has positive z then they are in counter-clockwise order, negative z then clockwise.

That only works if the polygon in question is convex, otherwise local orientation says nothing about the polygon's orientation (unless you pick your locale cleverly, of course).

Take the example of a banana-shaped counterclockwise polygon: the interior section will have a "clockwise" orientation.

--
F o x t r o t U n i f o r m
Found a typo in this node? /msg me
The hell with paco, vote for Erudil!

Given 3 2d non-colinear points in sequence there's no such thing as convex or concave. (that's why i didn't go with 3 or more...) =P