Last active
August 28, 2019 20:17
-
-
Save GoToLoop/a5db257be4d7756a00220a3e97066dd5 to your computer and use it in GitHub Desktop.
Ramer–Douglas–Peucker Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| height: 600 | |
| scrolling: no | |
| border: yes | |
| license: cc-by-4.0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <script defer src=https://Unpkg.com/processing-js></script> | |
| <canvas data-processing-sources="RamerDouglasPeucker.pde Calc.pde Data.pde"></canvas> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * 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); | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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