stu96art has asked for the
wisdom of the Perl Monks concerning the following question:
Thanks for everyone's help on my "Inside??" question, but I think that it would be easier to be able to tell if an order of points is going clockwise or counterclockwise. My problem is that I have points on the line and a command that I use (in the final output) that will connect two points with an arc. What I need to do is make sure the arc curves inside (making an notch, not a tabcurving outward). I can do this if I can order my points in a clockwise fashion. Once again, thanks for all the help with the Inside?? problem, but if you could help me with finding out how to order the points in a clockwise manner. Thanks.
Re: Clockwise or Counterclockwise
by Zaxo (Archbishop) on Feb 19, 2003 at 05:20 UTC

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 xy 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";
That is not reliable unless the figure is convex. A banana shaped figure will have different sign at different vertices.
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  [reply] [d/l] 
Re: Clockwise or Counterclockwise
by tall_man (Parson) on Feb 19, 2003 at 05:12 UTC

There is a simple polygon area computation that comes out negative if the polygon is clockwise and positive if it is counterclockwise. Here is some perl code that computed it for a polygon object I wrote (not included).
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;
}
Update2: My assertion that it will work for selfcrossing polygons is refuted by counterexample
here.
Update:It will work even for concave and selfcrossing polygons. But because the test does not work for colinear points and other zeroarea polygons, I use it like this:
my $EPSILON = 1e20;
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";
}
 [reply] [d/l] [select] 
Re: Clockwise or Counterclockwise
by BrowserUk (Pope) on Feb 19, 2003 at 08:51 UTC

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';
Examine what is said, not who speaks.
The 7th Rule of perl club is  pearl clubs are easily damaged. Use a diamond club instead.  [reply] [d/l] 

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";
I tested a selfcrossing unit "cube" in the input instead of a straight one, and got the result "0". This refutes my idea that selfcrossing polygons will work with this algorithm.  [reply] [d/l] 
Re: Clockwise or Counterclockwise
by toma (Vicar) on Feb 19, 2003 at 05:08 UTC

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.
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 welltested algorithms. Even then, lots of
testing is required, and many times problems will
be found later.
To evaluate clockwise and counterclockwise,
take a look at the atan2 function.
It should work perfectly the first time!  toma  [reply] 

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 
+++ +++
No circles, or radii, but most people would recognise the first as being "numbered clockwise from top left" and the second as "numbered anitclockwise 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]
+);
which given the limitations of the medium looks something like this.
 /\
/ /
\ \/\
 \ /
 \/
+
Examine what is said, not who speaks.
The 7th Rule of perl club is  pearl clubs are easily damaged. Use a diamond club instead.  [reply] [d/l] [select] 

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
 [reply] 
Re: Clockwise or Counterclockwise
by FoxtrotUniform (Prior) on Feb 19, 2003 at 05:35 UTC

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?
}
}
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!
 [reply] [d/l] [select] 
Re: Clockwise or Counterclockwise
by zengargoyle (Deacon) on Feb 19, 2003 at 05:57 UTC

Given 3 2d noncolinear points in sequence, create the 3d vectors v_{1} = p_{1}>p_{2} and v_{2} = p_{1}>p_{3} on the z_{0} plane. calculate v_{3} = v_{1} X v_{2}. if v_{3} has positive z then they are in counterclockwise order, negative z then clockwise.
this is the righthand rule, place your right hand on
p_{1}>p_{2} and curl your fingers onto p_{2}>p_{3}, 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...
 [reply] 

Given 3 2d noncolinear 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 counterclockwise 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 bananashaped 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!
 [reply] 

 [reply] 



