Geometric Primitives - 3D Math Primer for Graphics and Game Development - page 337

interior angle, meaning they sum to 360 o . (It's not the same as the “turn
angle,” and you might notice that the definition of exterior angle for polygon
vertices is different from the classic one used for triangle vertices.) So, if
we take the sum of the smaller angle (interior or exterior) at each vertex,
then the sum will be (n − 2)180 o for convex polygons, and less than that if
the polygon is concave.

Listing 9.7 shows how to determine if a polygon is convex by summing
the angles.

bool i s P o l y g o n C o n v e x (

i n t

n , / / Number o f v e r t i c e s

c o n s t V e c t o r 3 v l [ ] , / / p o i n t e r t o a r r a y o f o f v e r t i c e s

) {

/ / I n i t i a l i z e sum t o 0 r a d i a n s

f l o a t angleSum = 0 . 0 f ;

/ / Go around t h e polygon and sum t h e a n g l e a t each v e r t e x

f o r ( i n t i = 0 ; i < n ; ++ i ) {

/ / Get edge v e c t o r s . We have t o be c a r e f u l on

/ / t h e f i r s t and l a s t v e r t i c e s . Also , n o t e t h a t

/ / t h i s c o u l d be o p t i m i z e d c o n s i d e r a b l y

V e c t o r 3 e1 ;

i f ( i == 0 ) {

e1 = v l [ n − 1] − v l [ i ] ;

} e l s e {

e1 = v l [ i − 1] − v l [ i ] ;

}

V e c t o r 3 e2 ;

i f ( i == n − 1) {

e2 = v l [ 0 ] − v l [ i ] ;

} e l s e {

e2 = v l [ i + 1 ] − v l [ i ] ;

}

/ / Normalize and compute d o t p r o d u c t

e1 . n o r m a l i z e ( ) ;
e2 . n o r m a l i z e ( ) ;
f l o a t

d o t = e1 ∗ e2 ;

/ / Compute s m a l l e r a n g l e u s i n g ' ' s a f e ' ' f u n c t i o n t h a t p r o t e c t s

/ / a g a i n s t r a n g e e r r o r s which c o u l d be caused by

/ / n u m e r i c a l i m p r e c i s i o n

f l o a t t h e t a = s a f e A c o s ( d o t ) ;

/ / Sum i t up

angleSum += t h e t a ;

}

/ / F i g u r e o u t what t h e sum o f t h e a n g l e s s h o u l d be , a s su m i n g

/ / we a r e convex . Remember t h a t p i r a d = 180 d e g r e e s

f l o a t convexAngleSum = ( f l o a t ) ( n − 2 ) ∗ k P i ;

/ / Now, check i f t h e sum o f t h e a n g l e s i s l e s s t h a n i t s h o u l d be ,

/ / t h e n we ' r e concave . We g i v e a s l i g h t t o l e r a n c e f o r

/ / n u m e r i c a l i m p r e c i s i o n

i f ( angleSum < convexAngleSum − ( f l o a t ) n ∗ 0 . 0 0 0 1 f ) {