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 06:42:13 GMT

In article <1992Oct15.091759.4837@leland.Stanford.EDU> ledwards@leland.Stanford.EDU (Laurence James Edwards) writes:
>In article <1992Oct15.064957.14261@kpc.com>, hollasch@kpc.com (Steve Hollasch) writes:
>...

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-2);i++)
              if (RightTurn(P[0],P[(i+1)%n],P[(i+2)%n]) return FALSE; 
             return TRUE;

Note the bug fix - I think I have it right this time...


>|>       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.
>|>
>
>Yes, you are right. Although, with the given P0 Sloans algorithm will
>successfully flag this poly as concave in the second loop. However, if P0
>is vertex 4 or 5, in the above diagram, then it will fail.

OK let's renumber vertex 4 as vertex 0 - here's the diagram:

       5 ________ 4
         \       |        
          \   1  |
           \ /|  |
            X |  |
           / \|  |
          /   0  |
         /       |
       2 ~~~~~~~~ 3

RightTurn(0,1,2) FALSE
RightTurn(1,2,3) FALSE
RightTurn(2,3,4) FALSE
RightTurn(3,4,5) FALSE
RightTurn(4,5,0) FALSE
RightTurn(5,0,1) FALSE

and now

RightTurn(0,2,3) FALSE
RightTurn(0,3,4) FALSE
RightTurn(0,4,5) FALSE   

Hmmm, looks bad for the home team.  

Full points to Mr. Edwards for a correct correction.

Half points to Mr. Hollasch, for an almost correct correction, with 10%
off for rudeness.

Now, let's give the screw one more turn:

Consider - the method as given fails on the "Hollasch polygon" if
P[0] = 4 or 5, but succeeds for all other choices of P[0].  So...one
might ask, "What is special about vertices 4 and 5?", and "Can I avoid
this unfortunate choice?", and "Can I avoid this unfortunate choice with
O(n) cost?"

This leads to:

CONVEX(P) == ChooseSafeP0(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-2);i++)
              if (RightTurn(P[0],P[(i+1)%n],P[(i+2)%n]) return FALSE; 
             return TRUE;

Design and implementation of "ChooseSafeP0" (and the proof of
correctness) are left as this morning's exercise.  


Bonus exercise: if you still want to use sweep angles, you may want to
worry about the cost of calculating the angles exactly.  In fact, all
you need is a function which is monotonic with angle (so that
comparisons continue to give the right answer) but cheaper to implement.
The fastest such function that I know of requires one DIVIDE, plus a
small number of additions, subtractions, and comparisons.  Back when I
really cared about this, the DIVIDE was by far the most expensive part.
Can anyone do better?






-- 
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,alt.graphics.pixutils,alt.binaries.pictures.d