Reduce the number of points in a polygon with the Ramer-Douglas-Peucker algorithm

March 4, 2013 • Actionscript 3, Flash by Emanuele Feronato • 1 Comment

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;
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

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.

Rate this post: 1 Star

(9 votes, average: 3.78 out of 5)

Loading ...

Flash Templates provided by Template Monster are pre-made web design products developed using Flash technology.
They can be easily customized to meet the unique requirements of your project.

Be my fan on Facebook and follow me on Twitter! Exclusive content for my Facebook fans and Twitter followers

This post has one comment

Flo - derhess.de

on March 7, 2013 at 1:10 pm

Hi,

nice tutorial, like the idea very much. For reducing points I also like the
Lang Simplification and McMaster’s Slide Averaging Algorithm
http://www.motiondraw.com/blog/?p=50

another approach is the Douglas Peuker Line Generalization
http://lostinactionscript.com/2007/07/11/douglas-peuker-line-generalization/
but the result is not so well in my opinion

however very useful topic for game editors and other stuff :-)

Emanuele Feronato

italian geek and PROgrammer

Reduce the number of points in a polygon with the Ramer-Douglas-Peucker algorithm

This post has one comment

Flo - derhess.de