IsConvex() ,PolygonArea() for Polygons

Monkey Forums/Monkey Code/IsConvex() ,PolygonArea() for Polygons

Difference

(Posted 2011) [#1]

An answer to http://www.monkeycoder.co.nz/Community/posts.php?topic=1657

Strict

' assume pointCount > 3 and not odd array length
Function IsConvex:Bool(points:Float[])
		
	Local winding:Int = Sgn(PolygonArea(points)) ' determine winding , positive area means clockwise
	
	Local pointCount:Int = points.Length()
	
	Local i2:Int = 2
	Local i3:Int = 4
	
	For Local i1:Int = 0 Until pointCount Step 2
	
		'Print i1 + " ,  " + i2 + " , " + i3
	
		Local tri:Float[6]
		
		tri[0] = points[i1]
		tri[1] = points[i1+1]
		tri[2] = points[i2]
		tri[3] = points[i2+1]				
		tri[4] = points[i3]
		tri[5] = points[i3+1]				
		

		If Sgn(PolygonArea(tri))<>winding ' compare triangle winding
			Return False
		Endif
		
		i2+=2
		If i2 = pointCount Then i2 = 0

		i3+=2
		If i3 = pointCount Then i3 = 0
		
	Next
				
	Return True
	
End Function	
	
Function PolygonArea:Float(polyPoints:Float[])

	Local accum:Float
	Local  j:Int = polyPoints.Length()-2

	For Local i:Int =0 Until polyPoints.Length() Step 2
		accum += polyPoints[j] * polyPoints[i+1] - polyPoints[i] * polyPoints[j+1]
    		j=i 
	Next

	Return accum / 2

End Function



Function Main:Int()

	Local points:Float[8]

	points[0] =  0
	points[1] =  0
	
	points[2] =  100
	points[3] =  0

	points[4] =  100  ' 40 for concave
 	points[5] =  100	' 40 for concave
	
	points[6] =  0
	points[7] =  100		

	If IsConvex(points)
		Print "Convex"
	Else
		Print "Concave"	
	Endif

	Return 0
End Function

[EDIT] Version with slightly more elegant point enumeration

Strict

' assume pointCount > 3 and not odd array length
Function IsConvex:Bool(points:Float[])
		
	Local winding:Int = Sgn(PolygonArea(points)) ' determine winding , positive area means clockwise
	
	Local pointCount:Int = points.Length()
	
	Local a:Int = pointCount - 4
	Local b:Int = pointCount - 2
	
	
	For Local c:Int = 0 Until pointCount Step 2
	
		'Print a + " ,  " + b + " , " + c
	
		Local tri:Float[6]
		
		tri[0] = points[a]
		tri[1] = points[a+1]
		tri[2] = points[b]
		tri[3] = points[b+1]				
		tri[4] = points[c]
		tri[5] = points[c+1]				
		

		If Sgn(PolygonArea(tri))<>winding ' compare triangle winding
			Return False
		Endif
		
		a=b
		b=c

	Next
				
	Return True
	
End Function	
	
Function PolygonArea:Float(polyPoints:Float[])

	Local accum:Float
	Local  j:Int = polyPoints.Length()-2

	For Local i:Int =0 Until polyPoints.Length() Step 2
		accum += polyPoints[j] * polyPoints[i+1] - polyPoints[i] * polyPoints[j+1]
    		j=i 
	Next

	Return accum / 2

End Function



Function Main:Int()

	Local points:Float[8]

	points[0] =  0
	points[1] =  0
	
	points[2] =  100
	points[3] =  0

	points[4] =  100   '40 for concave
 	points[5] =  100   '40 for concave
	
	points[6] =  0
	points[7] =  100		

	If IsConvex(points)
		Print "Convex"
	Else
		Print "Concave"	
	Endif

	Return 0
End Function

hardcoal

(Posted 2011) [#2]

great work

impixi

(Posted 2011) [#3]

Here's a function to calculate a polygon's centroid (makes use of your PolygonArea function):

'Get the centre point of a polygon
Function PolyCentroid:Float[](poly:Float[])

	Local result:Float[2]	'i0 = x, i1 = y
    result[0] = 0
    result[1] = 0

    For Local i:Int = 0 Until (poly.Length - 2) Step 2
		result[0] += (poly[i] + poly[i+2]) * ((poly[i] * poly[i+3]) - (poly[i+2] * poly[i+1]))
		result[1] += (poly[i+1] + poly[i+3]) * ((poly[i] * poly[i+3]) - (poly[i+2] * poly[i+1]))
    Next

    Local area:Float = PolygonArea(poly)

    result[0] = Abs(result[0] / 6.0 / area)
    result[1] = Abs(result[1] / 6.0 / area)

	Return result

End