Instantly share code, notes, and snippets.

Last active June 25, 2024 15:25
Show Gist options
• Save msbarry/9152218 to your computer and use it in GitHub Desktop.
Visvalingam vs. Douglas-Peucker
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
 // Douglas Peucker polyline simplification algorithm // Adapted from http://onthegomap.com (function () { // utilities var sqr = function (x) { return x * x; }; var distSquared = function (p1, p2) { return sqr(p1[0] - p2[0]) + sqr(p1[1] - p2[1]); }; // Representation of a line segment, used to determine distance to a point var Line = function(p1, p2) { this.p1 = p1; this.p2 = p2; this.lengthSquared = distSquared(p1, p2); }; Line.prototype = { getRatio: function (point) { var p1 = this.p1, p2 = this.p2; var segmentLength = this.lengthSquared; if (segmentLength === 0) { return distSquared(point, p1); } return ((point[0] - p1[0]) * (p2[0] - p1[0]) + (point[1] - p1[1]) * (p2[1] - p1[1])) / segmentLength; }, distanceToSquared: function (point) { var p1 = this.p1, p2 = this.p2; var t = this.getRatio(point); if (t < 0) { return distSquared(point, p1); } if (t > 1) { return distSquared(point, p2); } return distSquared(point, [ p1[0] + t * (p2[0] - p1[0]), p1[1] + t * (p2[1] - p1[1]) ]); }, distanceTo: function (point) { return Math.sqrt(this.distanceToSquared(point)); } }; window.simplifyDouglasPeucker = function (points, pointsToKeep) { var start = new Date().getTime(); var weights = []; var len = points.length; function douglasPeucker (start, end) { if (end > start + 1) { var line = new Line(points[start], points[end]); var maxDist = -1; var maxDistIndex = 0; var dist; // find point furthest off the line from start to end for (var i = start + 1; i < end; i += 1) { dist = line.distanceToSquared(points[i]); if (dist > maxDist) { maxDist = dist; maxDistIndex = i; } } // record the weight of this point weights[maxDistIndex] = maxDist; // split the segment at that furthest point, and recursively invoke // this method to assign weights to each point in the subsegments douglasPeucker(start, maxDistIndex); douglasPeucker(maxDistIndex, end); } } douglasPeucker(0, len - 1); weights[0] = Infinity; weights[len - 1] = Infinity; // create descending weight array so to get n most important weights, // just find all points with weights >= weightsDescending[n] var weightsDescending = weights.slice(); weightsDescending.sort(function (a, b) { return b - a; }); var maxTolerance = weightsDescending[pointsToKeep -1]; var result = points.filter(function (d, i) { return weights[i] >= maxTolerance; }); var end = new Date().getTime(); window.simplifyDouglasPeucker.stats[pointsToKeep] = end - start; return result; }; window.simplifyDouglasPeucker.stats = {}; })();
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
 // Visvalingam polyline simplification algorithm, adapted from // http://bost.ocks.org/mike/simplify/simplify.js (function () { window.simplifyVisvalingam = function (points, pointsToKeep) { var start = new Date().getTime(), heap = minHeap(), maxArea = 0, triangle, triangles = []; points = points.map(function (d) { return d.slice(0,2); }); for (var i = 1, n = points.length - 1; i < n; ++i) { triangle = points.slice(i - 1, i + 2); if (triangle[1][2] = area(triangle)) { triangles.push(triangle); heap.push(triangle); } } for (var i = 0, n = triangles.length; i < n; ++i) { triangle = triangles[i]; triangle.previous = triangles[i - 1]; triangle.next = triangles[i + 1]; } while (triangle = heap.pop()) { // If the area of the current point is less than that of the previous point // to be eliminated, use the latters area instead. This ensures that the // current point cannot be eliminated without eliminating previously- // eliminated points. if (triangle[1][2] < maxArea) triangle[1][2] = maxArea; else maxArea = triangle[1][2]; if (triangle.previous) { triangle.previous.next = triangle.next; triangle.previous[2] = triangle[2]; update(triangle.previous); } else { triangle[0][2] = triangle[1][2]; } if (triangle.next) { triangle.next.previous = triangle.previous; triangle.next[0] = triangle[0]; update(triangle.next); } else { triangle[2][2] = triangle[1][2]; } } function update(triangle) { heap.remove(triangle); triangle[1][2] = area(triangle); heap.push(triangle); } var weights = points.map(function (d) { return d.length < 3 ? Infinity : d[2] += Math.random(); /* break ties */ }); weights.sort(function (a, b) { return b - a; }); var result = points.filter(function (d) { return d[2] > weights[pointsToKeep]; }); var end = new Date().getTime(); window.simplifyVisvalingam.stats[pointsToKeep] = end - start; return result; }; window.simplifyVisvalingam.stats = {}; function compare(a, b) { return a[1][2] - b[1][2]; } function area(t) { return Math.abs((t[0][0] - t[2][0]) * (t[1][1] - t[0][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[0][1])); } function minHeap() { var heap = {}, array = []; heap.push = function() { for (var i = 0, n = arguments.length; i < n; ++i) { var object = arguments[i]; up(object.index = array.push(object) - 1); } return array.length; }; heap.pop = function() { var removed = array[0], object = array.pop(); if (array.length) { array[object.index = 0] = object; down(0); } return removed; }; heap.size = function () { return array.length; }; heap.remove = function(removed) { var i = removed.index, object = array.pop(); if (i !== array.length) { array[object.index = i] = object; (compare(object, removed) < 0 ? up : down)(i); } return i; }; function up(i) { var object = array[i]; while (i > 0) { var up = ((i + 1) >> 1) - 1, parent = array[up]; if (compare(object, parent) >= 0) break; array[parent.index = i] = parent; array[object.index = i = up] = object; } } function down(i) { var object = array[i]; while (true) { var right = (i + 1) * 2, left = right - 1, down = i, child = array[down]; if (left < array.length && compare(array[left], child) < 0) child = array[down = left]; if (right < array.length && compare(array[right], child) < 0) child = array[down = right]; if (down === i) break; array[child.index = i] = child; array[object.index = i = down] = object; } } return heap; } })();

Two well-known algorithms for polyline simplification are the Douglas Peucker and Visvalingam algorithms.

The Douglas Peucker algorithm uses a recursive divide-and-conquer approach. It starts by drawing a straight line from the first point to the last point. Then it finds the intermediate point that is furthest away from the straight line and deems this the "most important" and splits the polyline into two halves at that point. This process is repeated on both halves until the distance of the intermediate point is below a certain threshold, after which all points on that sub-polyline are thrown away since they have a negligible impact on the overall shape.

The Visvalingam algorithm works from the inside-out. It starts by computing the area of the triangle formed by each consecutive three points along the polyline. Then the midpoint of the triangle with the least area is thrown out since those three points are the closest to colinear and the area of triangles on either side are recomputed. The process continues until all remaining triangles are above a certain threshold.

The Douglas Peucker algorithm is O(n^2) and if a min-heap is used for the Visvalingam algorithm to keep track of the triangle with the smallest area then its complexity is O(n log(n)) - making it a more attractive choice when the number of points gets very large.

This simulation shows the results of both algorithms side-by-side when applied to the Seven Climbs of Death bicycle ride in State College, Pennsylvania. The original route is shown in gray, the simplified route in black, and the discrepancy is shaded in red.

To get the desired number of points instead of using a threshold, this simulation uses the algorithms to sort the points in each polyline by importance, then extract the N most important points. The Douglas-Peucker algorithm implementation is extracted from the source for onthegomap.com and the Visvalingam algorithm implementation is from bost.ocks.org/mike/simplify.

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

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
 [ [ 243.7572378297191, 309.83684390242706 ], [ 243.79583958824514, 309.8538417195159 ], [ 244.16898992063943, 310.00682195820264 ], [ 244.349131460418, 310.0918108900587 ], [ 244.64507827577472, 310.22779304789583 ], [ 244.7608835513529, 310.29578406536893 ], [ 245.03109586102073, 310.4657614297321 ], [ 245.0825648723985, 310.49975687187543 ], [ 245.24983915935445, 310.6187408387268 ], [ 245.61012223889702, 310.9416966876888 ], [ 245.7773965258384, 311.1116730790163 ], [ 245.85460004289052, 311.17966356385296 ], [ 246.02187432981736, 311.34963959665765 ], [ 246.4979626849672, 311.8425686437913 ], [ 246.4979626849672, 311.8425686437913 ], [ 246.4979626849672, 311.82557112630457 ], [ 247.25713060262206, 311.09467545138614 ], [ 247.37293587820022, 310.9756919864376 ], [ 247.8361569804838, 310.49975687187543 ], [ 247.87475873900985, 310.48275915205886 ], [ 247.91336049752135, 310.4657614297321 ], [ 247.92622775035852, 310.4657614297321 ], [ 247.96482950891368, 310.44876370484417 ], [ 247.99056401457347, 310.44876370484417 ], [ 248.00343126742519, 310.4317659773369 ], [ 248.54385588677542, 309.9218329623254 ], [ 248.54385588677542, 309.9218329623254 ], [ 248.68539566801337, 310.05781532498804 ], [ 248.8140681964287, 310.22779304789583 ], [ 248.8140681964287, 310.22779304789583 ], [ 248.82693544929498, 310.15980198946636 ], [ 248.86553720780648, 310.00682195820264 ], [ 248.904138966318, 309.9218329623254 ], [ 248.99420973622182, 309.71785911097686 ], [ 249.66330688397284, 308.79997221670055 ], [ 249.7405104010395, 308.68098633181216 ], [ 249.75337765387667, 308.66398833804124 ], [ 250.17799699763418, 308.0860550251746 ], [ 250.20373150332307, 308.0520588557483 ], [ 250.74415612265875, 307.32113873553317 ], [ 250.80849238685914, 307.23614771651773 ], [ 250.8856959039258, 307.13415840924426 ], [ 251.20737722495687, 306.6752053855744 ], [ 251.2974479948607, 306.5562172598802 ], [ 251.94081063693739, 305.67230154027493 ], [ 252.0308814068121, 305.55331235686754 ], [ 252.42976624490984, 304.99236165895854 ], [ 252.58417327898496, 304.77138031520735 ], [ 252.82865108297847, 304.43140817200765 ], [ 252.93158910570492, 304.29541902783967 ], [ 253.02165987560875, 304.176428392253 ], [ 253.4076774608693, 303.63246960278775 ], [ 254.11537636714638, 302.6465376119668 ], [ 254.6043319751043, 301.94958048922126 ], [ 254.66866823931923, 301.86458542360924 ], [ 255.08042033026868, 301.2696181713254 ], [ 255.15762384730624, 301.16762347014446 ], [ 255.73665022518253, 300.38566103107587 ], [ 256.1355350632657, 299.8416839636411 ], [ 256.225605833155, 299.72268863049976 ], [ 257.02337550932134, 298.6347254790817 ], [ 257.10057902637345, 298.53272839567944 ], [ 257.65387089856085, 297.76774733080674 ], [ 257.97555221960647, 297.3257559066478 ], [ 258.0527557366295, 297.2237576397456 ], [ 258.297233540623, 296.9177622857824 ], [ 258.9534634355514, 296.0167711457907 ], [ 259.1850739867077, 295.64277271002356 ], [ 259.50675530772423, 295.2007729600664 ], [ 259.6354278361687, 295.01377254451654 ], [ 260.24018871970475, 294.19776710354927 ], [ 260.4460647651722, 293.9257639781572 ], [ 260.98648938452243, 293.1777520015239 ], [ 261.2953034527018, 292.7697433782305 ], [ 261.75852455501445, 292.1237267064789 ], [ 261.87432983057806, 291.95372170430346 ], [ 262.27321466866124, 291.4097039755288 ], [ 262.72356851810764, 290.79768089453864 ], [ 262.8779755522264, 290.5936724629282 ], [ 263.3025948959694, 289.98164495442325 ], [ 263.79155050397094, 289.33561231510976 ], [ 263.9073557795491, 289.21660589899693 ], [ 263.99742654942384, 289.1486021762976 ], [ 263.99742654942384, 289.1486021762976 ], [ 263.8172850096453, 288.89358785106015 ], [ 262.7621702766628, 287.46549697516457 ], [ 262.3632854385651, 286.93845887010684 ], [ 262.1445421402459, 286.63243561451964 ], [ 261.9515333476302, 286.3774156006184 ], [ 261.1408964186121, 285.2723222110362 ], [ 260.88355136178143, 284.8982881498232 ], [ 260.88355136178143, 284.8982881498232 ], [ 260.6390735578025, 284.60926098030905 ], [ 259.8284366287844, 283.6061609403914 ], [ 259.71263135320623, 283.4701466888582 ], [ 259.46815354921273, 283.13011034241936 ], [ 259.31374651512306, 282.89208428992424 ], [ 259.1850739867077, 282.6370558191993 ], [ 259.172206733856, 282.603051979524 ], [ 259.05640145827783, 282.2800149913601 ], [ 258.8762599185138, 281.7019464929035 ], [ 258.78618914862454, 281.4469153311002 ], [ 258.6703838730464, 281.20888572651165 ], [ 258.297233540623, 280.57980506766035 ], [ 258.03988848380686, 280.2227577274243 ], [ 257.8468796911766, 279.9847255393397 ], [ 257.666738151398, 279.7806975497224 ], [ 257.4608621059451, 279.5936715683565 ], [ 257.2549860604631, 279.4066452768311 ], [ 256.9590392451064, 279.1856138051953 ], [ 256.57302165987494, 278.9305769535131 ], [ 255.60797769675264, 278.4545066207502 ], [ 255.13188934161735, 278.1484603456702 ], [ 253.06026163414936, 276.72023341453314 ], [ 251.86360711988527, 275.88709268565435 ], [ 251.54192579883966, 275.649051346918 ], [ 251.10443920223042, 275.32599444082007 ], [ 249.8048466652399, 274.3228118339175 ], [ 247.604546429342, 272.605478522637 ], [ 246.93544928157644, 271.9933533968797 ], [ 246.88398027019866, 271.9593463480487 ], [ 246.43362642075226, 271.48324658739875 ], [ 246.17628136393614, 271.17718139419594 ], [ 246.06047608835797, 271.041152152844 ], [ 246.02187432981736, 270.9731374706171 ], [ 245.95753806561697, 270.88811906016053 ], [ 245.8674672957277, 270.75208947010833 ], [ 245.68732575593458, 270.49703354654775 ], [ 245.53291872185946, 270.2589808307239 ], [ 245.37851168775524, 270.02092761243694 ], [ 245.13403388376173, 269.62983909145987 ], [ 245.03109586102073, 269.47680408364977 ], [ 244.7222817928414, 269.0176978141608 ], [ 244.20759167918004, 268.20150427566114 ], [ 243.74437057688192, 267.5723510579264 ], [ 243.53849453139992, 267.30028371453227 ], [ 243.33261848594702, 267.0622242505415 ], [ 243.29401672743552, 267.0282157146721 ], [ 243.04953892344201, 266.7731513687322 ], [ 242.5991850739956, 266.3650472152076 ], [ 242.32897276429867, 266.1439901820486 ], [ 242.02015869613388, 265.8889238360862 ], [ 240.87497319321847, 265.15773044693924 ], [ 239.2794338408712, 264.22247617830726 ], [ 238.32725713060063, 263.6273103322965 ], [ 237.68389448852395, 263.2702093169355 ], [ 235.161912931595, 261.79077877736563 ], [ 234.78876259918616, 261.55270768207265 ], [ 234.73729358780838, 261.5357025846315 ], [ 234.20973622129532, 261.16158979158354 ], [ 233.74651511901175, 260.7534653290568 ], [ 233.5149045678554, 260.5153920437515 ], [ 231.8807634570112, 258.9338924599797 ], [ 230.98005575807474, 258.11762593164894 ], [ 230.42676388591644, 257.6244620406287 ], [ 230.1822860819084, 257.43739931080927 ], [ 228.99849882051058, 256.3830399387516 ], [ 228.63821574092435, 256.04292190912383 ], [ 228.63821574092435, 256.04292190912383 ], [ 228.67681749946496, 255.9068744100441 ], [ 228.67681749946496, 255.73681480529922 ], [ 228.8440917863918, 255.27765259137232 ], [ 229.01136607334774, 254.85250072611234 ], [ 229.38451640574203, 254.3933349110448 ], [ 231.35320609049813, 252.4035947712764 ], [ 231.35320609049813, 252.4035947712764 ], [ 230.15655157623405, 250.56688039897563 ], [ 230.15655157623405, 250.56688039897563 ], [ 231.0186575166299, 249.86960136656126 ], [ 231.5462148831284, 249.42742218482454 ], [ 232.66566588034038, 248.5260515590271 ], [ 233.23182500536495, 248.0838671079473 ], [ 233.28329401671363, 248.03284571351833 ], [ 233.5406390735443, 247.84576706977532 ], [ 233.8880549002788, 247.57365212474542 ], [ 234.2226034741616, 247.31854376728734 ], [ 234.45421402530337, 247.13146393829084 ], [ 235.00750589749077, 246.7232886884376 ], [ 235.41925798841112, 246.3831415180248 ], [ 235.7538065622939, 246.1110230428094 ], [ 235.89534634356096, 246.00897844525025 ], [ 237.01479734077293, 245.15860320722277 ], [ 237.34934591465571, 244.92049699111521 ], [ 239.04782328971487, 243.57688820379553 ], [ 239.04782328971487, 243.57688820379553 ], [ 239.12502680678153, 243.44082566157886 ], [ 239.25369933519687, 243.25373939787096 ], [ 239.25369933519687, 243.16870008441765 ], [ 239.22796482949343, 242.9816133691711 ], [ 239.2022303238191, 242.84555010847544 ], [ 239.08642504825548, 242.57342309450178 ], [ 238.98348702549993, 242.31830342230387 ], [ 238.79047823289875, 241.84207848957158 ], [ 238.5073986703792, 241.1957700060011 ], [ 238.30152262491174, 240.6685156040403 ], [ 237.9541067981918, 239.83510845537967 ], [ 237.55522196009406, 238.8486185617221 ], [ 237.43941668453044, 238.5424647705222 ], [ 237.29787690327794, 238.20229291625583 ], [ 237.05339909928443, 237.6069897012785 ], [ 236.70598327256448, 236.73954224599584 ], [ 236.59017799700086, 236.51842712116922 ], [ 236.50010722711158, 236.3483382685081 ], [ 236.39716920437058, 236.21226700156694 ], [ 236.28136392879242, 236.09320450826635 ], [ 236.13982414755446, 235.923115014004 ], [ 235.97254986059852, 235.75302526308224 ], [ 234.956036886113, 234.66444477996993 ], [ 234.8273643577122, 234.51136230645352 ], [ 234.6858245764597, 234.3582796250339 ], [ 234.57001930088154, 234.22220595591352 ], [ 234.32554149687348, 233.9670673836008 ], [ 234.04246193436848, 233.64389102970745 ], [ 233.21895775252779, 232.6913658599733 ], [ 231.76495818143303, 230.9904080369597 ], [ 231.49474587175064, 230.6842329029605 ], [ 231.00579026377818, 230.10589982527017 ], [ 230.88998498821456, 229.9868308821242 ], [ 230.3881621273904, 229.4255041702272 ], [ 230.07934805918194, 229.06829480727174 ], [ 229.53892343984626, 228.47294335337938 ], [ 229.3587819000677, 228.26882213106 ], [ 228.98563156765886, 227.8435683972857 ], [ 228.8054900278803, 227.65645624614262 ], [ 228.62534848808718, 227.43532330344897 ], [ 228.13639288011473, 226.90800453552947 ], [ 227.7761098005576, 226.4997560532138 ], [ 227.51876474371238, 226.244600000864 ], [ 227.20995067553304, 225.93841197563597 ], [ 227.02980913573992, 225.7853176511053 ], [ 226.84966759596136, 225.64923363250273 ], [ 226.6952605618717, 225.51314944964543 ], [ 226.55372078060464, 225.41108620464365 ], [ 226.4250482521893, 225.29201230203034 ], [ 226.06476517263218, 225.0198429093798 ], [ 225.8074201158015, 224.8157154335713 ], [ 225.53720780613367, 224.59457691766147 ], [ 225.00965043963515, 224.20333078813564 ], [ 224.85524340554548, 224.06724485955783 ], [ 224.76517263564165, 223.98219107070327 ], [ 224.68796911858954, 223.8801264394424 ], [ 224.61076560153742, 223.76105091945647 ], [ 224.37915505039564, 223.33578017824038 ], [ 223.77439416683046, 222.07696938013396 ], [ 223.59425262706645, 221.70272562083846 ], [ 223.4141110872879, 221.36250294314232 ], [ 223.1825005361461, 220.85216700095043 ], [ 223.0409607548645, 220.51194175574346 ], [ 222.91228822644916, 220.25677214788448 ], [ 222.7578811923595, 219.96757922721736 ], [ 222.33326184858743, 219.06597300578142 ], [ 222.24319107869815, 218.81080012421444 ], [ 222.24319107869815, 218.81080012421444 ], [ 221.94724426334142, 218.98091544277122 ], [ 220.68625348487694, 219.7804540008292 ], [ 219.48959897061286, 220.51194175574346 ], [ 219.12931589105574, 220.7160770261471 ], [ 218.73043105297256, 220.93722315181367 ], [ 218.57602401886834, 221.0392904480468 ], [ 217.67531631996098, 221.5156032751911 ], [ 217.28929873471498, 221.70272562083846 ], [ 216.8646793909429, 221.88984765577334 ], [ 216.38859103582217, 222.07696938013396 ], [ 216.04117520910222, 222.19604667925887 ], [ 215.51361784258916, 222.36615688844176 ], [ 215.02466223460215, 222.5192558571871 ], [ 214.18829079990974, 222.74039844489016 ], [ 213.37765387090622, 222.89349690527888 ], [ 212.18099935664213, 223.0806169633579 ], [ 208.8355136178434, 223.48887782990641 ], [ 207.09843448422907, 223.71001851520123 ], [ 206.69954964616045, 223.76105091945647 ], [ 206.2105940381589, 223.8461048751269 ], [ 205.9146472228167, 223.91414799347694 ], [ 205.63156766029715, 223.99920183361974 ], [ 205.41282436199253, 224.06724485955783 ], [ 205.07827578810975, 224.18632005606196 ], [ 204.8337979841308, 224.2713736908263 ], [ 204.38344413466984, 224.49251284089405 ], [ 203.92022303238628, 224.7306622095566 ], [ 203.63714346986671, 224.9007685934339 ], [ 203.27686039029504, 225.1559276878179 ], [ 202.87797555221186, 225.4621178386733 ], [ 202.41475444991374, 225.81933863008453 ], [ 201.59125026807305, 226.48274566767213 ], [ 200.29165773106797, 227.46934378441074 ], [ 200.16298520265264, 227.57140516568325 ], [ 199.86703838728135, 227.7925378413929 ], [ 199.4552862963901, 228.0476903896997 ], [ 197.2421188076405, 229.20437469804165 ], [ 197.1391807848995, 229.23839464509365 ], [ 197.04911001499568, 229.27241458185745 ], [ 196.97190649797267, 229.28942454641947 ], [ 196.85610122237995, 229.3234444677728 ], [ 196.66309242976422, 229.35746437883063 ], [ 196.28994209735538, 229.4255041702272 ], [ 195.92965901779826, 229.51055385169457 ], [ 195.60797769675264, 229.59560346904618 ], [ 194.99034956036485, 229.78271240123286 ], [ 194.7072699978453, 229.88477168785903 ], [ 194.53999571091845, 229.95281116096157 ], [ 194.1925798841985, 230.12290966400906 ], [ 193.89663306884177, 230.2930079104044 ], [ 192.97019086424552, 230.82031084300252 ], [ 192.23675745227956, 231.22854367737455 ], [ 191.45185502895038, 231.67079424620897 ], [ 189.81771391807706, 232.52127123264654 ], [ 189.58610336692072, 232.6743564087592 ], [ 188.95560797771032, 233.09959191825328 ], [ 188.2993780827819, 233.59286309967138 ], [ 188.05490027880296, 233.77996539689047 ], [ 188.00343126741063, 233.81398396303848 ], [ 187.60454642932746, 234.10314136069792 ], [ 186.99978554579138, 234.56238982069772 ], [ 186.29208663949976, 235.08967278233467 ], [ 185.7773965258384, 235.4638720975272 ], [ 184.9024233326054, 236.04217768694798 ], [ 183.9759811280237, 236.65449801856448 ], [ 183.5899635427777, 236.90963050840946 ], [ 183.42268925585086, 237.0286921394436 ], [ 183.31975123310986, 237.11373608458962 ], [ 183.2168132103834, 237.1987799655908 ], [ 183.15247694618301, 237.26681502420251 ], [ 183.0752734291309, 237.334850041756 ], [ 182.94660090070101, 237.48792868110468 ], [ 182.90799914217496, 237.53895484800887 ], [ 182.81792837227113, 237.67502451354085 ], [ 182.57345056830673, 238.03220660421357 ], [ 182.50911430410633, 238.11724979230348 ], [ 182.35470726998756, 238.32135318204382 ], [ 182.21316748873505, 238.50844763128407 ], [ 182.02015869610477, 238.72955885284318 ], [ 181.87861891486682, 238.91665262464812 ], [ 181.62127385803615, 239.27383078129787 ], [ 181.42826506540587, 239.528957343231 ], [ 181.19665451426408, 239.85211682615045 ], [ 180.99077846879663, 240.14125873612647 ], [ 180.66909714775102, 240.56646608011215 ], [ 180.5275573664985, 240.7535568033927 ], [ 180.42461934377206, 240.87261437472625 ], [ 180.283079562505, 241.0256882102767 ], [ 180.1672742869414, 241.14474549426086 ], [ 180.0772035170521, 241.22978633436287 ], [ 179.9742654943111, 241.31482711032731 ], [ 179.8584602187475, 241.39986782213236 ], [ 179.74265494316933, 241.4849084698144 ], [ 179.63971692044288, 241.5359328276536 ], [ 179.51104439202754, 241.62097337267915 ], [ 179.3823718636122, 241.6890057625278 ], [ 179.26656658803404, 241.77404619210574 ], [ 178.94488526700297, 241.97814296136494 ], [ 178.81621273858764, 242.0631831728242 ], [ 178.63607119879453, 242.16523134188174 ], [ 178.5588676817424, 242.19924737771362 ], [ 178.49453141754202, 242.23326340330095 ], [ 178.43019515334163, 242.26727941860008 ], [ 178.35299163627496, 242.2842874224225 ], [ 178.2757881192374, 242.31830342230387 ], [ 178.14711559083662, 242.35231941195525 ], [ 178.03131031525845, 242.4033433772056 ], [ 177.9669740510435, 242.42035136047343 ], [ 177.825434269791, 242.4883832679261 ], [ 177.67102723568678, 242.55641513428418 ], [ 177.41368217884155, 242.67547080172517 ], [ 177.22067338622583, 242.7605104871909 ], [ 176.92472657088365, 242.84555010847544 ], [ 176.30709843446675, 243.06665282370523 ], [ 176.0240188719763, 243.15169221407996 ], [ 175.84387733218318, 243.20271581753332 ], [ 175.5350632639893, 243.32177080237307 ], [ 175.40639073557395, 243.3387786471285 ], [ 175.03324040317966, 243.44082566157886 ], [ 174.672957323608, 243.49184913413774 ], [ 174.5700193008961, 243.50885695319448 ], [ 174.47994853099226, 243.5258647697192 ], [ 174.40274501394015, 243.55988039501972 ], [ 174.35127600257692, 243.57688820379553 ], [ 174.29980699119915, 243.59389601006114 ], [ 174.24833797983592, 243.62791161478526 ], [ 174.1968689684727, 243.66192720929394 ], [ 174.1582672099612, 243.6959427935435 ], [ 174.11966545140604, 243.74696615069843 ], [ 174.10679819858342, 243.78098170924932 ], [ 174.08106369289453, 243.81499725761387 ], [ 174.04246193438303, 243.90003608351253 ], [ 174.02959468154586, 243.95105934824096 ], [ 174.00386017584242, 244.03609807156317 ], [ 174.00386017584242, 244.13814445478056 ], [ 173.99099292300525, 244.22318303693464 ], [ 173.99099292300525, 244.32522925086232 ], [ 173.97812567016808, 244.444283050354 ], [ 173.96525841731636, 244.51231373648625 ], [ 173.9523911644792, 244.56333672413166 ], [ 173.92665665880486, 244.6143596886759 ], [ 173.9137894059677, 244.6483749856052 ], [ 173.88805490026425, 244.6823902721735 ], [ 173.8237186360784, 244.8014436945523 ], [ 173.73364786617458, 244.9375045946872 ], [ 173.6435770962853, 245.05655774760817 ], [ 173.51490456786996, 245.22663346227637 ], [ 173.4119665451435, 245.34568630993454 ], [ 173.2575595110393, 245.5157615884309 ], [ 173.11601972980134, 245.702844098465 ], [ 173.06455071842356, 245.77087402514735 ], [ 172.93587819000822, 245.87291883821308 ], [ 172.88440917863045, 245.9239412100942 ], [ 172.84580742011894, 245.95795611186622 ], [ 172.74286939737794, 246.02598588461115 ], [ 172.67853313317755, 246.07700818721787 ], [ 172.58846236328827, 246.1280304667307 ], [ 172.48552434056182, 246.19606013684825 ], [ 172.33111730644305, 246.29810456503037 ], [ 172.2667810422572, 246.33211935396685 ], [ 172.18957752519054, 246.3831415180248 ], [ 172.13810851384187, 246.43416365898884 ], [ 172.0609049967752, 246.50219314439164 ], [ 171.9837014797231, 246.5702225887435 ], [ 171.89363070984837, 246.68927401758265 ], [ 171.76495818141848, 246.8423399556341 ], [ 171.58481664163992, 247.02942026437813 ], [ 171.3918078490242, 247.284529276003 ], [ 171.25026806777169, 247.45460162977542 ], [ 171.09586103366746, 247.6416809225775 ], [ 170.88998498818546, 247.87978139173356 ], [ 170.6455071842065, 248.1859098274872 ], [ 170.49110015011684, 248.3559808215141 ], [ 170.34956036886433, 248.50904449679365 ], [ 170.220887840449, 248.6280938783966 ], [ 169.96354278361832, 248.88319927269913 ], [ 169.8091357495141, 249.00224825923942 ], [ 169.6032597040612, 249.13830408985086 ], [ 169.25584387734125, 249.37640139838186 ], [ 169.10143684325158, 249.46143602961092 ], [ 168.93416255628108, 249.56347750235 ], [ 168.35513617841934, 249.9036150779648 ], [ 167.75037529486872, 250.27776522595377 ], [ 167.4672957323637, 250.44783306460886 ], [ 166.96547287153953, 250.73694780153164 ], [ 166.78533133176097, 250.83898811994732 ], [ 166.65665880334564, 250.9240216480539 ], [ 166.48938451640424, 250.9920484243703 ], [ 166.29637572377396, 251.09408851186163 ], [ 166.29637572377396, 251.09408851186163 ], [ 166.09049967833562, 250.8049746907418 ], [ 165.65301308171183, 250.24375162742945 ], [ 165.34419901351794, 249.92062192983576 ], [ 164.99678318679798, 249.49544986408728 ], [ 164.2504825219803, 248.66210796429368 ], [ 163.98027021231246, 248.28795245470974 ], [ 163.1181642719166, 247.31854376728734 ], [ 162.77074844519666, 246.97839839275548 ], [ 162.16598756164603, 246.41715628124803 ], [ 161.8314389877778, 246.07700818721787 ], [ 161.49689041389502, 245.83890391074965 ], [ 161.14947458717506, 245.48174655323965 ], [ 160.82779326612945, 245.07356533061102 ], [ 160.724855243403, 244.81845131603768 ], [ 160.63478447352827, 244.51231373648625 ], [ 160.50611194509838, 243.72995836757036 ], [ 160.31310315248265, 243.04964493794978 ], [ 160.13296161268954, 242.65846285692533 ], [ 159.97855457859987, 242.35231941195525 ], [ 159.6182714990282, 241.7570381113328 ], [ 159.48959897061286, 241.3828596849271 ], [ 159.2451211666339, 240.54945781717106 ], [ 159.0392451211519, 239.66502460679476 ], [ 158.9234398455883, 239.17177999490377 ], [ 158.69182929443195, 238.44041332205234 ], [ 158.5245550075051, 238.03220660421357 ], [ 158.21574093929667, 237.40288501824398 ], [ 158.02273214668094, 237.09672730066814 ], [ 157.77825434270198, 236.75655108378123 ], [ 157.58524555005715, 236.4844093711581 ], [ 157.34076774609275, 236.1612402341343 ], [ 156.07977696762828, 234.81752704560495 ], [ 155.75809564658266, 234.39229801660986 ], [ 155.35921080848493, 233.9670673836008 ], [ 155.17906926870637, 233.72893752845266 ], [ 154.9217242118757, 233.3037043930526 ], [ 154.71584816640825, 232.92949790697458 ], [ 154.49710486811819, 232.6913658599733 ], [ 154.25262706411013, 232.50426175582834 ], [ 153.98241475445684, 232.40220484082965 ], [ 153.712202444789, 232.31715734113095 ], [ 153.14604331973533, 232.28313832325512 ], [ 152.72142397599237, 232.23210977724375 ], [ 152.07806133390113, 232.1980907337056 ], [ 151.4733004503505, 232.1470621491826 ], [ 151.01007934806694, 232.1470621491826 ], [ 150.48252198156842, 232.2151002567407 ], [ 150.07076989063353, 232.3001478334918 ], [ 149.80055758095114, 232.40220484082965 ], [ 149.6075487883354, 232.48725227639807 ], [ 149.17006219172617, 232.65734695503488 ], [ 148.60390306668705, 232.94650731964066 ], [ 148.19215097575216, 233.18463882768992 ], [ 146.85395668025012, 234.08613212251657 ], [ 146.17199227966194, 234.51136230645352 ], [ 145.73450568303815, 234.81752704560495 ], [ 145.29701908642892, 235.2597635341226 ], [ 144.84666523698252, 235.6169532775457 ], [ 144.11323182498745, 236.1102134436078 ], [ 143.77868325111922, 236.31432046717237 ], [ 143.32832940167282, 236.55244486092124 ], [ 143.0323825863161, 236.75655108378123 ], [ 142.68496675959614, 237.09672730066814 ], [ 142.29894917435013, 237.43690249105566 ], [ 142.09307312886813, 237.58998099182645 ], [ 141.64271927942173, 237.89613736976753 ], [ 141.2180999356642, 238.11724979230348 ], [ 140.33025948959403, 238.55947333631048 ], [ 139.8284366287844, 238.67853322484007 ], [ 139.40381728501234, 238.7125503127536 ], [ 139.06926871112955, 238.69554177005193 ], [ 138.22003002359997, 238.372378971726 ], [ 137.74394166845013, 238.16827567441214 ], [ 137.47372935879685, 237.99818931099435 ], [ 137.19064979624818, 237.862120035541 ], [ 136.66309242977877, 237.5559635652171 ], [ 136.48295088998566, 237.43690249105566 ], [ 136.26420759168104, 237.2498062634113 ], [ 136.03259704053926, 236.99467454341357 ], [ 135.92965901779826, 236.70552456271253 ], [ 135.90392451212392, 236.33132936908805 ], [ 135.94252627063543, 235.97414188922994 ], [ 136.1355350632657, 235.51489918065636 ], [ 136.5858889127121, 234.9195817738364 ], [ 136.84323396952823, 234.68145393083978 ], [ 137.1649152905884, 234.44332558481256 ], [ 137.5766673815233, 234.18818751296203 ], [ 137.84687969117658, 234.00108589327283 ], [ 138.03988848380686, 233.76295610998932 ], [ 138.4773750804161, 233.1676294509307 ], [ 139.10787046964106, 232.36818584864523 ], [ 139.51962256057595, 231.94294758000615 ], [ 140.35599399529747, 231.17751465390756 ], [ 140.70340982200287, 230.82031084300252 ], [ 141.43684323396883, 230.17393916490255 ], [ 142.0287368646823, 229.74869261847198 ], [ 142.64636500107008, 229.25540461477794 ], [ 143.14818786189426, 228.89819471271767 ], [ 143.57280720566632, 228.59201389571535 ], [ 145.03967402959825, 227.6904766603766 ], [ 146.09478876259527, 226.8739838851252 ], [ 146.6352133819455, 226.4487248889418 ], [ 147.02123096717696, 226.10851653676218 ], [ 147.4201158052747, 225.73428616336605 ], [ 147.79326613766898, 225.41108620464365 ], [ 148.16641647009237, 225.03685351565218 ], [ 148.46236328543455, 224.76468350688083 ], [ 149.06712416898517, 224.18632005606196 ], [ 149.4917435127718, 223.7270293192123 ], [ 149.62041604118713, 223.57393199101352 ], [ 150.32811494744965, 222.55327782200038 ], [ 150.4953892344056, 222.28110181596276 ], [ 150.7141325327102, 221.99191408941988 ], [ 150.8556723139627, 221.82180331538984 ], [ 151.01007934806694, 221.61767004764988 ], [ 151.65344199012907, 221.00526802623062 ], [ 152.7085567231261, 219.71240838692756 ], [ 154.5357066266297, 217.5179153115896 ], [ 154.80591893631208, 217.1946917910609 ], [ 154.8959897061868, 217.16066820861306 ], [ 155.15333476303203, 216.95652649850672 ], [ 155.51361784258916, 216.59927761607105 ], [ 155.66802487669338, 216.37812297847267 ], [ 155.75809564658266, 216.3100753103572 ], [ 155.98970619772444, 216.02087226254662 ], [ 156.19558224320645, 215.83374048324913 ], [ 156.3371220244444, 215.765692486435 ], [ 156.7874758738908, 215.4594759924148 ], [ 156.92901565515785, 215.34039157561347 ], [ 157.1734934591659, 215.10222236445406 ], [ 157.22496247051458, 215.000149691361 ], [ 157.39223675745598, 214.65990677991067 ], [ 157.49517478018242, 214.3536872813711 ], [ 157.61098005574604, 214.01344241823244 ], [ 157.80398884837632, 213.58813489480963 ], [ 157.99699764099205, 213.31593723747937 ], [ 158.16427192793344, 213.1288009666896 ], [ 158.42161698477867, 212.8225773078666 ], [ 158.70469654728367, 212.482327822152 ], [ 158.9234398455883, 212.19311495160218 ], [ 159.1421831438929, 211.8188383703382 ], [ 159.30945743084885, 211.51261115200032 ], [ 159.5796697405167, 211.05326876432082 ], [ 159.87561655587342, 210.57691171803162 ], [ 160.19729787690449, 210.10055265820847 ], [ 160.4803774394095, 209.6241915847495 ], [ 160.8921295303444, 208.9606853054429 ], [ 161.2524126099015, 208.34821450330492 ], [ 161.5483594252728, 207.8208064229766 ], [ 161.71563371219963, 207.4805418354008 ], [ 161.8057044820889, 207.24235601275723 ], [ 161.90864250481536, 206.9191030196962 ], [ 161.9729787690303, 206.61286248670513 ], [ 162.05018228608242, 206.40870166903915 ], [ 162.19172206732037, 206.15350012677663 ], [ 162.2817928372242, 205.98336544422637 ], [ 162.43619987132843, 205.7962169967068 ], [ 162.46193437701731, 205.7621899728474 ], [ 162.46193437701731, 205.69413589431497 ], [ 162.43619987132843, 205.62608177468792 ], [ 162.4104653656541, 205.5580276139517 ], [ 162.35899635427631, 205.48997341217182 ], [ 162.2431910787127, 205.43893273379217 ], [ 162.06304953891959, 205.43893273379217 ], [ 161.84430624061497, 205.45594629583502 ], [ 161.5226249195839, 205.48997341217182 ], [ 161.110872828649, 205.5580276139517 ], [ 159.06497962685535, 205.72816293872893 ], [ 158.76903281149862, 205.74517645704327 ], [ 158.39588247907523, 205.71114941778796 ], [ 158.0999356637476, 205.66010883963463 ], [ 157.98413038816943, 205.5750411580011 ], [ 157.90692687111732, 205.4729598552658 ], [ 157.59811280290887, 205.01359284861246 ], [ 157.59811280290887, 205.01359284861246 ], [ 157.43083851598203, 204.7073471371623 ], [ 156.53013081707468, 203.24416169489996 ], [ 155.24340553290676, 201.30456100939045 ], [ 155.01179498176498, 200.9472625047565 ], [ 154.97319322325347, 200.8962197687215 ], [ 154.9217242118757, 200.84517700961442 ], [ 154.8573879476753, 200.77711996145808 ], [ 154.7415826721117, 200.74309142197308 ], [ 154.6386446493707, 200.74309142197308 ], [ 154.54857387946686, 200.74309142197308 ], [ 154.41990135105152, 200.74309142197308 ], [ 154.31696332832507, 200.7260771483925 ], [ 154.17542354708712, 200.62399145287054 ], [ 154.00814926013118, 200.40280546194117 ], [ 153.93094574307906, 200.2496764446696 ], [ 153.93094574307906, 200.16460467849538 ], [ 154.00814926013118, 200.06251847429667 ], [ 154.00814926013118, 200.06251847429667 ], [ 154.4456358567404, 199.7392448841856 ], [ 154.9217242118757, 199.36492693692708 ], [ 154.9989277289278, 199.27985450276174 ], [ 155.02466223460215, 199.24582551111962 ], [ 155.02466223460215, 199.24582551111962 ], [ 155.02466223460215, 199.14373847450042 ], [ 154.8959897061868, 198.99060774618556 ], [ 154.80591893631208, 198.87150592473336 ], [ 154.45850310959213, 198.54822891758522 ], [ 154.18829079990974, 198.31002421359153 ], [ 153.04310529700888, 197.32317078951746 ], [ 152.29680463220575, 196.676606963214 ], [ 151.7049110015214, 196.18317417851358 ], [ 150.8170705554512, 195.43451341326727 ], [ 149.71048681106186, 194.51569567526167 ], [ 148.73257559511694, 193.71597784155165 ], [ 148.59103581386444, 193.59687044449674 ], [ 148.17928372292954, 193.25656290198094 ], [ 147.29144327685935, 192.52489820498158 ], [ 145.901779969965, 191.38485304499045