From: fred@kpc.com (Fred Fisher)
Subject: Determining if a polygon is convex
Summary: Here's one method, does anyone know of a better one?
Keywords: polygon, convex, area
Organization: Kubota Pacific Inc., Santa Clara, CA
Date: Tue, 13 Oct 1992 23:29:36 GMT

Hello,

Does anyone know a nice quick way to determine if a polygon is convex?

I've come up with the following, however it seems like there should be 
a better way...

The basic idea is to use the polygon vertices to form triangles in three 
different ways, and see if any of the triangles "face" the other way. At the
time when I'd like to determine if the polygon is convex or not, I've
already projected the polygon onto the plane which produces the largest
shadow (largest cross product), so it's a 2D problem at this point.

Each pass can easily be combined for efficiency, although I'll describe each
pass seperately for clarity. To describe the algorithm, I'll define the
"area" of triangle ABC as 'vector AB' cross 'vector AC'. Even though this is
actually twice the area, I'm only interested in the sign of the result.
more specifically:
	V1x = Bx - Ax	V2x = Cx - Ax
	V1y = By - Ay	V2y = Cy - Ay
	"area" = V1x * V2y  -  V1y * V2x

Given a set of vertices (call them 0, 1, 2, 3, ....)

pass 1:
	consider triangles by moving 3 points along the list of polygon 
	vertices:
		triangles: 012 123 234 345 ...
	if any signs are different, the polygon is not convex.
	if all area signs are the same, proceed to pass two.

	pass 1 catches simple concave cases like this:
	              4  	      2
		      | .	  .   |
		      |	 .    .       |
		      |	  3  	      |
		      |		      |
		      |		      |
		      0 ------------- 1

	this case would not be caught by the other two passes.

pass 2:
	consider triangles by keeping one vertex constant, and moving the
	other two along the list of polygon vertices:
		i.e. triangles: 012 023 034 045 ...
	if any signs are different, the polygon is not convex.
	if all area signs are the same, proceed to pass three.

	pass 2 catches self-intersecting cases like this:
	   
	  		0
              
	  	2               3
	 	           		    
	 	             
	  
	  	    4 	    1
	   
	or this:

	                3 ------------- 2
	                 \              |
	  		  \   6         |
	  	           \	\	|
	  	            \	  5     |
	  		     \  /       |
	  		      4         |
	  				|
	  		0 ------------- 1

	As specified, pass 2 would find the areas of 012 023 the same sign.
	However, the area of 034 would be different.
	Neither pass 1 or 3 would catch this case.

pass 3:
	consider triangles by keeping two vertices constant, and moving the
	other one along the list of polygon vertices:
		i.e. triangles: 012 013 014 015 016 ...
	if any signs are different, the polygon is not convex.
	if all area signs are the same, then the polygon is convex.

	pass 3 catches self-intersecting cases like the following. This looks
	similar to the one above, but the vertex numbers are different.
	Unless you could reliably determine a good starting vertex, the
	complete algorithm must not assume anything about where the vertices
	start.

	                4 ------------- 3
	                 \              |
	  		  \   0         |
	  	           \	\	|
	  	            \	  6     |
	  		     \  /       |
	  		      5         |
	  				|
	  		1 ------------- 2


	Pass 1 would not catch this because triangles 012 123 234 345 456 are 
	all CCW.

	Pass 2 would not catch this because triangles 012 023 034 045 056 are 
	all CCW.

regards,

Fred Fisher
fred@kpc.com