Hi. I want to turn a concave polygon into a set of convex ones. Does anyone know a good tutorial for implementing that. Or a nice lib that I can use with flashpunk that does that?
I need it because I have implemented polygon intersection check using Separating Axis Theorem, and as it only works with convex polygons, I need to divide my concave polygons into convex ones so I can do the collision check.
This is for Box2D but might be a good starting point: http://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/
More links you may find useful:
I’m also really curious to take a look at your SAT implementation… could I? ;D
There are many approaches to solving this problem. Here are a few.
@azrafe7 your hxGeomAlgo is awesome! It was really really handy for me. I would take a lot of time to implement polygon decomposition myself, and this saved me a lot of time. And the best thing is that you can automatically get the points of a polygon from a png. This was the next thing I would have to see, and your lib had it, that’s really nice. It’s working nicely.
I’ll post my SAT here, since you want to see. Most of the code is based on this article. The only lib I’m using is a Vec2 lib. Please feel free to point any mistake I could have done.
/**
* Returns true if two polygons overlap. The polygon must be given as an Array of Points (flash.geom.Point).
* @param poly1 The first polygon.
* @param poly2 The second polygon.
*/
public function sat(poly1:Array, poly2:Array):Boolean {
var currVertex:Point, nextVertex:Point, axis:Vec2, proj1:Array, proj2:Array;
//test all the edges of the first polygon
for ( var i1:int = 0; i1 < poly1.length; i1++) {
currVertex = poly1[i1] as Point;
nextVertex = i1 == poly1.length - 1? poly1[0] as Point:
poly1[i1 + 1] as Point;
//direction the current edge is pointing at
axis = new Vec2(currVertex.x - nextVertex.x, currVertex.y - nextVertex.y);
axis.perpLeftSelf();
//projections of both polygons
proj1 = project(poly1, axis);
proj2 = project(poly2, axis);
//if the two projections are not overlapping, the polygons are not overlapping
if( ! overlap(proj1, proj2) ){
return false;
}
}
//teste all teh edges of the second polygon
for ( var i2:int = 0; i2 < poly2.length; i2++) {
currVertex = poly2[i2] as Point;
nextVertex = i2 == poly2.length - 1? poly2[0] as Point:
poly2[i2 + 1] as Point;
//direction the current edge is pointing at
axis = new Vec2(currVertex.x - nextVertex.x, currVertex.y - nextVertex.y);
axis.perpLeftSelf();
//projections of both polygons
proj1 = project(poly1, axis);
proj2 = project(poly2, axis);
//if the two projections are not overlapping, the polygons are not overlapping
if( ! overlap(proj1, proj2) ){
return false;
}
}
//if no projections are separated, the polygons are colliding
return true;
}
/**
* Returns true if a polygon and a circle overlap. The polygon must be given as an Array of Points (flash.geom.Point).
* For the circle, a center point and a radius must be given.
* @param poly The polygon.
* @param circleCenter The center point of the circle.
* @param circleRadius The radius of the circle.
*/
public function circleSat(poly:Array, circleCenter:Point, circleRadius:Number):Boolean {
var currVertex:Point, nextVertex:Point, axis:Vec2, proj1:Array, proj2:Array;
//test all the edges of the polygon.
for ( var i1:int = 0; i1 < poly.length; i1++) {
currVertex = poly[i1] as Point;
nextVertex = i1 == poly.length - 1? poly[0] as Point:
poly[i1 + 1] as Point;
//direction the current edge is pointing at
axis = new Vec2(currVertex.x - nextVertex.x, currVertex.y - nextVertex.y);
axis.perpLeftSelf();
//projection of the polygon
proj1 = project(poly, axis);
//projection of the circle
proj2 = projectCircle(circleCenter, circleRadius, axis);
//if the two projections are not overlapping, the polygon and the circle are not overlapping
if( ! overlap(proj1, proj2) ){
return false;
}
}
//get also the axis that points from the circle to the closest vertex
var closest:Point = closestVertex(poly, circleCenter);
axis = new Vec2(closest.x - circleCenter.x, closest.y - circleCenter.y);
//and see if the projections on that vertex overlap
if( ! overlap(project(poly, axis), projectCircle(circleCenter, circleRadius, axis)) ){
return false;
}
//if no projections are separated, the circle and the polygon are overlapping.
return true;
}
//projects a polygon
private function project(poly:Array, axis:Vec2):Array {
axis.normalizeSelf();
var min:Number = axis.dotXY( (poly[0] as Point).x, (poly[0] as Point).y );
var max:Number = min;
var proj:Number = 0;
for each( var p:Point in poly ){
proj = axis.dotXY(p.x, p.y);
if(proj < min){
min = proj;
}
if(proj > max){
max = proj;
}
}
return new Array(min, max);
}
//projects a circle
private function projectCircle(circleCenter:Point, circleRadius:Number, axis:Vec2):Array {
var centerDot:Number = axis.dotXY( circleCenter.x, circleCenter.y );
return new Array(centerDot - circleRadius, centerDot + circleRadius);
}
//returns the closest vertex to a circle
private function closestVertex(poly:Array, cirlceCenter:Point):Point {
var distance:Number = Number.MAX_VALUE;
var closest:Point;
for each (var p:Point in poly){
var testDistance:Number = eDistance(p.x, p.y, cirlceCenter.x, cirlceCenter.y);
if( testDistance < distance){
distance = testDistance;
closest = p;
}
}
return closest;
}
//returns true if a point is between two other points, in an unidimensional space
private function contains(n:Number, range:Array):Boolean {
return n >= range[0] && n <= range[1];
}
//returns true if two projections are overlapping
private function overlap(proj1:Array, proj2:Array):Boolean {
if (contains(proj1[0], proj2) ) return true;
else if (contains(proj1[1], proj2) ) return true;
else if (contains(proj2[0], proj1) ) return true;
else if (contains(proj2[1], proj1) ) return true;
return false;
}
//euclidean distance
private function eDistance(x1:Number, y1:Number, x2:Number, y2:Number):Number {
return Math.sqrt( (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) );
}
Also, thanks a lot for your sugestions @zachwlewis and @Ultima2876. I had already learned the concepts and all, but I was looking for something done already.
Glad to hear my little incomplete lib has been of help! 
Oh… and I just realized that the code you linked to (Polygonal Collision Detection) is the same starting point used by HaxePunk (and in turn the upcoming FlashPunk) implementation.
I’ve tested your code and seems to work fine! (I seem to recall there was a subtle bug in the circleSat algo, but haven’t been able to reproduce it with your code, so all is good).
The only things I can add is that it could be slighlty optimized by decreasing the number of allocations of new objects, and that you’re currently forced to do all the offsetting/rotation manually if you need to move/rotate the polygon across the screen.
@azrafe7, take a look at this:
There are some missing parts and some are overlapping. Do you have any idea why this is happening? I was just testing, and I’m not actually gonna have such complex polygons for my game, but I want to be aware of the limitations of this tool so I can avoid possible issues. .
Yeah, my first impression was exactly like @Ultima2876’s: WTF?! 
Are you using as3GeomAlgo, or hxGeomAlgo directly?
I’ve only tested your png directly with the haxe lib so far, and it actually seems that BayazDecomp doesn’t play well, so you’ve probably encountered some bugs in my implementation. By the way ECDecomp seems to work well with it (although it obviously uses more polys to decompose the original image, but it is far more tested than the other - more performant - algo).
Can you please test and report if the previous steps are behaving correctly (MarchingSquares and DougPeuck)?
Also bear in mind that, unlike my lib (which is somewhat new/immature - although useful, as it already served me well for some little projects of mine), Nape is a production ready/well-tested solution for decomposing polys on-the-fly (and much much more).
Really hope to get some feedback and kill some bugs
Cheers!
EDIT: ECDecomp.png (lots of polys I know, but looks correct)
Haha, I’ve seen more complex polygons than this when I was researching. I was just trying to see If it would still work if I made some things, like having a very thin part, with a very low angle vertex, and making it so that if there was a line passing through the polygon, it would pass through a lot of edges, and so on.
Anyway, @azrafe7, I used the as3GeomAlgo. Also, I’ve tested without the Bayazit, and indeed, the MarchingSquares and DougPeuck are working correctly. The problem seems to be with the Bayazit.
Also. I was wondering how much work you had to take my polygon from that image and take the chess background away. I would have given you if you asked =D
Nah, it actually took me less than 5 min to remove it using the magic-wand tool and a proper tolerance.
By the way I’ll look further into Bayazit code and see if I can fix it. Thanks for the feedback!
Hey @Linck5, some bad news and some good ones…
Bad first… Had time to recheck my Bayazit code and compare it to the original one in search for obvious mistakes, but couldn’t find any. So I decided to directly run the original author’s c++ code on the shape above, and discovered that it fails in the same spot. I’ll try to contact him and see if he’s willing to help in solving the issue (but this could prove a difficult task, also because his site is currently offline and haven’t found a way to contact him yet).
The good news is that I’ve finished porting an awesome poly-decomp algo from Snoeyink and Keil that should guarantee a minimum number of decomposing polygons (at the cost of increased computation time). (Spent quite some time fixing bugs on my side, but all seems good so far).
Haven’t yet updated the lib on github. It’ll need a round of tests and refactoring before sitting there, hehe. 
Here’s a snapshot of using it on the test shape (w/DouglasPeucker epsilon to 1.5):
Also… if you have any other complex image to test at hand please send it my way.
