stu96art has asked for the wisdom of the Perl Monks concerning the following question:

I again come to ya'll for some help. I have a list of blocks, and in each list of blocks, there is a list of verticies ( these vertex make the outline of the block) and then there is a list of values (x, y, flag1, flag2, and so on). My code below goes through the list of vertex for each block, finds the greatest y-value and then compares the x-value of the next vertex with the x-value of the current vertex and if the x-value is greater than 0 then it is going in a clockwise fashion. This works great except for when the highest point is a corner, for instance the top right corner (and lets say it is going clockwise) The highest point is (120, 75) and the next point is (108, 50). My code will mark this as counterclockwise because the next x-value is less than the current x-value. My biggest question is how to distinguish this as clockwise. I hope that I did not confuse anyone. Here is a list of the x,y values and the order they are in, followed by the code I am using. My goal is to make the order of the points clockwise. <x,y> Clockwise - my code will think this is counter-clockwise and thu reverse the order (changing what is actually clockwise into counter clockwise) <10, 10> <15, 30> <45, 40> <40, 10> <10,10> Also when it is counter-clockwise, it will think that it is clockwise and not change it. <10,10> <30,10> <30,40> <5,40> <10,10> Here is the code  @blocks[$i] is the list of blocks  @blocks[$i][$j] is the list of vertex in block$i  $blocks[$i][$j][1] is the x-value  $blocks[$i][$j][2] is the y-value
my ($hij, $highest, $hv, $xclock, $right, $negx); my @backwards; # MAKE CLOCKWISE ************************************* CLK: for $i (0..$#blocks) { $highest = 0; for $j (0..$#{$blocks[$i]}) { if ($blocks[$i][$j][2] > $highest) { $highest = $blocks[$i][$j][2]; $hv = $j; $right = $blocks[$i][$j][1]; } } print "high [$i][$hv] $highest\n"; for $hij (0..$#{$blocks[$i]}) { if ($blocks[$i][$hij][2] == $highest) { if ($blocks[$i][$hij][1] > $right) { $right = $blocks[$i][$hij][1]; $hv = $hij; } } } $xclock = $blocks[$i][$hv + 1][1] - $blocks[$i][$hv - 1][1]; $negx = $blocks[$i][$hv][1] - $blocks[$i][$hv - 1]; if ($hv == $#{$blocks[$i]}) { $xclock = $blocks[$i][0][1] - $blocks[$i][$hv - 1][1]; } if ($hv == 0) { $xclock = $blocks[$i][$hv + 1][1] - $blocks[$i][$#{$blocks[$i]}][1 +]; } print "xclock $xclock block[$i] vertex[$hv]\n"; print "negx $negx\n"; if ($xclock < 0) { @backwards = reverse @{$blocks[$i]}; @{$blocks[$i]} = @backwards; print "reverse\n"; next CLK; } }

Replies are listed 'Best First'.
Re: Help with clockwise
by Abigail-II (Bishop) on Apr 25, 2003 at 23:45 UTC
    I'm not quite sure what you are asking, but I think you want to know that if you have the following:
    * C \ \ \ * B / / / / * A

    and you travel from A to C, whether at B you go "right" or "left". There's a simple formula for that.

    Let A, B and C have coordinates (xa,ya), (xb,yb), and (xc,yc).

    Then you turn "left" or "counter-clockwise" at B if, and only if, the determinant

                     
        |                 |
        | xa - xb  xc - xb |
        |                 |  =
        | ya - yb  yc - yb |
        |                 |
    
        (xa - xb) * (yc - yb) - (xc - xb) * (ya - yb)
    
    
    is negative. If it's positive, you turn "right", or "clockwise". If the result is 0, you continue in a straight line.

    Abigail

Re: Help with clockwise
by BrowserUk (Patriarch) on Apr 25, 2003 at 21:07 UTC

    Isn't this the same question you asked at Clockwise or Counter-clockwise?


    Examine what is said, not who speaks.
    1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
    2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
    3) Any sufficiently advanced technology is indistinguishable from magic.
    Arthur C. Clarke.
Re: Help with clockwise
by LogicalChaos (Beadle) on Apr 26, 2003 at 15:46 UTC
    What you are trying to do will not work for creating a path around your points. One way to create this path is to calculate the points on a convex hull. A convex hull is the set of points which encloses all points in a set. The points in your set need to be coplanar. Depending on your point layout, it's possible to create a convex hull with three side from four points, so this may not be exactly what you want.

    The graham scan algorithm to calculate a convex hull is explained here better than I can 'splain it.

    Here is the implementation I happened to have. You'll need GD if you want to see the graph

    Update - You'll notice that both Abigail-II and I use the same method for determining clockwise vs counter-clockwise.

    Cheers,
    LogicalChaos