{{ message }}

Instantly share code, notes, and snippets.

Last active May 24, 2020
Visvalingam vs. Douglas-Peucker
 // 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 = {}; })();
 // 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.


 [ [ 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 ], [ 144.94960325970897, 190.58511298864323 ], [ 143.48273643577704, 189.34295228353585 ], [ 142.49195796696586, 188.49214937750367 ], [ 141.12802916577493, 187.3180308160663 ], [ 140.74201158052892, 186.97770430799574 ], [ 140.2787904782308, 186.58632755281724 ], [ 139.661162341843, 186.05881760115153 ], [ 139.28801200943417, 185.73550382930262 ], [ 139.18507398670772, 185.6504211035135 ], [ 137.3707913360413, 184.10190426798363 ], [ 135.92965901779826, 182.87668905175087 ], [ 135.4407034098258, 182.468281018555 ], [ 134.92601329616446, 182.02583731183404 ], [ 134.73300450353418, 181.87268331619998 ], [ 134.3598541711399, 181.54935753050813 ], [ 133.83229680462682, 181.12392745136458 ], [ 133.4334119665582, 180.80059951674048 ], [ 133.17606690971297, 180.59639192197938 ], [ 132.93158910571947, 180.3921839570903 ], [ 132.55843877332518, 180.0858713156631 ], [ 132.22389019945695, 179.83061014489795 ], [ 131.72206733861822, 179.439208559721 ], [ 131.24597898349748, 179.08184070728748 ], [ 129.7019086424989, 177.90762406732392 ], [ 129.5603688612464, 177.8055176941125 ], [ 129.43169633283105, 177.7204289790825 ], [ 129.1614840231632, 177.48218023502704 ], [ 129.01994424189616, 177.34603786937805 ], [ 128.85266995495476, 177.1588418479223 ], [ 128.6725284151762, 176.95462765157572 ], [ 128.54385588677542, 176.80146676133154 ], [ 128.2993780827819, 176.4951443561731 ], [ 128.0549002787884, 176.17180313594872 ], [ 127.78468796912057, 175.76337079430232 ], [ 127.69461719921674, 175.61020828441542 ], [ 127.59167917649029, 175.42300937838445 ], [ 127.45013939525234, 175.1166832247909 ], [ 127.38580313102284, 174.9294834986722 ], [ 127.321466866837, 174.75930165944737 ], [ 127.23139609693317, 174.5721013393777 ], [ 127.17992708555539, 174.4699919427876 ], [ 127.06412180997722, 174.24875459924806 ], [ 126.97405104011705, 174.07857173164666 ], [ 126.79390950032393, 173.78926026661065 ], [ 126.5622989491676, 173.44889288585546 ], [ 126.36929015653732, 173.2106351073744 ], [ 126.09907784688403, 172.90430293742975 ], [ 125.49431696331885, 172.25759895408555 ], [ 125.23697190650273, 171.96828281210037 ], [ 124.61934377011494, 171.23647984194395 ], [ 124.45206948317355, 171.032254908685 ], [ 124.33626420759538, 170.9301423032448 ], [ 124.15612266780226, 170.75995442174462 ], [ 123.88591035813442, 170.52169095571298 ], [ 123.56422903710336, 170.19833258852304 ], [ 123.2425477160723, 169.82391647732584 ], [ 123.04953892342746, 169.6026700084476 ], [ 122.81792837228568, 169.31334704725305 ], [ 122.12309671884577, 168.37729708139523 ], [ 121.98155693759327, 168.19008615475468 ], [ 121.80141539781471, 167.98585569811985 ], [ 121.63414111088787, 167.7646056188678 ], [ 121.37679605402809, 167.50931652583677 ], [ 121.0036457216338, 167.1689301684164 ], [ 120.70769890627707, 166.9306591061977 ], [ 120.57902637786174, 166.82854278235754 ], [ 120.42461934377206, 166.72642636597448 ], [ 120.11580527557817, 166.53921269546117 ], [ 119.78125670169538, 166.35199871375517 ], [ 119.52391164486471, 166.2328623815847 ], [ 119.35663735792332, 166.16478442089283 ], [ 119.12502680676698, 166.06266740269348 ], [ 119.0349560368777, 166.0286283760579 ], [ 118.91915076131409, 165.99458933917776 ], [ 118.79047823289875, 165.94353076448897 ], [ 118.66180570448341, 165.89247216664808 ], [ 118.30152262491174, 165.79035490161186 ], [ 117.86403602830251, 165.68823754400364 ], [ 117.09200085781049, 165.50102214783692 ], [ 115.62513403389312, 165.14361007294065 ], [ 113.43770105081785, 164.6159996990391 ], [ 112.9487454428454, 164.49686153062794 ], [ 112.24104653658287, 164.30964415422932 ], [ 111.22453356206825, 164.0713670432815 ], [ 110.34956036884978, 163.90116879830748 ], [ 109.60325970404665, 163.76501001709403 ], [ 109.0499678318738, 163.6458709485305 ], [ 108.56101222387224, 163.52673175392556 ], [ 108.29079991421895, 163.45865215761296 ], [ 108.16212738580361, 163.40759243336652 ], [ 107.943384087499, 163.3224928415002 ], [ 107.67317177783116, 163.20335330481612 ], [ 107.49303023803805, 163.11825355863402 ], [ 107.26141968689626, 162.98209383097856 ], [ 106.6695260561828, 162.6076537312547 ], [ 106.16770319537318, 162.28427264329366 ], [ 105.27986274928844, 161.72260854698834 ], [ 104.93244692256849, 161.4673057590844 ], [ 104.63650010722631,