Polygonflow: clockwise or counter-clockwise?

Alex Tweedly alex at tweedly.net
Wed Feb 3 18:33:56 CST 2010


Alex Tweedly wrote:
>
> I'll post a couple of suggested solutions shortly (once I've got the 
> stack running properly)
>
There are two approaches (at least) that consistently get the same 
answers as we all intuitively "know" are correct.

By AREA.

Calculate the (signed) area between each edge and some baseline (i.e. 
the area enclosed by the edge itself, its projectino onto the baseline 
and the two projection lines). Sum this area for all edges. Looking at 
whether this is positive or negative gives an answer.

By Point.

Find the leftmost, lowest point (**). (i.e. the one with the lowest X 
value, and of all those having the same X value, the lowest Y value).
(Note that this same point (value) can occur multiple times in a 
polygon, due to self-intersection or self-overlapping polygons - this 
doesn't matter, just pick any of those points).  Looking at the previous 
and next points, determine the change of direction implied for these two 
edges (you could use the cross-product to do this, or simply normalize 
and compare the gradients).

(**) - this description assumes 'normal' cartesian coordinates. Beware 
that RunRev uses a coordinate system where the vertical axis is 
"upside-down", so increasing Y values are associated with moving downawards.

Some sample code - adopted from elsewhere (and translated into revtalk) 
- with only moderate testing, but I'm fairly confident I converted it 
fairly accurately.
(It's a bit wordy, but seemed clearer that way).
> constant kDebug  = false
> on mouseUp
>    put empty into field "F"
>    repeat with i = 1 to the number of controls
>       if char 2 to -2 of word 2 of the name of control i = "Polygon" then
>          repeat for each line L in the points of control i
>             put L & "; " after field "F"
>          end Repeat
>          put CR after field "F"
>          if calculateflowusingarea (i, kDebug) then
>             put "counterclockwise" & CR after field "F"
>          else
>             put "clockwise" & CR after field "F"
>          end if
>          if calculateflowusingpoint (i, false) then
>             put "counterclockwise" & CR after field "F"
>          else
>             put "clockwise" & CR after field "F"
>          end if
>       end if
>    end repeat
> end mouseUp
>    
> function calculateflowusingarea P, pDebug
>    put the points of control P into tPoints
>    put item 1 of line 1 of tPoints into x2
>    put item 2 of line 1 of tPoints into y2
>    put 0 into total
>    repeat for each line L in tPoints
>       put x2 into x1
>       put y2 into y1
>       put item 1 of L into x2
>       put item 2 of L into y2
>       put (x2-x1) * (0.5*(y1+y2)) into t
>       if pDebug then put (x2-x1) && (x2-x1)*0.5*(y2+y1) && x1 && y1 && 
> x2 && y2 && t & CR after field F
>       add t to total
>       put L into tLast
>    end repeat
>    
>    -- close the polygon in the case where Rev has an open polygon
>    if tLast <> line 1 of tPoints then
>       put x2 into x1
>       put y2 into y1
>       put item 1 of line 1 of tPoints into x2
>       put item 2 of line 1 of tPoints into y2
>       put (x2-x1) * (0.5*(y1+y2)) into t
>       if pDebug then put (x2-x1) && (x2-x1)*0.5*(y2+y1) && x1 && y1 && 
> x2 && y2 && t & CR after field F
>       add t to total
>    end if
>    if pDebug then put "Total is " & total & CR after field "F"
>    return total > 0   -- i.e. true if the polygon is counter-clockwise
> end calculateflowusingarea
>    
> function calculateflowusingpoint P, pDebug
>    put the points of control P into tPoints
>    -- find the leftmost, lowest point   
>    put item 1 of line 1 of tPoints into x
>    put item 2 of line 1 of tPoints into y
>    repeat with i = 1 to the number of lines in tPoints
>       if item 1 of line i of tPoints < x or \
>             (item 1 of line i of tPoints = x and item 2 of line 1 of 
> tPoints <= y) then
>          put item 1 of line i of tPoints into x
>          put item 2 of line i of tPoints into y
>          put i into tOne
>       end if
>    end repeat
>     
>    -- find the adjacent points
>    switch tOne
>       case 1
>          put the number of lines in tPoints into tPrev
>          put 2 into tNext
>          break
>       case the number of lines in tPoints
>          put tOne-1 into tPrev
>          put 1 into tNext
>          -- special case where the poly is already closed !!
>          if line tOne of tPoints = line 1 of tPoints then put 2 into tNext
>          break
>       default
>          put tOne-1 into tPrev
>          put tOne+1 into tNext
>          break
>    end switch
>    
>    if pDebug then put x && y && tPrev && tOne && tNext & CR after 
> field "F"
>    if pDebug then put line tPrev of tPoints && x && y && line tNext of 
> tPoints & CR after field "F"
>    -- now deal with the end-cases
>    if item 1 of line tPrev of tPoints = x then return false -- 
> incoming edge is vertical, so counter
>    if item 1 of line tNext of tPoints = x then return true -- outgoing ...
>    -- so can safely that x-delta's are non-zero
>    put (y-item 2 of line tPrev of tPoints) / (x-item 1 of line tPrev 
> of tPoints) into yprev    
>    put (y-item 2 of line tNext of tPoints) / (x-item 1 of line tNext 
> of tPoints) into ynext
>    if pDebug then put "ys are " && yprev && ynext & CR after field "F"
>    
>    if yprev < ynext then return true
>    return false
>    
> end calculateflowusingpoint




More information about the use-livecode mailing list