From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: Determining if a polygon is convex
Organization: CIS, University of Alabama at Birmingham
Date: Fri, 16 Oct 1992 05:17:20 GMT

In article <1992Oct15.064957.14261@kpc.com> hollasch@kpc.com (Steve Hollasch) writes:
>sloan@cis.uab.edu (Kenneth Sloan) writes:
>| 0)Assume that you have the subroutine:
>| 
>|     RightTurn(A,B,C)
>| 
>| which returns TRUE iff the path A->B->C describes a strict right turn, 
>| and returns FALSE if the path A->B->C describes a left turn, or if the
>| points are colinear.
>| 
>| 1)Assume that your polygon is represented as: P = (P[0], P[1], ..., P[n-1]).
>| 
>| 2)Assume that you know that the polygon vertices are given in
>|   counter-clockwise order (that is, convex vertices turn to the LEFT.
>|   [This assumption will be removed later, if necessary]
>| 
>| 3)CONVEX(P) == for(i=0;i<n;i++)
>|                 if (RightTurn(P[i],P[(i+1)%n],P[(i+2)%n]) return FALSE;
>|                for(i=2;i<n;i++)
>|                 if (RightTurn(P[0],P[(i+1)%n],P[(i+2)%n]) return FALSE; 
>|                return TRUE;
>| 
>| Looks O(n) to me.
>| 
>| Proof of correctness is left as an exercise.
>
>    Counterexample provided in lieu of proof.
>
>    Consider AGAIN the following polygon:
>
>      3 ________ 2      0-1 (left) 2 (left) 3 (left) 4 (left) 5 (left) 0 ...
>        \       |        
>         \   5  |       NOTE:  This polygon was included in the original
>          \ /|  |              post (over 20 articles ago).  It is a
>           X |  |              particularly NASTY polygon - it has big
>          / \|  |              wicked fangs and eats rendering weenies
>         /   4  |              like you & I for breakfast.  If your method
>        /       |              uses dot or cross products, and appears to
>      0 ~~~~~~~~ 1             be O(n), check it on this baby first.


Here's the code again, with a bug fix: (see the line marked +++, note
that this doesn't change my point, below)

 3)CONVEX(P) == for(i=0;i<n;i++)
                 if (RightTurn(P[i],P[(i+1)%n],P[(i+2)%n]) return FALSE;
+++             for(i=1;i<(n-3);i++)
***              if (RightTurn(P[0],P[(i+1)%n],P[(i+2)%n]) return FALSE; 
                return TRUE;

Note the line marked ***. 

    i      RightTurn(P[0],P[(i+1)%6],P[(i+2}%6])
   ---     -------------------------------------
    1        FALSE -> continue
    2        TRUE  -> return FALSE, this polygon is NOT CONVEX

Do you think that RightTurn(P[0],P[3],P[4]) is FALSE? 

Perhaps I'm missing something.  Can you please explain why this polygon
is a counterexample?  You very nicely pointed out that:

RightTurn(P[0],P[1],P[2]) is TRUE, and
RightTurn(P[1],P[2],P[3]) is TRUE, and
RightTurn(P[2],P[3],P[4]) is TRUE, and
RightTurn(P[3],P[4],P[5]) is TRUE, and
RightTurn(P[4],P[5],P[0]) is TRUE, and
RightTurn(P[5],P[0],P[1]) is TRUE.

but you don't report results for:    (I get)
RightTurn(P[0],P[2],P[3])            (FALSE)
RightTurn(P[0],P[3],P[4])            (TRUE)        *****
RightTurn(P[0],P[4],P[5])            (FALSE)

The result marked **** indicates that your polygon is NOT CONVEX, and my
algorithm correctly reports this.  Doesn't it?  

[One down - still waiting for Zhu to send *his* counterexample.  I hope
it's as easy as this one...]





-- 
Kenneth Sloan                   Computer and Information Sciences
sloan@cis.uab.edu               University of Alabama at Birmingham
(205) 934-2213                  115A Campbell Hall, UAB Station 
(205) 934-5473 FAX              Birmingham, AL 35294-1170
Newsgroups: comp.graphics