Skip to content

Instantly share code, notes, and snippets.

@stephanbogner
Last active November 13, 2017 14:03
Show Gist options
  • Save stephanbogner/c93b1895b3a5baef16f15d0a9304b85f to your computer and use it in GitHub Desktop.
Save stephanbogner/c93b1895b3a5baef16f15d0a9304b85f to your computer and use it in GitHub Desktop.
Removes the loops from a lineString (Test to outline a lineString without having weird overlaps) Please note that this algorithm is not optimized for performance. I recommend only using it in command line tools
Display the source blob
Display the rendered blob
Raw
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {
"stroke": "#555555",
"stroke-width": 7,
"stroke-opacity": 1
},
"geometry": {
"type": "LineString",
"coordinates": [
[
23.37890625,
57.61010702068388
],
[
16.5234375,
53.225768435790194
],
[
23.37890625,
50.064191736659104
],
[
23.203125,
46.800059446787316
],
[
18.80859375,
26.745610382199022
],
[
14.589843749999998,
28.613459424004414
],
[
17.578125,
35.31736632923788
],
[
28.30078125,
33.137551192346145
],
[
30.585937499999996,
11.523087506868514
],
[
30.234375,
-20.797201434306984
],
[
21.09375,
-21.125497636606266
],
[
10.1953125,
-13.752724664396975
],
[
11.074218749999998,
-5.0909441750333855
],
[
13.18359375,
-0.7031073524364783
],
[
18.10546875,
1.9332268264771233
],
[
22.67578125,
2.986927393334876
],
[
46.05468749999999,
-7.536764322084078
],
[
63.28125,
-8.581021215641842
],
[
64.86328125,
-3.513421045640032
],
[
65.21484375,
2.986927393334876
],
[
60.64453125000001,
4.565473550710278
],
[
54.140625,
3.8642546157214084
],
[
51.67968749999999,
0.17578097424708533
],
[
51.15234375,
-11.350796722383672
],
[
51.328125,
-20.632784250388013
],
[
49.39453125,
-33.7243396617476
],
[
50.09765625,
-46.07323062540835
],
[
44.29687499999999,
-48.224672649565186
]
]
}
},
{
"type": "Feature",
"properties": {
"stroke": "#ffffff",
"stroke-width": 2,
"stroke-opacity": 1
},
"geometry": {
"type": "LineString",
"coordinates": [
[
23.37890625,
57.61010702068388
],
[
16.5234375,
53.225768435790194
],
[
23.37890625,
50.064191736659104
],
[
23.203125,
46.800059446787316
],
[
20.554340872593087,
34.712329642573984
],
[
28.30078125,
33.137551192346145
],
[
30.585937499999996,
11.523087506868514
],
[
30.45499614735498,
-0.5147787383520281
],
[
46.05468749999999,
-7.536764322084078
],
[
51.31225567391882,
-7.855472817116946
],
[
51.15234375,
-11.350796722383672
],
[
51.328125,
-20.632784250388013
],
[
49.39453125,
-33.7243396617476
],
[
50.09765625,
-46.07323062540835
],
[
44.29687499999999,
-48.224672649565186
]
]
}
}
]
}
var ls = {
"type": "Feature",
"properties": {},
"geometry": {
"type": "LineString",
"coordinates": [
[23.37890625, 57.61010702068388],
[16.5234375, 53.225768435790194],
[23.37890625, 50.064191736659104],
[23.203125, 46.800059446787316],
[18.80859375, 26.745610382199022],
[14.589843749999998, 28.613459424004414],
[17.578125, 35.31736632923788],
[28.30078125, 33.137551192346145],
[30.585937499999996, 11.523087506868514],
[30.234375, -20.797201434306984],
[21.09375, -21.125497636606266],
[10.1953125, -13.752724664396975],
[11.074218749999998, -5.0909441750333855],
[13.18359375, -0.7031073524364783],
[18.10546875, 1.9332268264771233],
[22.67578125, 2.986927393334876],
[46.05468749999999, -7.536764322084078],
[63.28125, -8.581021215641842],
[64.86328125, -3.513421045640032],
[65.21484375, 2.986927393334876],
[60.64453125000001, 4.565473550710278],
[54.140625, 3.8642546157214084],
[51.67968749999999, 0.17578097424708533],
[51.15234375, -11.350796722383672],
[51.328125, -20.632784250388013],
[49.39453125, -33.7243396617476],
[50.09765625, -46.07323062540835],
[44.29687499999999, -48.224672649565186]
]
}
}
console.log(JSON.stringify(removeLoops(ls), null, 4));
function removeLoops(feature) {
var segments = turf.lineSegment(feature);
var hasIntersection = false;
for (var i = 0; i < segments.features.length - 2; i++) {
for (var j = i + 2; j < segments.features.length; j++) {
var line1 = turf.lineString(segments.features[i].geometry.coordinates);
var line2 = turf.lineString(segments.features[j].geometry.coordinates);
var intersect = turf.lineIntersect(line1, line2);
if (intersect.features.length > 0) {
var intersectionCoordinates = intersect.features[0].geometry.coordinates;
var throwAwayFromIndex = i + 1;
var throwAwayToIndex = j + 1;
var throwAwayNumber = throwAwayToIndex - throwAwayFromIndex;
segments.features.splice(throwAwayFromIndex, throwAwayNumber);
var newLineString = mergeLineStrings(segments);
newLineString.geometry.coordinates.splice(throwAwayFromIndex, 0, intersectionCoordinates);
return removeLoops(newLineString);
}
}
}
if (hasIntersection === false) {
return feature;
}
}
function mergeLineStrings(featureCollection) {
var lineString = JSON.parse(JSON.stringify(featureCollection.features[0]));
lineString.geometry.coordinates = [];
delete lineString.bbox;
delete lineString.id;
for (var i = 0; i < featureCollection.features.length; i++) {
var feature = featureCollection.features[i];
lineString.geometry.coordinates.push(feature.geometry.coordinates[0]);
}
lineString.geometry.coordinates.push(featureCollection.features[featureCollection.features.length - 1].geometry.coordinates[1]);
return lineString;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment