2D Polygon Convex Decomposition Code

I need a function where I put the vertices of the polygon and returns a list of arrays of Vector2 where each array is the points of the individual convex polygons, for my custom collision detection that uses SAT, Separating Axis Theorem (which only works for convex polygons).

All I want to do is to decompose a concave polygon into several convex ones and get their vertices. If the polygon is already convex then it should return the same polygon.

It doesn’t necessarily have to work with polygons with holes, but preferably with complex polygons (self-intersecting ones).

So what algorithm can I use and what approach can I take to have a fast polygon decomposition function that works with concave and preferably self-intersecting polygons?

Hi, I finally found the solution to my problem.
I found a free physics engine in the asset store, named FarseerUnity.
That asset has a class named “Bayazit Decomposer”, which obviously uses Bayazit’s algorithm to decompose the polygon.
So I copyed the functions that were necessary and the class is now working perfectly.

Here is the class:

using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;

/// <summary>
/// This class is took from the "FarseerUnity" physics engine, which uses Mark Bayazit's decomposition algorithm.
/// I also have to make it work with self-intersecting polygons, so I'll use another different algorithm to decompose a self-intersecting polygon into several simple polygons,
/// and then I would decompose each of them into convex polygons.
/// </summary>

//From phed rev 36

/// <summary>
/// Convex decomposition algorithm created by Mark Bayazit (http://mnbayazit.com/)
/// For more information about this algorithm, see http://mnbayazit.com/406/bayazit
/// </summary>
public static class BayazitDecomposer
{
	private static Vector2 At(int i, List<Vector2> vertices)
	{
		int s = vertices.Count;
		return vertices[i < 0 ? s - (-i % s) : i % s];
	}
	
	private static List<Vector2> Copy(int i, int j, List<Vector2> vertices)
	{
		List<Vector2> p = new List<Vector2>();
		while (j < i) j += vertices.Count;
		//p.reserve(j - i + 1);
		for (; i <= j; ++i)
		{
			p.Add(At(i, vertices));
		}
		return p;
	}
	
	/// <summary>
	/// Decompose the polygon into several smaller non-concave polygon.
	/// If the polygon is already convex, it will return the original polygon, unless it is over Settings.MaxPolygonVertices.
	/// Precondition: Counter Clockwise polygon
	/// </summary>
	/// <param name="vertices"></param>
	/// <returns></returns>
	public static List<List<Vector2>> ConvexPartition(List<Vector2> vertices)
	{
		//We force it to CCW as it is a precondition in this algorithm.
		ForceCounterClockWise (vertices);
		
		List<List<Vector2>> list = new List<List<Vector2>>();
		float d, lowerDist, upperDist;
		Vector2 p;
		Vector2 lowerInt = new Vector2();
		Vector2 upperInt = new Vector2(); // intersection points
		int lowerIndex = 0, upperIndex = 0;
		List<Vector2> lowerPoly, upperPoly;
		
		for (int i = 0; i < vertices.Count; ++i)
		{
			if (Reflex(i, vertices))
			{
				lowerDist = upperDist = float.MaxValue; // std::numeric_limits<qreal>::max();
				for (int j = 0; j < vertices.Count; ++j)
				{
					// if line intersects with an edge
					if (Left(At(i - 1, vertices), At(i, vertices), At(j, vertices)) &&
					    RightOn(At(i - 1, vertices), At(i, vertices), At(j - 1, vertices)))
					{
						// find the point of intersection
						p = LineIntersect(At(i - 1, vertices), At(i, vertices), At(j, vertices),
						                              At(j - 1, vertices));
						if (Right(At(i + 1, vertices), At(i, vertices), p))
						{
							// make sure it's inside the poly
							d = SquareDist(At(i, vertices), p);
							if (d < lowerDist)
							{
								// keep only the closest intersection
								lowerDist = d;
								lowerInt = p;
								lowerIndex = j;
							}
						}
					}
					
					if (Left(At(i + 1, vertices), At(i, vertices), At(j + 1, vertices)) &&
					    RightOn(At(i + 1, vertices), At(i, vertices), At(j, vertices)))
					{
						p = LineIntersect(At(i + 1, vertices), At(i, vertices), At(j, vertices),
						                              At(j + 1, vertices));
						if (Left(At(i - 1, vertices), At(i, vertices), p))
						{
							d = SquareDist(At(i, vertices), p);
							if (d < upperDist)
							{
								upperDist = d;
								upperIndex = j;
								upperInt = p;
							}
						}
					}
				}
				
				// if there are no vertices to connect to, choose a point in the middle
				if (lowerIndex == (upperIndex + 1) % vertices.Count)
				{
					Vector2 sp = ((lowerInt + upperInt) / 2);
					
					lowerPoly = Copy(i, upperIndex, vertices);
					lowerPoly.Add(sp);
					upperPoly = Copy(lowerIndex, i, vertices);
					upperPoly.Add(sp);
				}
				else
				{
					double highestScore = 0, bestIndex = lowerIndex;
					while (upperIndex < lowerIndex) upperIndex += vertices.Count;
					for (int j = lowerIndex; j <= upperIndex; ++j)
					{
						if (CanSee(i, j, vertices))
						{
							double score = 1 / (SquareDist(At(i, vertices), At(j, vertices)) + 1);
							if (Reflex(j, vertices))
							{
								if (RightOn(At(j - 1, vertices), At(j, vertices), At(i, vertices)) &&
								    LeftOn(At(j + 1, vertices), At(j, vertices), At(i, vertices)))
								{
									score += 3;
								}
								else
								{
									score += 2;
								}
							}
							else
							{
								score += 1;
							}
							if (score > highestScore)
							{
								bestIndex = j;
								highestScore = score;
							}
						}
					}
					lowerPoly = Copy(i, (int)bestIndex, vertices);
					upperPoly = Copy((int)bestIndex, i, vertices);
				}
				list.AddRange(ConvexPartition(lowerPoly));
				list.AddRange(ConvexPartition(upperPoly));
				return list;
			}
		}
		
		// polygon is already convex
		list.Add(vertices);
		
		//The polygons are not guaranteed to be without collinear points. We remove
		//them to be sure.
		for (int i = 0; i < list.Count; i++)
		{
			//list _= SimplifyTools.CollinearSimplify(list*, 0);*_

* }*

* //Remove empty vertice collections*
* for (int i = list.Count - 1; i >= 0; i–)*
* {*
_ if (list*.Count == 0)
list.RemoveAt(i);
}*_

* return list;*
* }*

* private static bool CanSee(int i, int j, List vertices)*
* {*
* if (Reflex(i, vertices))*
* {*
* if (LeftOn(At(i, vertices), At(i - 1, vertices), At(j, vertices)) &&*
* RightOn(At(i, vertices), At(i + 1, vertices), At(j, vertices))) return false;*
* }*
* else*
* {*
* if (RightOn(At(i, vertices), At(i + 1, vertices), At(j, vertices)) ||*
* LeftOn(At(i, vertices), At(i - 1, vertices), At(j, vertices))) return false;*
* }*
* if (Reflex(j, vertices))*
* {*
* if (LeftOn(At(j, vertices), At(j - 1, vertices), At(i, vertices)) &&*
* RightOn(At(j, vertices), At(j + 1, vertices), At(i, vertices))) return false;*
* }*
* else*
* {*
* if (RightOn(At(j, vertices), At(j + 1, vertices), At(i, vertices)) ||*
* LeftOn(At(j, vertices), At(j - 1, vertices), At(i, vertices))) return false;*
* }*
* for (int k = 0; k < vertices.Count; ++k)*
* {*
* if ((k + 1) % vertices.Count == i || k == i || (k + 1) % vertices.Count == j || k == j)*
* {*
* continue; // ignore incident edges*
* }*
* Vector2 intersectionPoint;*
* if (LineIntersect2(At(i, vertices), At(j, vertices), At(k, vertices), At(k + 1, vertices), out intersectionPoint))*
* {*
* return false;*
* }*
* }*
* return true;*
* }*

* // precondition: ccw*
* private static bool Reflex(int i, List vertices)*
* {*
* return Right(i, vertices);*
* }*

* private static bool Right(int i, List vertices)*
* {*
* return Right(At(i - 1, vertices), At(i, vertices), At(i + 1, vertices));*
* }*

* private static bool Left(Vector2 a, Vector2 b, Vector2 c)*
* {*
* return Area(ref a, ref b, ref c) > 0;*
* }*

* private static bool LeftOn(Vector2 a, Vector2 b, Vector2 c)*
* {*
* return Area(ref a, ref b, ref c) >= 0;*
* }*

* private static bool Right(Vector2 a, Vector2 b, Vector2 c)*
* {*
* return Area(ref a, ref b, ref c) < 0;*
* }*

* private static bool RightOn(Vector2 a, Vector2 b, Vector2 c)*
* {*
* return Area(ref a, ref b, ref c) <= 0;*
* }*

* private static float SquareDist(Vector2 a, Vector2 b)*
* {*
* float dx = b.x - a.x;*
* float dy = b.y - a.y;*
_ return dx * dx + dy * dy;
* }*_

* //forces counter clock wise order.*
* private static void ForceCounterClockWise(List vertices)*
* {*
* if (!IsCounterClockWise(vertices))*
* {*
* vertices.Reverse();*
* }*
* }*

* private static bool IsCounterClockWise(List vertices)*
* {*
* //We just return true for lines*
* if (vertices.Count < 3)*
* return true;*

* return (GetSignedArea(vertices) > 0.0f);*
* }*

* //gets the signed area.*
* private static float GetSignedArea(List vertices)*
* {*
* int i;*
* float area = 0;*

* for (i = 0; i < vertices.Count; i++)*
* {*
* int j = (i + 1) % vertices.Count;*
area += vertices_.x * vertices[j].y;
area -= vertices.y * vertices[j].x;
* }
area /= 2.0f;
return area;
}*_

* //From Mark Bayazit’s convex decomposition algorithm*
* private static Vector2 LineIntersect(Vector2 p1, Vector2 p2, Vector2 q1, Vector2 q2)*
* {*
* Vector2 i = Vector2.zero;*
* float a1 = p2.y - p1.y;*
* float b1 = p1.x - p2.x;*
_ float c1 = a1 * p1.x + b1 * p1.y;
* float a2 = q2.y - q1.y;
float b2 = q1.x - q2.x;*

float c2 = a2 * q1.x + b2 * q1.y;
float det = a1 * b2 - a2 * b1;_

* if (!FloatEquals(det, 0))*
* {*
* // lines are not parallel*
_ i.x = (b2 * c1 - b1 * c2) / det;
i.y = (a1 * c2 - a2 * c1) / det;
* }
return i;
}*_

* //from Eric Jordan’s convex decomposition library, it checks if the lines a0->a1 and b0->b1 cross.*
* //if they do, intersectionPoint will be filled with the point of crossing. Grazing lines should not return true.*
* private static bool LineIntersect2(Vector2 a0, Vector2 a1, Vector2 b0, Vector2 b1, out Vector2 intersectionPoint)*
* {*
* intersectionPoint = Vector2.zero;*

* if (a0 == b0 || a0 == b1 || a1 == b0 || a1 == b1)*
* return false;*

* float x1 = a0.x;*
* float y1 = a0.y;*
* float x2 = a1.x;*
* float y2 = a1.y;*
* float x3 = b0.x;*
* float y3 = b0.y;*
* float x4 = b1.x;*
* float y4 = b1.y;*

* //AABB early exit*
* if (Math.Max(x1, x2) < Math.Min(x3, x4) || Math.Max(x3, x4) < Math.Min(x1, x2))*
* return false;*

* if (Math.Max(y1, y2) < Math.Min(y3, y4) || Math.Max(y3, y4) < Math.Min(y1, y2))*
* return false;*

_ float ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3));
float ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3));
float denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
* if (Math.Abs(denom) < Mathf.Epsilon)
{
//Lines are too close to parallel to call*

* return false;
}
ua /= denom;
ub /= denom;*_

* if ((0 < ua) && (ua < 1) && (0 < ub) && (ub < 1))*
* {*
_ intersectionPoint.x = (x1 + ua * (x2 - x1));
intersectionPoint.y = (y1 + ua * (y2 - y1));
* return true;
}*_

* return false;*
* }*

* private static bool FloatEquals(float value1, float value2)*
* {*
* return Math.Abs(value1 - value2) <= Mathf.Epsilon;*
* }*

* // Returns a positive number if c is to the left of the line going from a to b. Positive number if point is left,*
* //negative if point is right,and 0 if points are collinear.*
* private static float Area(Vector2 a, Vector2 b, Vector2 c)*
* {*
* return Area(ref a, ref b, ref c);*
* }*

* //returns a positive number if c is to the left of the line going from a to b. Positive number if point is left, negative if point is right, and 0 if points are collinear.*
* private static float Area(ref Vector2 a, ref Vector2 b, ref Vector2 c)*
* {*
_ return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
* }*_

* //removes all collinear points on the polygon.*
* private static List CollinearSimplify(List vertices, float collinearityTolerance)*
* {*
* //We can’t simplify polygons under 3 vertices*
* if (vertices.Count < 3)*
* return vertices;*

* List simplified = new List();*

* for (int i = 0; i < vertices.Count; i++)*
* {*
* int prevId = PreviousIndex(vertices, i);*
* int nextId = NextIndex(vertices, i);*

* Vector2 prev = vertices[prevId];*
_ Vector2 current = vertices*;
Vector2 next = vertices[nextId];*_

* //If they collinear, continue*
* if (Collinear(ref prev, ref current, ref next, collinearityTolerance))*
* continue;*

* simplified.Add(current);*
* }*

* return simplified;*
* }*

* //gets the previous index.*
* private static int PreviousIndex(List vertices, int index)*
* {*
* if (index == 0)*
* {*
* return vertices.Count - 1;*
* }*
* return index - 1;*
* }*

* //nexts the index.*
* private static int NextIndex(List vertices, int index)*
* {*
* if (index == vertices.Count - 1)*
* {*
* return 0;*
* }*
* return index + 1;*
* }*

* private static bool Collinear(ref Vector2 a, ref Vector2 b, ref Vector2 c, float tolerance)*
* {*
* return FloatInRange(Area(ref a, ref b, ref c), -tolerance, tolerance);*
* }*

* //checks if a floating point Value is within a specified range of values (inclusive).*
* private static bool FloatInRange(float value, float min, float max)*
* {*
* return (value >= min && value <= max);*
* }*
}
and here’s a class to test it, just attach this script and a 2d polygon collider to an object, and you’ll see the algorithm in action.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BayazitDecomposerTester : MonoBehaviour
{
* private PolygonCollider2D col;*
* public bool show;*

* void Start ()*
* {*
* col = GetComponent ();*

* if (col == null)*
* {*
* Debug.LogError (“There is no ‘PolygonCollider2D’ attached to the object ‘BayazitDecomposerTester’ is attached to.”);*
* }*
* }*

* void OnDrawGizmos ()*
* {*
* if (!Application.isPlaying || !show)*
* return;*

* Gizmos.color = Color.green;*

* List worldColPoints = new List ();*

* foreach (Vector2 point in col.points)*
* {*
* Vector2 currentWorldPoint = this.transform.TransformPoint (point);*
* worldColPoints.Add (currentWorldPoint);*
* }*

* List vertices = worldColPoints;*

* List<List> listOfConvexPolygonPoints = BayazitDecomposer.ConvexPartition (vertices);*

* foreach (List pointsOfIndivualConvexPolygon in listOfConvexPolygonPoints)*
* {*
* List currentPolygonVertices = pointsOfIndivualConvexPolygon;*

* for (int i = 0; i < currentPolygonVertices.Count; i++)*
* {*
_ Vector2 currentVertex = currentPolygonVertices*;
Vector2 nextVertex = currentPolygonVertices[i + 1 >= currentPolygonVertices.Count? 0 : i + 1];*_

* Gizmos.DrawLine (currentVertex, nextVertex);*
* }*
* }*
* }*
}