Skip to content

Instantly share code, notes, and snippets.

@GoToLoop
Last active August 28, 2019 20:17
Show Gist options
  • Save GoToLoop/a5db257be4d7756a00220a3e97066dd5 to your computer and use it in GitHub Desktop.
Save GoToLoop/a5db257be4d7756a00220a3e97066dd5 to your computer and use it in GitHub Desktop.
Ramer–Douglas–Peucker Algorithm
height: 600
scrolling: no
border: yes
license: cc-by-4.0
static final String[] ERRORS = {
"Polygon's newSize parameter can't be less than 2!",
"Parameter dots[] must contain at least 2 PVector objects!",
"Parameter epsilon can't be a negative value!"
};
static final PVector[] reducePolygon(final PVector[] dots, final int newSize) {
if (newSize < 2) throw new Error(ERRORS[0]);
PVector[] reduced;
int ep = 0;
do {
reduced = shortDistRDP(dots, ep++);
if (DEBUG) println("Step: " + (ep - 1) + "\t\tSize: " + reduced.length);
} while (reduced.length > newSize);
return reduced;
}
static final PVector[] shortDistRDP(final PVector[] dots, final float epsilon) {
if (dots == null || dots.length < 2) throw new Error(ERRORS[1]);
if (epsilon < 0) throw new Error(ERRORS[2]);
if (dots.length == 2) return (PVector[]) expand(dots, dots.length);
final int last = dots.length - 1;
final PVector head = dots[0], tail = dots[last];
float maxDistSq = 0;
int idx = -1;
for (int i = 1; i < last; ++i) {
final float currDistSq = dotLineSq(dots[i], head, tail);
if (currDistSq > maxDistSq) {
maxDistSq = currDistSq;
idx = i;
}
}
if (sqrt(maxDistSq) > epsilon) {
final PVector[]
recurResL = shortDistRDP((PVector[]) subset(dots, 0, idx + 1), epsilon),
recurResR = shortDistRDP((PVector[]) subset(dots, idx), epsilon);
return (PVector[]) concat(shorten(recurResL), recurResR);
}
return new PVector[] { head, tail };
}
static final float dotLineSq(final PVector p, final PVector v, final PVector w) {
final float lineLen = vec2dDistSq(v, w);
if (lineLen == 0) return vec2dDistSq(p, v);
final float lineX = w.x - v.x, lineY = w.y - v.y;
final float t = ((p.x - v.x)*lineX + (p.y - v.y)*lineY) / lineLen;
if (t < 0) return vec2dDistSq(p, v);
if (t > 1) return vec2dDistSq(p, w);
final PVector z = v.get();
z.add(t * lineX, t * lineY, 0);
return vec2dDistSq(p, z);
}
static final float vec2dDistSq(final PVector a, final PVector b) {
return sq(a.x - b.x) + sq(a.y - b.y);
}
static final String FILENAME = "xy.csv", DELIM = ",";
PVector[] loadCoordsXYAsPVectorsArray() {
final String[] lines = loadStrings(FILENAME);
final PVector[] vecs = new PVector[lines.length];
for (int i = 0; i < lines.length; ++i) {
final PVector v = vecs[i] = new PVector();
v.set(float(lines[i].split(DELIM)));
}
return vecs;
}
<script defer src=https://Unpkg.com/processing-js></script>
<canvas data-processing-sources="RamerDouglasPeucker.pde Calc.pde Data.pde"></canvas>
/**
* Ramer-Douglas-Peucker Algorithm (v1.2.3)
* GoToLoop & JeffThompson (2019/Aug/26)
*
* https://Discourse.Processing.org/t/reducing-points-in-polygon/13590/2
*
* https://en.Wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
* https://Karthaus.nl/rdp/js/rdp2.js
*
* https://Bl.ocks.org/GoToLoop/a5db257be4d7756a00220a3e97066dd5
* https://www.OpenProcessing.org/sketch/747172
*/
static final int QTY = 12, DIAM = 15, BOLD = 2;
static final color BG = -1, FG = 0x64000000, STROKE = #0096FF;
static final boolean DEBUG = true;
PVector[] coords, reduced;
void setup() {
size(800, 600);
smooth();
noLoop();
strokeWeight(BOLD);
coords = loadCoordsXYAsPVectorsArray();
if (DEBUG) println("Polygon's original size: " + coords.length);
reduced = reducePolygon(coords, QTY);
if (DEBUG) println("Polygon's final size: " + reduced.length + "\n");
if (DEBUG) {
final int len = reduced.length, digits = max(0, str(len - 1).length());
for (int i = 0; i < len; println(nf(i, digits) + ": " + reduced[i++]));
}
}
void draw() {
background(BG);
drawPoints(coords);
translate(width >> 1, 0);
drawPoints(reduced);
}
void drawPoints(final PVector[] dots) {
if (dots == null) return;
noFill();
stroke(STROKE);
beginShape();
for (final PVector v : dots) vertex(v.x, v.y);
endShape(CLOSE);
fill(FG);
noStroke();
for (final PVector v : dots) ellipse(v.x, v.y, DIAM, DIAM);
}
337 333
337 342
333 390
332 391
328 406
328 407
328 408
314 445
314 446
291 494
291 495
289 499
276 525
272 531
271 532
266 539
261 543
259 545
257 547
256 548
253 549
252 550
247 551
234 552
222 552
221 551
219 550
219 550
159 443
154 433
151 424
150 422
139 392
135 380
134 378
124 326
122 313
118 283
118 270
118 258
119 245
121 227
126 193
129 182
132 173
133 171
154 134
208 41
220 41
220 42
277 127
286 142
304 174
319 211
320 213
320 214
330 243
330 245
330 246
334 260
334 262
337 299
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment