You appeared to have created an Objective C version of the "Angelov" solution, but abandoned it for a different approach (Bayazit). See below.
(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.");
}
}
}
//
// 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.mThe 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];
}
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
}
}