Break a Concave Shape into Multiple Convex Shapes

February 8th, 2020

You appeared to have created an Objective C version of the "Angelov" solution, but abandoned it for a different approach (Bayazit). See below.

Original

(Original notes from 2012-01-27 11:03 PM; some code examples salvaged from NoS work/tooling).

Actionscript? I think. From here or more likely here. This looks like someone's Java implementation.

/* 
* Convex Separator for Box2D Flash
*
* This class has been written by Antoan Angelov.
* It is designed to work with Erin Catto's Box2D physics library.
*
* Everybody can use this software for any purpose, under two restrictions:
* 1. You cannot claim that you wrote this software.
* 2. You can not remove or alter this notice.
*
*/

package Box2DSeparator
{
     import Box2D.Collision.Shapes.b2PolygonShape;
     import Box2D.Common.Math.b2Vec2;
     import Box2D.Dynamics.b2Body;
     import Box2D.Dynamics.b2FixtureDef;

     public class b2Separator
     {
          public function b2Separator()
          {
          }
         
          /**
           * Separates a non-convex polygon into convex polygons and adds them as fixtures to the <code>body</code> parameter.<br/>
           * There are some rules you should follow (otherwise you might get unexpected results) :
           * <ul>
           * <li>This class is specifically for non-convex polygons. If you want to create a convex polygon, you don't need to use this class - Box2D's <code>b2PolygonShape</code> class allows you to create convex shapes with the <code>setAsArray()</code>/<code>setAsVector()</code> method.</li>
           * <li>The vertices must be in clockwise order.</li>
           * <li>No three neighbouring points should lie on the same line segment.</li>
           * <li>There must be no overlapping segments and no "holes".</li>
           * </ul> <p/>
           * @param body The b2Body, in which the new fixtures will be stored.
           * @param fixtureDef A b2FixtureDef, containing all the properties (friction, density, etc.) which the new fixtures will inherit.
           * @param verticesVec The vertices of the non-convex polygon, in clockwise order.
           * @param scale <code>[optional]</code> The scale which you use to draw shapes in Box2D. The bigger the scale, the better the precision. The default value is 30.
           * @see b2PolygonShape
           * @see b2PolygonShape.SetAsArray()
           * @see b2PolygonShape.SetAsVector()
           * @see b2Fixture
           * */
         
          public function Separate(body:b2Body, fixtureDef:b2FixtureDef, verticesVec:Vector.<b2Vec2>, scale:Number = 30):void
          {              
               var i:int, n:int = verticesVec.length, j:int, m:int;
               var vec:Vector.<b2Vec2> = new Vector.<b2Vec2>(), figsVec:Array;
               var polyShape:b2PolygonShape;
              
               for(i=0; i<n; i++) vec.push(new b2Vec2(verticesVec[i].x*scale, verticesVec[i].y*scale));
              
               figsVec = calcShapes(vec);
               n = figsVec.length;    

               for(i=0; i<n; i++)
               {
                    verticesVec = new Vector.<b2Vec2>();
                    vec = figsVec[i];
                    m = vec.length;
                    for(j=0; j<m; j++) verticesVec.push(new b2Vec2(vec[j].x/scale, vec[j].y/scale));
                                       
                    polyShape = new b2PolygonShape();
                    polyShape.SetAsVector(verticesVec);
                    fixtureDef.shape = polyShape;
                    body.CreateFixture(fixtureDef);
               }
          }
         
          /**
           * Checks whether the vertices in <code>verticesVec</code> can be properly distributed into the new fixtures (more specifically, it makes sure there are no overlapping segments and the vertices are in clockwise order).
           * It is recommended that you use this method for debugging only, because it may cost more CPU usage.
           * <p/>
           * @param verticesVec The vertices to be validated.
           * @return An integer which can have the following values:
           * <ul>
           * <li>0 if the vertices can be properly processed.</li>
           * <li>1 If there are overlapping lines.</li>
           * <li>2 if the points are <b>not</b> in clockwise order.</li>
           * <li>3 if there are overlapping lines <b>and</b> the points are <b>not</b> in clockwise order.</li>
           * </ul>
           * */
         
          public function Validate(verticesVec:Vector.<b2Vec2>):int
          {
               var i:int, n:int = verticesVec.length, j:int, j2:int, i2:int, i3:int, d:Number, ret:int = 0;
               var fl:Boolean, fl2:Boolean = false;
              
               for(i=0; i<n; i++)
               {
                    i2 = (i<n-1?i+1:0);
                    i3 = (i>0?i-1:n-1);
                   
                    fl = false;
                    for(j=0; j<n; j++)
                    {
                         if(j!=i&&j!=i2)
                         {
                              if(!fl)
                              {
                                   d = det(verticesVec[i].x, verticesVec[i].y, verticesVec[i2].x, verticesVec[i2].y, verticesVec[j].x, verticesVec[j].y);
                                   if(d>0) fl = true;
                              }
                             
                              if(j!=i3)
                              {
                                   j2 = (j<n-1?j+1:0);
                                   if(hitSegment(verticesVec[i].x, verticesVec[i].y, verticesVec[i2].x, verticesVec[i2].y, verticesVec[j].x, verticesVec[j].y, verticesVec[j2].x, verticesVec[j2].y))
                                        ret = 1;
                              }
                         }
                    }
                   
                    if(!fl) fl2 = true;              
               }
              
               if(fl2)
               {
                    if(ret==1) ret = 3;
                    else ret = 2;
               }
              
               return ret;
          }
         
          private function calcShapes(verticesVec:Vector.<b2Vec2>):Array
          {
               var vec:Vector.<b2Vec2>;
               var i:int, n:int, j:int;
               var d:Number, t:Number, dx:Number, dy:Number, minLen:Number;
               var i1:int, i2:int, i3:int, p1:b2Vec2, p2:b2Vec2, p3:b2Vec2;
               var j1:int, j2:int, v1:b2Vec2, v2:b2Vec2, k:int, h:int;
               var vec1:Vector.<b2Vec2>, vec2:Vector.<b2Vec2>;
               var v:b2Vec2, hitV:b2Vec2;
               var isConvex:Boolean;
               var figsVec:Array = [], queue:Array = [];
              
               queue.push(verticesVec);
              
               while(queue.length)
               {
                    vec = queue[0];
                    n = vec.length;
                    isConvex = true;
                   
                    for(i=0; i<n; i++)
                    {
                         i1 = i;
                         i2 = (i<n-1?i+1:i+1-n);
                         i3 = (i<n-2?i+2:i+2-n);

                         p1 = vec[i1];
                         p2 = vec[i2];
                         p3 = vec[i3];
                        
                         d = det(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
                         if(d<0)
                         {
                              isConvex = false;
                              minLen = Number.MAX_VALUE;
                             
                              for(j=0; j<n; j++)
                              {
                                   if(j!=i1&&j!=i2)
                                   {
                                        j1 = j;
                                        j2 = (j<n-1?j+1:0);

                                        v1 = vec[j1];
                                        v2 = vec[j2];

                                        v = hitRay(p1.x, p1.y, p2.x, p2.y, v1.x, v1.y, v2.x, v2.y);
                                       
                                        if(v)
                                        {
                                             dx = p2.x-v.x;
                                             dy = p2.y-v.y;
                                             t = dx*dx+dy*dy;
                                            
                                             if(t<minLen)
                                             {
                                                  h = j1;
                                                  k = j2;
                                                  hitV = v;
                                                  minLen = t;
                                             }
                                        }
                                   }
                              }
                             
                              if(minLen==Number.MAX_VALUE) err();
                             
                              vec1 = new Vector.<b2Vec2>();
                              vec2 = new Vector.<b2Vec2>();
                             
                              j1 = h;
                              j2 = k;
                              v1 = vec[j1];
                              v2 = vec[j2];
                             
                              if(!pointsMatch(hitV.x, hitV.y, v2.x, v2.y)) vec1.push(hitV);
                              if(!pointsMatch(hitV.x, hitV.y, v1.x, v1.y)) vec2.push(hitV);
                                                           
                              h = -1;
                              k = i1;
                              while(true)
                              {
                                   if(k!=j2) vec1.push(vec[k]);
                                   else
                                   {
                                        if(h<0||h>=n) err();
                                        if(!this.isOnSegment(v2.x, v2.y, vec[h].x, vec[h].y, p1.x, p1.y)) vec1.push(vec[k]);
                                        break;
                                   }

                                   h = k;
                                   if(k-1<0) k = n-1;
                                   else k--;
                              }
                             
                              vec1 = vec1.reverse();
                             
                              h = -1;
                              k = i2;
                              while(true)
                              {
                                   if(k!=j1) vec2.push(vec[k]);
                                   else
                                   {
                                        if(h<0||h>=n) err();
                                        if(k==j1&&!this.isOnSegment(v1.x, v1.y, vec[h].x, vec[h].y, p2.x, p2.y)) vec2.push(vec[k]);
                                        break;
                                   }

                                   h = k;
                                   if(k+1>n-1) k = 0;
                                   else k++;
                              }
                             
                              queue.push(vec1, vec2);
                              queue.shift();

                              break;
                         }
                    }
                   
                    if(isConvex) figsVec.push(queue.shift());
               }
              
               return figsVec;
          }
                   
          private function hitRay(x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number, x4:Number, y4:Number):b2Vec2
          {
               var t1:Number = x3-x1, t2:Number = y3-y1, t3:Number = x2-x1, t4:Number = y2-y1,
                    t5:Number = x4-x3, t6:Number = y4-y3, t7:Number = t4*t5-t3*t6, a:Number;
              
               a = (t5*t2-t6*t1)/t7;
               var px:Number = x1+a*t3, py:Number = y1+a*t4;
               var b1:Boolean = isOnSegment(x2, y2, x1, y1, px, py);
               var b2:Boolean = isOnSegment(px, py, x3, y3, x4, y4);
              
               if(b1&&b2) return new b2Vec2(px, py);
              
               return null;
          }
         
          private function hitSegment(x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number, x4:Number, y4:Number):b2Vec2
          {
               var t1:Number = x3-x1, t2:Number = y3-y1, t3:Number = x2-x1, t4:Number = y2-y1,
                    t5:Number = x4-x3, t6:Number = y4-y3, t7:Number = t4*t5-t3*t6, a:Number;
              
               a = (t5*t2-t6*t1)/t7;
               var px:Number = x1+a*t3, py:Number = y1+a*t4;
               var b1:Boolean = isOnSegment(px, py, x1, y1, x2, y2);
               var b2:Boolean = isOnSegment(px, py, x3, y3, x4, y4);
              
               if(b1&&b2) return new b2Vec2(px, py);
              
               return null;
          }
         
          private function isOnSegment(px:Number, py:Number, x1:Number, y1:Number, x2:Number, y2:Number):Boolean
          {
               var b1:Boolean = ((x1+0.1>=px&&px>=x2-0.1)||(x1-0.1<=px&&px<=x2+0.1));
               var b2:Boolean = ((y1+0.1>=py&&py>=y2-0.1)||(y1-0.1<=py&&py<=y2+0.1));
               return (b1&&b2&&isOnLine(px, py, x1, y1, x2, y2));
          }
         
          private function pointsMatch(x1:Number, y1:Number, x2:Number, y2:Number):Boolean
          {
               var dx:Number = (x2>=x1?x2-x1:x1-x2), dy:Number = (y2>=y1?y2-y1:y1-y2);
               return (dx<0.1&&dy<0.1);
          }
         
          private function isOnLine(px:Number, py:Number, x1:Number, y1:Number, x2:Number, y2:Number):Boolean
          {
               if(x2-x1>0.1||x1-x2>0.1)
               {
                    var a:Number = (y2-y1)/(x2-x1), possibleY:Number = a*(px-x1)+y1, diff:Number = (possibleY>py?possibleY-py:py-possibleY);
                    return (diff<0.1);
               }
              
               return (px-x1<0.1||x1-px<0.1);              
          }
         
          private function det(x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):Number
          {
               return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;   
          }
         
          private function err():void
          {
               throw new Error("A problem has occurred. Use the Validate() method to see where the problem is.");
          }
     }
}

Your Objective-C version of this:

AngelovConvexPolygons.m

//
//  AngelovConvexPolygons.m
//  Convex Shape Maker
//
//  Created by Nathan Lamont on 2/12/12.
//  Copyright (c) 2012 Bigger Planet. All rights reserved.
//

#include <stdio.h>
#import "BpPoint.h"
#import "NSMutableArray+Stack.h"

#define kNoise	0.01

BpPoint *hitRay( BpPoint *p1, BpPoint *p2, BpPoint *p3, BpPoint *p4);
BpPoint *hitSegment( BpPoint *p1, BpPoint *p2, BpPoint *p3, BpPoint *p4);
BOOL isOnSegment( BpPoint *pp, BpPoint *p1, BpPoint *p2);
BOOL pointsMatch( BpPoint *p1, BpPoint *p2);
BOOL isOnLine( BpPoint *pp, BpPoint *p1, BpPoint *p2);
float det( BpPoint *p1, BpPoint *p2, BpPoint *p3);
int validateVertices( NSMutableArray *vertices);

NSMutableArray *angelovCalculateShapes( NSMutableArray *vertices)
{
	NSMutableArray *queue = [NSMutableArray array], *results = [NSMutableArray array];
	float	minLen, dx, dy, t;
	int		j1, j2, h, k;
	NSMutableArray	*vec1, *vec2;
	BpPoint			*v, *v1, *v2, *hitV;
	
	if ( validateVertices( vertices) != 0) return nil;
	[queue push: vertices];
	while ( [queue count] > 0) {
		NSMutableArray *vec = [queue objectAtIndex: 0];
		int n = [vec count];
		BOOL isConvex = YES;
		
		for ( int i = 0; i < n; i++) {
			int i1 = i;
			int i2 = ((i < (n - 1)) ? (i + 1) : (i + 1 - n));
			int i3 = ((i < (n - 2)) ? (i + 2) : (i + 2 - n));
			BpPoint *p1 = [vec objectAtIndex: i1];
			BpPoint	*p2 = [vec objectAtIndex: i2];
			BpPoint	*p3 = [vec objectAtIndex: i3];
			
			float d = det(p1, p2, p3);
			if ( d < 0.0)
			{
				isConvex = NO;
				minLen = FLT_MAX;
				
				for ( int j = 0; j < n; j++)
				{
					if ( j!= i1 && j != i2)
					{
						j1 = j;
						j2 = (j < (n - 1)) ? (j + 1) : (0);
						
						v1 = [vec objectAtIndex: j1];
						v2 = [vec objectAtIndex: j2];
						v = hitRay(p1, p2, v1, v2);
						
						if ( v != nil)
						{
							dx = p2.x - v.x;
							dy = p2.y - v.y;
							t = dx*dx + dy*dy;
							
							if ( t < minLen)
							{
								h = j1;
								k = j2;
								hitV = v;
								minLen = t;
							}
						}
					}
				}
				assert( minLen != FLT_MAX);
				
				vec1 = [NSMutableArray array];
				vec2 = [NSMutableArray array];
				
				j1 = h;
				j2 = k;
				v1 = [vec objectAtIndex:j1];
				v2 = [vec objectAtIndex: j2];
				
				if ( !pointsMatch(hitV, v2)) [vec1 push:hitV];
				if ( !pointsMatch(hitV, v1)) [vec2 push:hitV];
				
				h = -1;
				k = i1;
				while (true) {
					if ( k != j1) [vec1 push: [vec objectAtIndex: k]];
					else
					{
						assert(!(h < 0 || h >= n));
						if ( !isOnSegment(v2, [vec objectAtIndex: h], p1)) [vec1 push: [vec objectAtIndex: k]];
						break;
					}
					
					h = k;
					if (( k - 1) < 0) k = n - 1;
					else k--;
				}
				vec1 = [NSMutableArray arrayWithArray:[[vec1 reverseObjectEnumerator] allObjects]];
				
				h = -1;
				k = i2;
				while ( true)
				{
					if ( k != j1) [vec2 push: [vec objectAtIndex: k]];
					else
					{
						assert(!(h < 0 || h >= n));
						if ( k == j1 && !isOnSegment(v1, [vec objectAtIndex:h], p2)) [vec2 push: [vec objectAtIndex:k]];
						break;
					}
					
					h = k;
					if ( (k + 1)  > (n - 1)) k = 0;
					else k++;
				}
				[queue push: vec1];
				[queue push: vec2];
				[queue shift];
				break;
			}
		}
		if ( isConvex) {
			[results push: [queue shift]];
		}
	}
	return results;
}

BpPoint *hitRay( BpPoint *p1, BpPoint *p2, BpPoint *p3, BpPoint *p4)
{
	float t1 = p3.x - p1.x, t2 = p3.y - p1.y, t3 = p2.x - p1.x, t4 = p2.y - p1.y;
	float t5 = p4.x - p3.x, t6 = p4.y - p3.y, t7 = t4 * t5 - t3 * t6;
	float a = (t5 * t2 - t6 * t1) / t7;
	float px = p1.x + a * t3, py = p1.y + a * t4;
	BpPoint *pp = [BpPoint pointWithX: px Y: py];
	BOOL b1 = isOnSegment( p2, p1, pp);
	BOOL b2 = isOnSegment( pp, p3, p4);
	if ( b1 && b2) return pp;
	else return nil;
}

BpPoint *hitSegment(  BpPoint *p1, BpPoint *p2, BpPoint *p3, BpPoint *p4)
{
	float t1 = p3.x - p1.x, t2 = p3.y - p1.y, t3 = p2.x - p1.x, t4 = p2.y - p1.y;
	float t5 = p4.x - p3.x, t6 = p4.y - p3.y, t7 = t4 * t5 - t3 * t6;
	float a = (t5 * t2 - t6 * t1) / t7;
	float px = p1.x + a * t3, py = p1.y + a * t4;
	BpPoint *pp = [BpPoint pointWithX: px Y: py];
	BOOL b1 = isOnSegment(pp, p1, p2);
	BOOL b2 = isOnSegment(pp, p3, p4);
	if (b1&&b2) return pp;
	else return nil;
}

BOOL isOnSegment( BpPoint *pp, BpPoint *p1, BpPoint *p2)
{
	BOOL b1 = ((((p1.x + kNoise) >= pp.x) && (pp.x >= (p2.x - kNoise))) ||
			   (((p1.x - kNoise) <= pp.x) && (pp.x <= (p2.x + kNoise))));
	BOOL b2 = ((((p1.y + kNoise) >= pp.y) && (pp.y >= (p2.y - kNoise))) ||
			   (((p1.y - kNoise) <= pp.y) && (pp.y <= (p2.y + kNoise))));
	return ( b1 && b2 && isOnLine( pp, p1, p2));
}

BOOL pointsMatch( BpPoint *p1, BpPoint *p2)
{
	float dx = (p2.x >= p1.x) ? (p2.x - p1.x) : (p1.x - p2.x);
	float dy = (p2.y >= p1.y) ? (p2.y - p1.y) : (p1.y - p2.y);
	return ((dx < kNoise) && ( dy < kNoise));
}

BOOL isOnLine(BpPoint *pp, BpPoint *p1, BpPoint *p2)
{
	if (((p2.x - p1.x) > kNoise) || ((p1.x - p2.x > kNoise))) {
		float a = (p2.y - p1.y) / (p2.x - p1.x);
		float possibleY = a * (pp.x - p1.x) + p1.y;
		float diff = (possibleY > pp.y) ? (possibleY - pp.y) : (pp.y - possibleY);
		return ( diff < kNoise);
	}
	return (((pp.x - p1.x) < kNoise) || ((p1.x - pp.x < kNoise)));
}

float det( BpPoint *p1, BpPoint *p2, BpPoint *p3)
{
	return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
}

int validateVertices( NSMutableArray *vertices)
{
	int	i, n = [vertices count], j, j1, j2, i2, i3, result = 0;
	float d;
	BOOL fl, fl2 = NO;
	
	for ( i = 0; i < n; i++)
	{
		i2 = ( i < ( n - 1)) ? ( i + 1) : (0);
		i3 = ( i > 0) ? ( i - 1) : ( n - 1);
		fl = NO;
		for ( j = 0; j < n; j++)
		{
			if ( j != i && j != i2)
			{
				if ( !fl)
				{
					d = det( [vertices objectAtIndex:i], [vertices objectAtIndex: i2], [vertices objectAtIndex:j]);
					if ( d > 0) fl = YES;
				}
				
				if ( j != i3)
				{
					j2 = ( j < ( n - 1)) ? ( j + 1) : ( 0);
					if ( hitSegment( [vertices objectAtIndex: i], [vertices objectAtIndex: i2],
									[vertices objectAtIndex: j], [vertices objectAtIndex: j2]))
						result = 1;
				}
			}
		}
		
		if ( !fl) fl2 = YES;
	}
	
	if ( fl2)
	{
		if ( result == 1) result = 3;
		else result = 2;
	}
	return result;
}

BayazitConvexPolygons.m

The solution you appear to have preferred. Source unknown but probably here -- C# Version Here but C++ version is not accessible.

Note, this was used in a single-purpose tool with somewhat controlled input. It seems to throw out line segments between the first and last vertices, possibly because the tool only cared about polygons describing 1/2 of an object (the last line segment being on the inside?).

//
//  BayazitConvexPolygons.m
//  Convex Shape Maker
//
//  Created by Nathan Lamont on 2/12/12.
//  Copyright (c) 2012 Bigger Planet. All rights reserved.
//

#include <stdio.h>
#include "BayazitConvexPolygons.h"
#include "AngelovConvexPolygons.h"

#import "NSMutableArray+Stack.h"
#import "BpPoint.h"

#pragma mark point prototypes

float area( BpPoint *a, BpPoint *b, BpPoint *c);
BOOL left( BpPoint *a, BpPoint *b, BpPoint *c);
BOOL leftOn( BpPoint *a, BpPoint *b, BpPoint *c);
BOOL right( BpPoint *a, BpPoint *b, BpPoint *c);
BOOL rightOn( BpPoint *a, BpPoint *b, BpPoint *c);
BOOL collinear( BpPoint *a, BpPoint *b, BpPoint *c);
float sqdist( BpPoint *a, BpPoint *b);

#pragma mark polygon prototypes
typedef struct bayazitInfoType {
	NSMutableArray *polys;
	NSMutableArray *steinerPoints;
	NSMutableArray *reflexVertices;
} bayazitInfoType;

BOOL eq(const float a, const float b);
void makeCCW( NSMutableArray **polygon);
BOOL isReflex( NSMutableArray *polygon, int i);
BpPoint *intersection(BpPoint *p1, BpPoint *p2, BpPoint *q1, BpPoint *q2);
BOOL pm1ok( NSMutableArray *a, int i);
void decomposePoly( NSMutableArray *poly, bayazitInfoType *info);

#pragma mark point functions

float area( BpPoint *a, BpPoint *b, BpPoint *c)
{
	if ( a == nil || b == nil || c == nil) return 0;
    return (((b.x - a.x)*(c.y - a.y))-((c.x - a.x)*(b.y - a.y)));	
}

BOOL left( BpPoint *a, BpPoint *b, BpPoint *c)
{
	return area(a, b, c) > 0;
}

BOOL leftOn( BpPoint *a, BpPoint *b, BpPoint *c)
{
    return area(a, b, c) >= 0;	
}

BOOL right( BpPoint *a, BpPoint *b, BpPoint *c)
{
    return area(a, b, c) < 0;	
}
BOOL rightOn( BpPoint *a, BpPoint *b, BpPoint *c)
{
    return area(a, b, c) <= 0;	
}

BOOL collinear( BpPoint *a, BpPoint *b, BpPoint *c)
{
	return area(a, b, c) == 0;
}

float sqdist( BpPoint *a, BpPoint *b)
{
	if ( a == nil || b == nil) return 0;
    float dx = b.x - a.x;
    float dy = b.y - a.y;
    return dx * dx + dy * dy;
}

#pragma mark polygon functions

BOOL eq(const float a, const float b) {
    return abs(a - b) <= 1e-8;
}

void makeCCW( NSMutableArray **polygon)
{
	int br = 0;
	BpPoint *brp = [*polygon objectAtIndex: br];
	
	// find bottom right point
	for ( int i = 0; i < [*polygon count]; ++i)
	{
		BpPoint *p = [*polygon objectAtIndex: i];
		if ( p.y < brp.y || (p.y == brp.y && p.x > brp.x)) {
			br = i;
			brp = [*polygon objectAtIndex: br];
		}
	}
	
	if ( !left( [*polygon at: br - 1], [*polygon at: br], [*polygon at: br + 1]))
	{
		*polygon = [NSMutableArray arrayWithArray:[[*polygon reverseObjectEnumerator] allObjects]];
	}
}

BOOL isReflex( NSMutableArray *polygon, int i)
{
	return ( right( [polygon at: i - 1], [polygon at: i], [polygon at: i+ 1]));
}

BpPoint *intersection(BpPoint *p1, BpPoint *p2, BpPoint *q1, BpPoint *q2) {
    BpPoint *i = [BpPoint pointWithX: 0.0 Y: 0.0];
    float a1, b1, c1, a2, b2, c2, det;
    a1 = p2.y - p1.y;
    b1 = p1.x - p2.x;
    c1 = a1 * p1.x + b1 * p1.y;
    a2 = q2.y - q1.y;
    b2 = q1.x - q2.x;
    c2 = a2 * q1.x + b2 * q1.y;
    det = a1 * b2 - a2*b1;
    if (!eq(det, 0)) { // lines are not parallel
        i.x = (b2 * c1 - b1 * c2) / det;
        i.y = (a1 * c2 - a2 * c1) / det;
    }
    return i;
}

void decomposePoly( NSMutableArray *poly, bayazitInfoType *info)
{
    BpPoint *upperInt = [BpPoint point], *lowerInt = [BpPoint point],
		*p = [BpPoint point], *closestVert = [BpPoint point];//[BpPoint point];
    float upperDist, lowerDist, d, closestDist;
    int upperIndex, lowerIndex, closestIndex;
    NSMutableArray *lowerPoly = [NSMutableArray array], *upperPoly = [NSMutableArray array];
	
    for (int i = 0; i < [poly count]; ++i) {
        if (isReflex(poly, i)) {
			[info->reflexVertices push: [poly objectAtIndex: i]];
            upperDist = lowerDist = FLT_MAX;
            for (int j = 0; j < [poly count]; ++j) {
                if (left([poly at: i - 1], [poly at: i], [poly at: j])
					&& rightOn([poly at: i - 1], [poly at: i], [poly at: j - 1])) { // if line intersects with an edge
                    p = intersection([poly at: i - 1], [poly at: i], [poly at: j], [poly at: j - 1]); // find the point of intersection
                    if (right([poly at: i + 1], [poly at: i], p)) { // make sure it's inside the poly
                        d = sqdist([poly objectAtIndex: i], p);
                        if (d < lowerDist) { // keep only the closest intersection
                            lowerDist = d;
                            lowerInt = [BpPoint pointWithPoint: p];
                            lowerIndex = j;
                        }
                    }
                }
                if (left([poly at: i + 1], [poly at: i], [poly at: j + 1])
					&& rightOn([poly at: i + 1], [poly at: i], [poly at: j])) {
                    p = intersection([poly at: i + 1], [poly at: i], [poly at: j], [poly at: j + 1]);
                    if (left([poly at: i - 1], [poly at: i], p)) {
                        d = sqdist([poly objectAtIndex: i], p);
                        if (d < upperDist) {
                            upperDist = d;
                            upperInt = [BpPoint pointWithPoint: p];
                            upperIndex = j;
                        }
                    }
                }
            }
            // if there are no vertices to connect to, choose a point in the middle
            if (lowerIndex == (upperIndex + 1) % [poly count]) {
                printf("Case 1: Vertex(%d), lowerIndex(%d), upperIndex(%d), poly.size(%d)\n", i, lowerIndex, upperIndex, (int) [poly count]);
				p = [BpPoint pointWithX:(lowerInt.x + upperInt.x) / 2 Y:(lowerInt.y + upperInt.y) / 2];
                [info->steinerPoints push: p];
				
                if (i < upperIndex) {
//                    lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + upperIndex + 1);
					[lowerPoly appendSubarray: poly fromIndex: i toIndex: upperIndex + 1];
                    [lowerPoly push: p];
                    [upperPoly push: p];
                    if (lowerIndex != 0) //upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.end());
						[upperPoly appendSubarray: poly fromIndex: lowerIndex toIndex: (int)[poly count]];
//                    upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);
					[upperPoly appendSubarray: poly fromIndex:0 toIndex: i + 1];
                } else {
                    if (i != 0) //lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.end());
						[lowerPoly appendSubarray: poly fromIndex:i toIndex: (int)[poly count]];
//                    lowerPoly.insert(lowerPoly.end(), poly.begin(), poly.begin() + upperIndex + 1);
					[lowerPoly appendSubarray: poly fromIndex: 0 toIndex: upperIndex + 1];
                    [lowerPoly push: p];
                    [upperPoly push: p];
//                    upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.begin() + i + 1);
					[upperPoly appendSubarray: poly fromIndex:lowerIndex toIndex:i + 1];
                }
            } else if ( poly != nil) {
                // connect to the closest point within the triangle
                printf("Case 2: Vertex(%d), closestIndex(%d), poly.size(%d)\n", i, closestIndex, (int)[poly count]);
				
                if (lowerIndex > upperIndex) {
                    upperIndex += [poly count];
                }
                closestDist = FLT_MAX;
                for (int j = lowerIndex; j <= upperIndex; ++j) {
                    if (leftOn([poly at: i - 1], [poly at: i], [poly at: j])
						&& rightOn([poly at: i + 1], [poly at: i], [poly at: j])) {
                        d = sqdist([poly at: i], [poly at: j]);
                        if (d < closestDist) {
                            closestDist = d;
                            closestVert = [poly at: j];
                            closestIndex = j % (int)[poly count];
                        }
                    }
                }
				
                if (i < closestIndex) {
//                    lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + closestIndex + 1);
					[lowerPoly appendSubarray: poly fromIndex: i toIndex: closestIndex + 1];
                    if (closestIndex != 0) //upperPoly.insert(upperPoly.end(), poly.begin() + closestIndex, poly.end());
						[upperPoly appendSubarray: poly fromIndex: closestIndex toIndex: (int)[poly count]];
//                    upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);
					[upperPoly appendSubarray: poly fromIndex: 0 toIndex: i + 1];
                } else {
                    if (i != 0) //lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.end());
						[lowerPoly appendSubarray: poly fromIndex:i toIndex:(int)[poly count]];
//                    lowerPoly.insert(lowerPoly.end(), poly.begin(), poly.begin() + closestIndex + 1);
					[lowerPoly appendSubarray: poly fromIndex: 0 toIndex: closestIndex + 1];
//                    upperPoly.insert(upperPoly.end(), poly.begin() + closestIndex, poly.begin() + i + 1);
					[upperPoly appendSubarray: poly fromIndex: closestIndex toIndex: i + 1];
                }
            }
			
            // solve smallest poly first
            if ([lowerPoly count] < [upperPoly count]) {
                decomposePoly(lowerPoly, info);
                decomposePoly(upperPoly, info);
            } else {
                decomposePoly(upperPoly, info);
                decomposePoly(lowerPoly, info);
            }
            return;
        }
    }
	if ( poly != nil)
		[info->polys push: poly];	
}

NSMutableArray *bayazitCalculateShapes( NSMutableArray *vertices)
{
	bayazitInfoType info;
	info.polys = [NSMutableArray array];
	info.steinerPoints = [NSMutableArray array];
	info.reflexVertices	= [NSMutableArray array];
	makeCCW(&vertices);
	if ( validateVertices( vertices) == 0)
		decomposePoly( vertices, &info);
	return info.polys;
}

Example usage:

if ( [vertices count] > 2) {
	self.autoVertices = bayazitCalculateShapes( vertices);
	if ( self.autoVertices && [self.autoVertices count] > 0) {
		for ( NSMutableArray *polygon in self.autoVertices)
		{
			for ( int i = 0; i < [polygon count]; i++)
			{
				BpPoint *point = [polygon objectAtIndex:i];
				BpPoint *newPoint = [BpPoint pointWithX:point.x *self.vertexScale
													  Y:point.y * self.vertexScale];
				
				[polygon replaceObjectAtIndex: i withObject: newPoint];
			}
		}
	}
	[self densityChanged: densityField];
}

Swift Version

Finally, here is my naïve Swift conversion of my Objective-C version of the Bayazit solution. The Swift version should correctly handle line segments formed between the first and last vertices. Implemented 2020-02-08.

//
//  PolygonDecomposer.swift
//  NathanMacOSSpriteKit
//
//  Created by Nathan Lamont on 2/5/20.
//  Copyright © 2020 Nathan Lamont. All rights reserved.
//  Swift version of Nathan Lamont Objective-C version of
//  Bayazit Solution
//  https://mpen.ca/406/bayazit
//  with portions of Angelov solution (validation only)
// https://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/
//  See
//  https://www.nathanlamont.com/notes-to-self/break-a-concave-shape-into-multiple-convex-shapes/


import Foundation

struct BayazitInfo {
    var polys: [[CGPoint]] = []
    var steinerPoints: [CGPoint] = []
    var reflexVertices: [CGPoint] = []
}

// https://stackoverflow.com/questions/25329186/safe-bounds-checked-array-lookup-in-swift-through-optional-bindings
extension Array {

    /// Returns the element at the specified index if it is within bounds, otherwise nil.
    subscript (safe index: Index) -> Element? {
        return indices.contains(index) ? self[index] : nil
    }
    subscript (wrap index: Int) -> Element {
        if (index < 0) {
            return self[index % count + count]
        } else {
            return self[index % self.count]
        }
    }
}

class PolygonDecomposer {
    static let noise:CGFloat = 0.01
    
    static func area(a: CGPoint, b: CGPoint, c: CGPoint) -> CGFloat {

        let t = (b.x - a.x) * (c.y - a.y)
        let u = (c.x - a.x) * (b.y - a.y)
        return t - u
    }
    
    static func left(a: CGPoint, b: CGPoint, c: CGPoint) -> Bool {
        return area(a: a, b: b, c: c) > 0
    }
    
    static func leftOn(a: CGPoint, b: CGPoint, c: CGPoint) -> Bool {
        return area(a: a, b: b, c: c) >= 0
    }

    static func right(a: CGPoint, b: CGPoint, c: CGPoint) -> Bool {
        return area(a: a, b: b, c: c) < 0
    }
    
    static func rightOn(a: CGPoint, b: CGPoint, c: CGPoint) -> Bool {
        return area(a: a, b: b, c: c) <= 0
    }

    static func collinear(a: CGPoint, b: CGPoint, c: CGPoint) -> Bool {
        return area(a: a, b: b, c: c) == 0
    }
    
    static func sqdist(a: CGPoint, b: CGPoint) -> CGFloat {
        let dx = b.x - a.x
        let dy = b.y - a.y
        return dx * dx + dy * dy
    }
    
    static func eq(a: CGFloat, b: CGFloat) -> Bool {
        return abs(a - b) <= 1e-8
    }
    
    static func makeCounterClockwise(polygon: inout [CGPoint]) {
        // find bottom right point
        var bri = 0
        var brp = polygon.count > 0 ? polygon[0] : CGPoint(x: 0.0, y: 0.0)
        
        for (i, p) in polygon.enumerated() {
            if (p.y < brp.y || (p.y == brp.y && p.x > brp.x)) {
                bri = i
                brp = p
            }
        }
        let a = polygon[wrap: bri - 1]
        let c = polygon[wrap: bri + 1]
        if (!left(a: a, b: brp, c: c)) {
            polygon.reverse()
        }
    }
    
    static func isReflex(polygon: [CGPoint], index: Int) -> Bool {
        return right(
            a: polygon[wrap: index - 1],
            b: polygon[wrap: index],
            c: polygon[wrap: index + 1]
        )
    }
    
    static func intersection(p1: CGPoint, p2: CGPoint, q1: CGPoint, q2: CGPoint) -> CGPoint {
        var i = CGPoint(x: 0.0, y: 0.0)
        let a1 = p2.y - p1.y
        let b1 = p1.x - p2.x
        let c1 = a1 * p1.x + b1 * p1.y
        let a2 = q2.y - q1.y
        let b2 = q1.x - q2.x
        let c2 = a2 * q1.x + b2 * q1.y
        let det = a1 * b2 - a2 * b1
        if (!eq(a:det, b:0.0)) { // lines are not parallel
            i.x = (b2 * c1 - b1 * c2) / det
            i.y = (a1 * c2 - a2 * c1) / det
        }
        return i
    }
    
    static func det(p1: CGPoint, p2: CGPoint, p3: CGPoint) -> CGFloat {
        return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.y * p2.x - p2.y * p3.x - p3.y * p1.x
    }
    
    static func isOnSegment(pp: CGPoint, p1: CGPoint, p2: CGPoint) -> Bool {
        let b1 = ((((p1.x + noise) >= pp.x) && (pp.x >= (p2.x - noise))) ||
        (((p1.x - noise) <= pp.x) && (pp.x <= (p2.x + noise))))
        let b2 = ((((p1.y + noise) >= pp.y) && (pp.y >= (p2.y - noise))) ||
                      (((p1.y - noise) <= pp.y) && (pp.y <= (p2.y + noise))))
        return (b1 && b2 && isOnLine(pp: pp, p1: p1, p2: p2))
    }
    
    static func isOnLine(pp: CGPoint, p1: CGPoint, p2: CGPoint) -> Bool {
        if (((p2.x - p1.x) > noise) || ((p1.x - p2.x > noise))) {
            let a = (p2.y - p1.y) / (p2.x - p1.x)
            let possibleY = a * (pp.x - p1.x) + p1.y
            let diff = (possibleY > pp.y) ? (possibleY - pp.y) : (pp.y - possibleY)
            return ( diff < noise);
        }
        return (((pp.x - p1.x) < noise) || ((p1.x - pp.x < noise)))
    }
    
    static func hitSegment(p1: CGPoint, p2: CGPoint, p3: CGPoint, p4: CGPoint) -> Bool {
        let t1 = p3.x - p1.x, t2 = p3.y - p1.y, t3 = p2.x - p1.x, t4 = p2.y - p1.y
        let t5 = p4.x - p3.x, t6 = p4.y - p3.y, t7 = t4 * t5 - t3 * t6
        let a = (t5 * t2 - t6 * t1) / t7
        let pp = CGPoint(x: p1.x + a * t3, y: p1.y + a * t4)
        
        return (isOnSegment(pp: pp, p1: p1, p2: p2) && isOnSegment(pp: pp, p1: p3, p2: p4))
    }
    
    static func validateVertices(vertices: [CGPoint]) -> Int {
        var result = 0
        var fl2 = false
        let n = vertices.count
        
        if (n < 3) {
            return 1
        }
        for (i, pi) in vertices.enumerated() {
            let i2 = (i < (n - 1)) ? (i + 1) : (0)
            let i3 = (i > 0) ? (i - 1) : (n - 1)
            var fl = false
            for (j, pj) in vertices.enumerated() {
                if (j != i && j != i2) {
                    if (!fl) {
                        let d = det(p1: pi, p2: vertices[i2], p3: vertices[j])
                        if (d > 0.0) {
                            fl = true
                        }
                    }
                    
                    if (j != i3) {
                        let j2 = (j < (n - 1)) ? (j + 1) : (0)
                        if (hitSegment(p1: pi, p2: vertices[i2], p3: pj, p4: vertices[j2])) {
                            result = 1
                        }
                    }
                }
            }
            if (!fl) {
                fl2 = true
            }
        }
        if (fl2) {
            if (result == 1) {
                result = 3
            } else {
                result = 2
            }
        }
        return result
    }
    
    static func decomposePoly(poly: [CGPoint], info: inout BayazitInfo) {
        var p = CGPoint(x:0, y:0)
        var lowerIndex = 0
        var upperIndex = 0
        var lowerPoly: [CGPoint] = []
        var upperPoly: [CGPoint] = []
        
        for (i, pi) in poly.enumerated() {
            if (isReflex(polygon: poly, index: i)) {
                var upperDist = CGFloat.greatestFiniteMagnitude
                var lowerDist = upperDist
                
                info.reflexVertices.append(pi)
                for (j, pj) in poly.enumerated() {
                    // if line intersects with an edge
                    if (left(a: poly[wrap: i - 1], b: pi, c: pj) &&
                        rightOn(a: poly[wrap: i - 1], b: pi, c: poly[wrap: j - 1])) {
                        p = intersection(p1: poly[wrap: i - 1], p2: pi, q1: pj, q2: poly[wrap: j - 1])
                        // make sure it's inside the poly
                        if (right(a: poly[wrap: i + 1], b: pi, c: p)) {
                            let d = sqdist(a: pi, b: p)
                            if (d < lowerDist) {
                                lowerDist = d
                                lowerInt = p
                                lowerIndex = j
                            }
                        }
                    }
                    if (left(a: poly[wrap: i + 1], b: pi, c: poly[wrap: j + 1]) &&
                        rightOn(a: poly[wrap: i + 1], b: pi, c: pj)) {
                        let p = intersection(p1: poly[wrap: i + 1], p2: pi, q1: pj, q2: poly[wrap: j + 1])
                        if (left(a: poly[wrap: i - 1], b: pi, c: p)) {
                            let d = sqdist(a: pi, b: p)
                            upperDist = d
                            upperInt = p
                            upperIndex = j
                        }
                    }
                }

                if (lowerIndex == (upperIndex + 1 % poly.count)) {
                    info.steinerPoints.append(p)
                    if (i < upperIndex) {
                        lowerPoly.append(contentsOf: poly[i..<(upperIndex + 1)])
                        lowerPoly.append(p)
                        upperPoly.append(p)
                        if (lowerIndex != 0) {
                            upperPoly.append(
                                contentsOf: poly[lowerIndex..<poly.count]
                            )
                        }
                        upperPoly.append(contentsOf: poly[0..<(i + 1)])
                    } else {
                        if (i != 0) {
                            lowerPoly.append(contentsOf: poly[i..<poly.count])
                        }
                        lowerPoly.append(contentsOf: poly[0..<upperIndex + 1])
                        lowerPoly.append(p)
                        upperPoly.append(p)
                        upperPoly.append(contentsOf: poly[lowerIndex..<(i + 1)])
                    }
                } else if (poly.count > 0) {
                    var closestDist = CGFloat.greatestFiniteMagnitude
                    var closestIndex = 0
                    if (lowerIndex > upperIndex) {
                        upperIndex += poly.count
                    }
                    for j in lowerIndex...upperIndex {
                        if (leftOn(a: poly[wrap: i - 1], b: poly[i], c: poly[j]) &&
                            rightOn(a: poly[wrap: i + 1], b: poly[i], c: poly[j])) {
                            let d = sqdist(a: poly[i], b: poly[j])
                            
                            if (d < closestDist) {
                                closestDist = d
                                closestIndex = j % poly.count
                            }
                        }
                    }
                    if (i < closestIndex) {
                        lowerPoly.append(contentsOf: poly[i...closestIndex])
                        if (closestIndex != 0) {
                            upperPoly.append(contentsOf: poly[closestIndex..<poly.count])
                        }
                        upperPoly.append(contentsOf: poly[0...i])
                    } else {
                        if (i != 0) {
                            lowerPoly.append(contentsOf: poly[i..<poly.count])
                        }
                        lowerPoly.append(contentsOf: poly[0...closestIndex])
                        upperPoly.append(contentsOf: poly[closestIndex...i])
                    }
                }
                if (lowerPoly.count < upperPoly.count) {
                    decomposePoly(poly: lowerPoly, info: &info)
                    decomposePoly(poly: upperPoly, info: &info)
                } else {
                    decomposePoly(poly: upperPoly, info: &info)
                    decomposePoly(poly: lowerPoly, info: &info)
                }
                return
            }
        }
        if (poly.count > 0) {
            info.polys.append(poly)
        }
    }
    static func anyPolyToConvexPolys(poly: [CGPoint]) -> [[CGPoint]] {
        var info = BayazitInfo()
        var pc = poly
        if (pc.count > 2 && pc[0] == pc[pc.count - 1]) {
            pc.removeLast()
        }
        
        if (validateVertices(vertices: pc) != 0) {
            return []
        }
        makeCounterClockwise(polygon: &pc)
        decomposePoly(poly: pc, info: &info)
        return info.polys
    }
}