Skip to content

Instantly share code, notes, and snippets.

@msbarry
Last active June 25, 2024 15:25
Show Gist options
  • Save msbarry/9152218 to your computer and use it in GitHub Desktop.
Save msbarry/9152218 to your computer and use it in GitHub Desktop.
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.

<!DOCTYPE html>
<style type="text/css">
body {
font-size: 12px;
font-family: Arial;
width: 960px;
margin: 1em auto 0.3em auto;
}
.path {
fill: none;
stroke: #ccc;
stroke-width: 1px;
}
.simpler {
stroke: black;
fill: red;
fill-opacity: 20%;
}
text {
fill: #888;
}
.numpoints {
fill: black;
font-size: 30px;
}
.arrow {
fill: lightGray;
}
.arrow:hover {
fill: steelBlue;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js" charset="utf-8"></script>
<script src="readme-visvalingam.js"></script>
<script src="readme-douglaspeucker.js"></script>
<script>
var margin = { top: 10, right: 100, bottom: 10, left: 10 },
width = 960 - margin.left - margin.right,
height = 400 - margin.top - margin.bottom,
padding = 40,
numPoints = 10,
rows = 2,
smallWidth = width / 2,
smallHeight = height,
verticalSpacing = 25;
var svg = d3.select("body").append("svg")
.attr("width", 960)
.attr("height", 400);
// read in the route, pre-projected using mercator projection
d3.json("seven-climbs-mercator.json", function(fullResPoints) {
var path = d3.svg.line();
// draw small multiples
var left = svg.append('g')
.attr('transform', 'translate(' + margin.left + ',' + margin.top + ')');
var right = svg.append('g')
.attr('transform', 'translate(' + (margin.left + smallWidth) + ',' + (margin.top) + ')');
var sections = svg.selectAll('g');
// labels
left.append('text')
.text('Visvalingam')
.attr('dy', 30);
right.append('text')
.text('Douglas Peucker')
.attr('dy', 30);
// draw the polylines simplified using visvalingam algorithm
var visSimplified = left.append('path')
.attr('class', 'simpler');
// draw the polylines simplified using douglas peucker algorithm
var dpSimplified = right.append('path')
.attr('class', 'simpler');
// draw reference polylines
sections.append('path')
.datum(fullResPoints)
.attr('class', 'path')
.call(drawPath);
var pointsDisplay = svg.append('text')
.attr('class', 'numpoints')
.attr('x', width + margin.left + margin.right / 2)
.attr('y', height / 2)
.attr('text-anchor', 'middle');
var line = d3.svg.line();
function arrow (dir) {
return svg.append('path')
.datum([[0, dir * 40], [40, 0], [-40, 0]])
.attr('class', 'arrow')
.attr('transform', 'translate(' + (width + margin.left + margin.right / 2) + ',' + (height / 2 - 8 + dir * 30) + ')')
.attr('d', line);
}
var up = arrow(-1);
var down = arrow(1);
var pts = 10;
function incr() { pts = Math.min(pts + 1, fullResPoints.length); update(pts); }
function decr() { pts = Math.max(pts - 1, 4); update(pts); }
up.on('click', incr);
down.on('click', decr);
d3.select('body').on('keydown', function () {
if (d3.event.keyCode === 40) { decr(); d3.event.preventDefault(); }
else if (d3.event.keyCode === 38) { incr(); d3.event.preventDefault(); }
});
function update(numPoints) {
pts = numPoints;
visSimplified
.datum(fullResPoints.concat(simplifyVisvalingam(fullResPoints, numPoints).reverse()))
.call(drawPath);
dpSimplified
.datum(fullResPoints.concat(simplifyDouglasPeucker(fullResPoints, numPoints).reverse()))
.call(drawPath);
pointsDisplay.text(numPoints);
}
update(10);
function drawPath(selection) {
return selection
.attr("d", path)
.attr('transform', 'translate(' + padding + ',' + verticalSpacing + ')');
}
});
d3.select(self.frameElement).style("height", "400px");
</script>
[
[
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