Last active
March 15, 2019 07:15
-
-
Save XANOZOID/d8d2c9973ff7dc120d94b356730c75f9 to your computer and use it in GitHub Desktop.
Monkey2 Polygon Decomposition
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment