From: zhu@sgi.com (Benjamin Zhu)
Newsgroups: comp.graphics
Subject: Re: Determining if a polygon is convex
Date: 14 Oct 1992 17:35:09 GMT
Organization: Silicon Graphics, Inc.
Distribution: world
NNTP-Posting-Host: graphack.asd.sgi.com

I will not give more arguments to prove the correctness of my algorithms.
Reuel has pretty much shown they are correct in examples Steve gave. Any-
body who are into proofs might want prove them himself/herself.

In article <1bhfu0INN617@fido.asd.sgi.com> reuel@blivet.houst.sgi.com (Reuel Nash) writes:
>
>In article <1992Oct14.051459.5967@kpc.com>, hollasch@kpc.com (Steve
>Hollasch) writes:
>|> fred@kpc.com (Fred Fisher) writes:
>|> > Does anyone know a nice quick way to determine if a polygon is convex?
>|> 
>|> zhu@sgi.com (Benjamin Zhu) writes:
>|> | 
>|> | Here are two relatively straightforward solutions off my head.
>|> | 
>|> | (1) Throw away vertex ordering, and compute the convex hull of
>|> |     these vertices. If the computed convex hull is identical to the
>|> |     original polygon, the old polygon is convex. Otherwise, not!
>|> 
>|>                                                 0 _____ 3
>|>                                                   \   /
>|>                                                    \ /
>|>     This fails for a bow-tie polygon, i.e.:         X
>|>                                                    / \
>|>                                                   /   \
>|>                                                 2 ~~~~~ 1
>|> 
>
>Does Not!
>
>The bow-tie polygon is given as 0123; the convex hull would have
>to be given as 0312, which is NOT 0123.
>

	Well said here. The connectivity between vertices is the key.

>Of course, your algorithm would have to be able to figure out that
>0312 == 3120 == 1203 == ...
>

	The trick here is for each point in the 2D convex hull algorithm
	to store a pointer to the original vertex. After computing the
	convex hull, you artificially pick a point from the hull as your
	starting point, and find its counter part in the original polygon.
	Walk along the edges of the hull and the polygon, and compare
	subsequent pairs of vertices. If any pair is different, not
	convex polygon! Notice that the second vertex next to the starting
	vertex is significant in determining which direction for traversal.
	Clearly, the work for comparison of the hull and the original
	polygon is merely O(n). O(n*ln(n)) is needed for the convex hull
	computation.


>|> | (2) Walk along the edges. See if every other vertex lies at the
>|> |     same side of current edge. If so, convex. Otherwise, not!
>|> 
>|>     This fails for the following polygon:
>|> 
>|>                3 ________ 2
>|>                  \       |         Another way to think of this rule
>|>                   \   5  |         is that you're always making a left
>|>                    \ /|  |         turn to get to the next vertex.
>|>                     X |  |         It's the self-intersection that
>|>                    / \|  |         screws us up here.
>|>                   /   4  |
>|>                  /       |
>|>                0 ~~~~~~~~ 1
>|> 
>
>Does not!
>
>the test is:	(note the word "every" above)
>for each edge
>	are ALL the other vertices on the same side of this edge?
>
>edge 01: yes (all to left)
>edge 12: yes (all to left)
>edge 23: yes (all to left)
>edge 34: no (0 to right, others to left) -> not convex
>

	Again, well said.

>This algorithm sounds like O(n^2) to me. 
>

	This is indeed O(n^2).

>Do you really have to know if it's convex? 
>For many scan conversion algorithms, monotonic on one axis will suffice.
>

	My naughty guess is that it is for polygon decomposition in
	OpenGL or an extention to OpenGL. I do not remember OpenGL asks
	to handle complex polygons.

>Reuel Nash	(713)293-9292	FAX (713)293-0503
>Silicon Graphics, 11490 Westheimer Suite 100, Houston, TX  77077
>
>Visualize Whirled Peas


--
Benjamin Zhu             ;;; Priest of ucode and self-appointed bug terminator
Silicon Graphics, Inc.   ;;; ``Just call my name, I will be there.''
zhu@graphack.asd.sgi.com ;;; ``Projective geometry is all geometry.'' - Cayley
(415) 390-1187           ;;; ``Learn forever, young forever.'' - Anonymous
Newsgroups: comp.graphics