Talking about Actionscript 3 and Flash.
Some of you already saw the potential of using marching squares algorithm to trace the contour of an image, because once you have a the contour of an image, it’s easy to convert it in a Box2D shape.
The problem is the resulting shape has too much points, the logo rendered in the example counts 2,200 points, way too much.
We really need to reduce the number of points. That’s where Ramer-Douglas-Peucker algorithm comes to help us.
The purpose of the algorithm is, given a curve composed of line segments, to find a similar curve with fewer points. The algorithm defines ‘dissimilar’ based on the maximum distance between the original curve and the simplified curve. The simplified curve consists of a subset of the points that defined the original curve.
Marius Karthaus wrote a nice javascript example of the RDP algorithm I ported to AS3 adding it to previous example, see highlighted lines:
package {
import flash.display.Sprite;
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.geom.Matrix;
import flash.geom.Point;
public class Main extends Sprite {
private var bitmapData:BitmapData=new BitmapData(640,480,true,0x00000000);
// tolerance is the amount of alpha for a pixel to be considered solid
private var tolerance:Number=0x01;
public function Main() {
// adding a png image with transparency
bitmapData.draw(new Logo(278,429),new Matrix(1,0,0,1,20,40));
var bitmap:Bitmap=new Bitmap(bitmapData);
addChild(bitmap);
bitmap.alpha=0.5
// at the end of this function, marchingVector will contain the points tracing the contour
var marchingVector:Vector.<Point>=marchingSquares(bitmapData);
marchingVector=RDP(marchingVector,0.50);
var canvas:Sprite=new Sprite();
addChild(canvas);
canvas.graphics.moveTo(marchingVector[0].x+320,marchingVector[0].y);
for (var i:Number=0; i<marchingVector.length; i++) {
canvas.graphics.lineStyle(2,0xffffff);
canvas.graphics.lineTo(marchingVector[i].x+320,marchingVector[i].y);
canvas.graphics.lineStyle(1,0xff0000);
canvas.graphics.drawCircle(marchingVector[i].x+320,marchingVector[i].y, 2);
}
canvas.graphics.lineStyle(2,0xffffff);
canvas.graphics.lineTo(marchingVector[0].x+320,marchingVector[0].y);
}
public function RDP(v:Vector.<Point>,epsilon:Number):Vector.<Point> {
var firstPoint:Point=v[0];
var lastPoint:Point=v[v.length-1];
if (v.length<3) {
return v;
}
var index:Number=-1;
var dist:Number=0;
for (var i:Number=1; i<v.length-1; i++) {
var cDist:Number=findPerpendicularDistance(v[i],firstPoint,lastPoint);
if (cDist>dist) {
dist=cDist;
index=i;
}
}
if (dist>epsilon) {
var l1:Vector.<Point>=v.slice(0,index+1);
var l2:Vector.<Point>=v.slice(index);
var r1=RDP(l1,epsilon);
var r2=RDP(l2,epsilon);
var rs:Vector.<Point>=r1.slice(0,r1.length-1).concat(r2);
return rs;
}
else {
return new Vector.<Point>(firstPoint,lastPoint);
}
return null;
}
private function findPerpendicularDistance(p:Point, p1:Point,p2:Point) {
var result;
var slope;
var intercept;
if (p1.x==p2.x) {
result=Math.abs(p.x-p1.x);
}
else {
slope = (p2.y - p1.y) / (p2.x - p1.x);
intercept=p1.y-(slope*p1.x);
result = Math.abs(slope * p.x - p.y + intercept) / Math.sqrt(Math.pow(slope, 2) + 1);
}
return result;
}
public function marchingSquares(bitmapData:BitmapData):Vector.<Point> {
var contourVector:Vector.<Point> = new Vector.<Point>();
// this is the canvas we'll use to draw the contour
var canvas:Sprite=new Sprite();
addChild(canvas);
canvas.graphics.lineStyle(2,0x00ff00);
// getting the starting pixel;
var startPoint:Point=getStartingPixel(bitmapData);
// if we found a starting pixel we can begin
if (startPoint!=null) {
// moving the graphic pen to the starting pixel
canvas.graphics.moveTo(startPoint.x,startPoint.y);
// pX and pY are the coordinates of the starting point;
var pX:Number=startPoint.x;
var pY:Number=startPoint.y;
// stepX and stepY can be -1, 0 or 1 and represent the step in pixels to reach
// next contour point
var stepX:Number;
var stepY:Number;
// we also need to save the previous step, that's why we use prevX and prevY
var prevX:Number;
var prevY:Number;
// closedLoop will be true once we traced the full contour
var closedLoop:Boolean=false;
while (!closedLoop) {
// the core of the script is getting the 2x2 square value of each pixel
var squareValue:Number=getSquareValue(pX,pY);
switch (squareValue) {
/* going UP with these cases:
+---+---+ +---+---+ +---+---+
| 1 | | | 1 | | | 1 | |
+---+---+ +---+---+ +---+---+
| | | | 4 | | | 4 | 8 |
+---+---+ +---+---+ +---+---+
*/
case 1 :
case 5 :
case 13 :
stepX=0;
stepY=-1;
break;
/* going DOWN with these cases:
+---+---+ +---+---+ +---+---+
| | | | | 2 | | 1 | 2 |
+---+---+ +---+---+ +---+---+
| | 8 | | | 8 | | | 8 |
+---+---+ +---+---+ +---+---+
*/
case 8 :
case 10 :
case 11 :
stepX=0;
stepY=1;
break;
/* going LEFT with these cases:
+---+---+ +---+---+ +---+---+
| | | | | | | | 2 |
+---+---+ +---+---+ +---+---+
| 4 | | | 4 | 8 | | 4 | 8 |
+---+---+ +---+---+ +---+---+
*/
case 4 :
case 12 :
case 14 :
stepX=-1;
stepY=0;
break;
/* going RIGHT with these cases:
+---+---+ +---+---+ +---+---+
| | 2 | | 1 | 2 | | 1 | 2 |
+---+---+ +---+---+ +---+---+
| | | | | | | 4 | |
+---+---+ +---+---+ +---+---+
*/
case 2 :
case 3 :
case 7 :
stepX=1;
stepY=0;
break;
case 6 :
/* special saddle point case 1:
+---+---+
| | 2 |
+---+---+
| 4 | |
+---+---+
going LEFT if coming from UP
else going RIGHT
*/
if (prevX==0&&prevY==-1) {
stepX=-1;
stepY=0;
}
else {
stepX=1;
stepY=0;
}
break;
case 9 :
/* special saddle point case 2:
+---+---+
| 1 | |
+---+---+
| | 8 |
+---+---+
going UP if coming from RIGHT
else going DOWN
*/
if (prevX==1&&prevY==0) {
stepX=0;
stepY=-1;
}
else {
stepX=0;
stepY=1;
}
break;
}
// moving onto next point
pX+=stepX;
pY+=stepY;
// saving contour point
contourVector.push(new Point(pX, pY));
prevX=stepX;
prevY=stepY;
// drawing the line
canvas.graphics.lineTo(pX,pY);
// if we returned to the first point visited, the loop has finished;
if (pX==startPoint.x&&pY==startPoint.y) {
closedLoop=true;
}
}
}
return contourVector;
}
private function getStartingPixel(bitmapData:BitmapData):Point {
// finding the starting pixel is a matter of brute force, we need to scan
// the image pixel by pixel until we find a non-transparent pixel
var zeroPoint:Point=new Point(0,0);
var offsetPoint:Point=new Point(0,0);
for (var i:Number=0; i<bitmapData.height; i++) {
for (var j:Number=0; j<bitmapData.width; j++) {
offsetPoint.x=j;
offsetPoint.y=i;
if (bitmapData.hitTest(zeroPoint,tolerance,offsetPoint)) {
return offsetPoint;
}
}
}
return null;
}
private function getSquareValue(pX:Number,pY:Number):Number {
/*
checking the 2x2 pixel grid, assigning these values to each pixel, if not transparent
+---+---+
| 1 | 2 |
+---+---+
| 4 | 8 | <- current pixel (pX,pY)
+---+---+
*/
var squareValue:Number=0;
// checking upper left pixel
if (getAlphaValue(bitmapData.getPixel32(pX-1,pY-1))>=tolerance) {
squareValue+=1;
}
// checking upper pixel
if (getAlphaValue(bitmapData.getPixel32(pX,pY-1))>tolerance) {
squareValue+=2;
}
// checking left pixel
if (getAlphaValue(bitmapData.getPixel32(pX-1,pY))>tolerance) {
squareValue+=4;
}
// checking the pixel itself
if (getAlphaValue(bitmapData.getPixel32(pX,pY))>tolerance) {
squareValue+=8;
}
return squareValue;
}
private function getAlphaValue(n:Number):Number {
// given an ARGB color value, returns the alpha 0 -> 255
return n >> 24 & 0xFF;
}
}
}
Everything is ruled by the second argument of RDP function, usually called epsilon, which in this case should run from 0.2 to 0.8.
Have a look at the final example, traced on the right of the stage, made with just 343 points with a 0.50 epsilon value:
No need to download anything, just copy-paste this code in the main class of the original example.
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.