Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Clockwise or Counter-clockwise

by stu96art (Scribe)
on Feb 19, 2003 at 04:41 UTC ( #236524=perlquestion: print w/ replies, xml ) Need Help??
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 counter-clockwise. 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 tab-curving 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.

Comment on Clockwise or Counter-clockwise
Re: Clockwise or Counter-clockwise
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 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 | +---+---+ +---+---+

      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] +);

      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.

        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

Re: Clockwise or Counter-clockwise
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 self-crossing polygons is refuted by counterexample here.

    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"; }
Re: Clockwise or Counter-clockwise
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 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";
    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

Re: Clockwise or Counter-clockwise
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!

Re: Clockwise or Counter-clockwise
by zengargoyle (Deacon) on Feb 19, 2003 at 05:57 UTC

    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.

    this is the right-hand rule, place your right hand on p1->p2 and curl your fingers onto p2->p3, 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

Re: Clockwise or Counter-clockwise
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.

      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 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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://236524]
Approved by toma
Front-paged by gmax
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2014-07-26 06:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (175 votes), past polls