Monkey2 Polygon Decomposition

MakeConvex.monkey2

Namespace polygonmath

#Import "<std>"

Using std..

#rem Decomposes counter-clockwise simple polygons into convex polygons in under-quadratic time.

 @author Matrefeytontias
 @engine HaxePunk
 @source https://github.com/HaxePunk/HaxePunk/blob/dev/haxepunk/math/MakeConvex.hx
 @article https://gamedevnotesblog.wordpress.com/2017/10/29/designing-algorithms-intuitively-convex-decomposition-of-simple-polygons/
 @license MIT
 
 @translator Abe Noll
#End

#Rem Decomposes a counter-clockwise simple polygon into convex polygons.
#End
Function MakeConvex<T>:Stack<Stack<Vec2<T>>>( polygon:Stack<Vec2<T>> )
	Local p:= New Stack<Vec2<T>>( polygon )			' polygon pt list
	Local r:= New Stack<Stack<Vec2<T>>>				' list of polygons 
	Local invalidVertices:= FindInvalid( p )
	Local np:= p.Length

	Local n:Int= invalidVertices.Length
	While invalidVertices.Length>0
		n = invalidVertices.Length 
		' Find the starting vertex ; it's any invalid vertex that has a valid vertex after it
		' we know this exists because a polygon must have at least one valid vertex
		Local startIndex:Int = 0
		For Local i:=0 Until n
			'if (n == 1 || (invalidVertices[i] + 1) % np != invalidVertices[(i + 1) % n])
			If n=1 Or ((invalidVertices[i] + 1) Mod np )<>invalidVertices[(i + 1) Mod n] Then 
				startIndex = invalidVertices[i]
				Exit
			Endif
		Next

		'After that, find the furthest valid point along the polygon that still forms a convex
		'polygon when linked to the starting vertex, or the first invalid vertex.
		'This is because by definition, the two edges that an invalid vertex is a part of cannot
		'belong to the same one polygon.
		Local startVertex:= p[startIndex]
		Local firstEdge:= p[ (startIndex + 1) Mod np] - startVertex
		Local found:= False, target:Int = 0
		For Local i:=2 Until np
			Local curIndex:= (startIndex + i) Mod np
			Local curVertex:= p[curIndex]

			' This vertex is invalid
			If invalidVertices.FindIndex(curIndex)>-1 Then  
				found = True
				target = curIndex
			Elseif (startVertex - curVertex).OrthoR().Dot(firstEdge)< 0
				' This vertex, If added, would turn the polygon from convex To concave.
				' Thus, the correct vertex is the previous one
				found = True
				target = (startIndex + i - 1) Mod np
			Endif

			If found Then 
				' Extract vertices startIndex to "target" ; they make up a convex polygon
				Local newPoly:= New Stack<Vec2<T>>, k:= startIndex
				While True
					newPoly.Push(p[k])
					If k=target Exit Else k = (k + 1) Mod np
				Wend
				
				r.Push( newPoly )
				
				' Then, discard the vertices that were added to the resulting array, except the start and end
				Local rem:= p.RemoveIf( Lambda:Bool( x:Vec2i )
					Return Not (newPoly.FindIndex(x)=-1 Or x=startVertex Or x=p[target])
				End )
				
				np = p.Length
				' Rearrange the indices in invalidVertices as well, since the contents of p will change
				invalidVertices = FindInvalid( p )
				If invalidVertices.Length=0 Then r.Push(p)
				Exit
				
			Endif
		Next
	Wend
	
	If r.Empty r.Push(polygon)
	Return r
End
	
Private
	
#Rem Find all invalid vertices, that is, vertices that form an invalid angle (> 180°)
#End
Function FindInvalid<T>:IntStack( p:Stack<Vec2<T>> )
	Local invalidVertices:=New IntStack
	Local np:= p.Length
	
	For Local VIndex:=0 Until np
		Local currentV:= p[VIndex]
		Local nextV:= p[ (VIndex + 1) Mod np]
		Local nextNextV:= p[(VIndex + 2) Mod np]
		
		Local currentEdge:= nextV - currentV
		Local nextEdge:= nextNextV - nextV
		
		If currentEdge.OrthoR().Dot( nextEdge ) < 0 Then 
			invalidVertices.Push( (VIndex + 1) Mod np)
		Endif
	Next
		
	Return invalidVertices
End

Struct Vec2<T> Extension
	Method OrthoR:Vec2<T>()
		Return New Vec2<T>(Self.y, -Self.x)
	End
End

PolygonDecomposition.monkey2

#Import "MakeConvex.monkey2"

Alias Poly:polygonmath

Function Main()


	' Makes this shape.
	'      /\
	'     /  \
	'    /    \
	'   /      \
	'   |  /\  |
	'   | /  \ |
	'   |/    \|
	'
	Local pointsA:=New Vec2i[]( 
		New Vec2i(0,0),
		New Vec2i(0,1),
		New Vec2i(1,3),
		New Vec2i(2,1),
		New Vec2i(2,0),
		New Vec2i(1,1) )
		
	' Convert to stack
	Local points:= New Stack<Vec2i>( pointsA )	
	
	' Basic printing function
	Local printPoints:= ( Lambda(s:Stack<Vec2i>)
		Local ps:= ""
		For Local p:=Eachin s
			ps += p.X + "," + p.Y + "  -->  "
		Next	
		Print ps + "~n"
	End )
	
	
	' Display the original point list 
	printPoints( points )
	
	' Display the created groups
	Local groups:=Poly.MakeConvex( points )
	For Local poly:=Eachin groups
		Print "group: "
		printPoints( poly )
	Next
	
End