lineSplit doesn't split correctly

[andersfalk]

LineSplit is a great feature but it doesn't work as expected. I use a simple Polygon (triangle) as a splitter to split a simple four-point LineString. This should result in three LineStrings but only two are produced:

var line = {
    type: "Feature",
    geometry: {
        type: "LineString",
        coordinates: [[13.8716,56.2783],[13.8715,56.2785],[13.8743,56.2794],[13.8796,56.2746]]
    }
};
var splitter = {
    type: "Feature",
    geometry: {
        type: "Polygon",
        coordinates: [[[13.8726,56.2786],[13.8716,56.2786],[13.8713,56.2784],[13.8726,56.2786]]]
    }
};
var split = turf.lineSplit(line, splitter);

Returns this collection:

{
    type: "FeatureCollection",
    features: [{
        type: "Feature",
        geometry: {
            type: "LineString",
            coordinates: [[13.8716, 56.2783], [13.871532142857145, 56.27843571428571]]
        }
    },
    {
        type: "Feature",
        geometry: {
            type: "LineString",
            coordinates: [[13.871532142857145, 56.27843571428571], [13.8715, 56.2785], [13.8743, 56.2794], [13.8796, 56.2746]]
        }
    }]
}

Instead of this:

{
    type: "FeatureCollection",
    features: [{
        type: "Feature",
        geometry: {
            type: "LineString",
            coordinates: [[13.8716, 56.2783], [13.871532142857145, 56.27843571428571]]
        }
    },
    {
        type: "Feature",
        geometry: {
            type: "LineString",
            coordinates: [[13.871532142857145, 56.27843571428571], [13.8715, 56.2785], [13.871811111111098, 56.2786]]
        }
    },
    {
        type: "Feature",
        geometry: {
            type: "LineString",
            coordinates: [[13.871811111111098, 56.2786], [13.8743, 56.2794], [13.8796, 56.2746]]
        }
    }]
}

This is my first post ever on GitHub, so please be kind if I'm doing something wrong. Have searched earlier issues and haven't seen this bug report.

[rowanwins]

Hey @andersfalk

Thanks for a great first bug report, test cases like you provided are always super helpful!

When I've got a computer turned on i'll take a look into things and report back.

[sroettering]

@andersfalk In your example it looks like you swapped the coordinates of the line and the polygon.

I found another case today, where lineSplit does not split correctly:

it('should split the line in three parts', () => {
  const poly = polygon([[
    [10.41993839, 50.0301184],
    [10.42587086, 50.02630702],
    [10.41993839, 50.02249594],
    [10.41400592, 50.02630702],
    [10.41993839, 50.0301184],
  ]]);
  const line = lineString([
    [10.424716, 50.024888],
    [10.417643, 50.029512],
  ]);
  expect(lineSplit(line, poly).features.length).toBe(3);
});

In the result the lineString inside the polygon is missing.
This is pretty bad since I'm using the LineSplit function for slicing polygons.

[andersfalk]

@sroettering My example has one polyline and one polygon where the polyline is much larger than the polygon. I think the example is ok.
I'm doing the opposite compared to what you want to achieve, i.e. I really want to split a linestring inte smaller linestrings using a polygon. I solved my problem by writing my own function using lineIntersect. Unfortunately it won't help you, otherwise I'd be happy to post my code.

[sroettering]

I would be very interested in your code, if you could post it somewhere.
In my polygon slicing function I also need to split a linestring with a polygon and this is exactly where lineSplit fails for me.

[andersfalk]

This is the code. It can probably be cleaned up. @rowanwins, if this code in any way helps you with your implementation of lineSplit, please feel free to use any part.

function lineSplit(line, area) {
    var splitOwn = turf.featureCollection([turf.lineString(line.geometry.coordinates)]);

    // dispatch all intersections
    var intersections = turf.lineIntersect(line, area).features;
    for (var i = 0; i < intersections.length; i++) {
        var point = intersections[i];

        // check if intersection is on line
        for (var j = 0; j < splitOwn.features.length; j++) {
            var lineString = splitOwn.features[j];

            if (!point || turf.pointToLineDistance(point, lineString) > .00001)
                return;

            // split line into two
            splitOwn.features.splice(j, 1);
            var pointStart = turf.point(lineString.geometry.coordinates[0]);
            var pointStop = turf.point(lineString.geometry.coordinates[lineString.geometry.coordinates.length-1]);
            splitOwn.features.push(turf.lineSlice(pointStart, point, line));
            splitOwn.features.push(turf.lineSlice(point, pointStop, line));

            point = null;
        }
    }

    // remove short splits
    for (var i = splitOwn.features.length-1; i >= 0; i--) {
        if (turf.length(splitOwn.features[i]) < .00001)
            splitOwn.features.splice(i, 1);
    }

    return splitOwn;
}

[jonsadka]

Another example where line-split doesn't seem to work as intended:

const line = {
  "type": "Feature",
  "properties": {},
  "geometry": {
    "type": "LineString",
    "coordinates": [
      [-0.1315423281249999, 51.498954046875],
      [-0.2066106601562549, 51.501714871093746]
    ]
  }
}

const area = {
  "type": "Feature",
  "geometry": {
    "type": "MultiPolygon",
    "coordinates": [
      [
        [
          [-0.118946, 51.507589],
          [-0.120549, 51.506011],
          [-0.121109, 51.504837],
          [-0.122793, 51.494529],
          [-0.126877, 51.494849],
          [-0.132243, 51.494917],
          [-0.13236, 51.494561],
          [-0.133341, 51.493736],
          [-0.133768, 51.493024],
          [-0.135071, 51.493265],
          [-0.135241, 51.493416],
          [-0.136939, 51.493215],
          [-0.136254, 51.494018],
          [-0.136508, 51.494101],
          [-0.13641, 51.494325],
          [-0.13658, 51.494439],
          [-0.1372, 51.493763],
          [-0.13756, 51.493824],
          [-0.137717, 51.493651],
          [-0.138005, 51.493271],
          [-0.137874, 51.49295],
          [-0.138043, 51.492756],
          [-0.140895, 51.494193],
          [-0.142141, 51.495561],
          [-0.142633, 51.496576],
          [-0.144843, 51.496721],
          [-0.146308, 51.497232],
          [-0.148472, 51.499797],
          [-0.151624, 51.501861],
          [-0.149854, 51.502533],
          [-0.146627, 51.502363],
          [-0.144329, 51.500803],
          [-0.1429, 51.500173],
          [-0.14245, 51.499615],
          [-0.142095, 51.49976],
          [-0.141583, 51.499356],
          [-0.141902, 51.498814],
          [-0.141664, 51.498761],
          [-0.141376, 51.498936],
          [-0.14143, 51.4991],
          [-0.141142, 51.499182],
          [-0.141157, 51.499474],
          [-0.140766, 51.499343],
          [-0.140668, 51.499254],
          [-0.140779, 51.499288],
          [-0.141208, 51.498647],
          [-0.140382, 51.498418],
          [-0.140073, 51.498834],
          [-0.139599, 51.498745],
          [-0.138706, 51.499246],
          [-0.138013, 51.499036],
          [-0.136656, 51.499322],
          [-0.136871, 51.499694],
          [-0.136078, 51.500495],
          [-0.136108, 51.50072],
          [-0.139119, 51.500412],
          [-0.140299, 51.501528],
          [-0.140074, 51.501731],
          [-0.140125, 51.502048],
          [-0.137076, 51.503299],
          [-0.136058, 51.502388],
          [-0.134671, 51.50293],
          [-0.133142, 51.503165],
          [-0.132246, 51.502994],
          [-0.130807, 51.503073],
          [-0.128764, 51.502274],
          [-0.126154, 51.502112],
          [-0.126181, 51.504271],
          [-0.126373, 51.504867],
          [-0.125187, 51.504965],
          [-0.123125, 51.504654],
          [-0.122836, 51.505484],
          [-0.122976, 51.505517],
          [-0.122442, 51.506558],
          [-0.123198, 51.506741],
          [-0.122709, 51.507417],
          [-0.123156, 51.507715],
          [-0.122416, 51.507982],
          [-0.121121, 51.507993],
          [-0.120446, 51.508623],
          [-0.119841, 51.508397],
          [-0.118946, 51.507589]
        ]
      ]
    ]
  }
}

[jonsadka]

The solution here seems to work as expected https://github.com/Turfjs/turf-line-slice-at-intersection/blob/master/index.js#L109

[crubier]

Another example where it fails, this seems pretty common:

const result = lineSplit(
      {
        type: "Feature",
        properties: {
          index: 0,
          stroke: "#ff00c8",
          "stroke-width": 2,
          "stroke-opacity": 1,
          intersectingIndex: 2
        },
        geometry: {
          type: "LineString",
          coordinates: [
            [-9.284582069501932, 38.68554008224343],
            [-9.286108016967773, 38.66594353859579],
            [-9.264135360717773, 38.6648042445158],
            [-9.263504188862719, 38.678904253099795]
          ]
        }
      },
      {
        type: "Feature",
        properties: {
          index: 4,
          stroke: "#1e00ff",
          "stroke-width": 2,
          "stroke-opacity": 1
        },
        geometry: {
          type: "LineString",
          coordinates: [
            [-9.255123138427734, 38.65716380410655],
            [-9.289369583129883, 38.68772067467188]
          ]
        }
      }
    );

Result is:

{
  "features":  [
     {
      "geometry":  {
        "coordinates":  [
          -9.28473432383367,
          38.683584799558915
        ],
        "type": "Point"
      },
      "properties":  {},
      "type": "Feature"
    },
     {
      "geometry":  {
        "coordinates":  [
          -9.264118106633084,
          38.66518969063523
        ],
        "type": "Point"
      },
      "properties":  {},
      "type": "Feature"
    }
  ],
  "type": "FeatureCollection"
}

While it should be made of 3 segments...

But for the record, lineIntersect gives the right answer (2 intersection points).

[crubier]

I had to modify @andersfalk code to make it work:

export const lineSplit = (line, splitter) => {
  const splitOwn = featureCollection([lineString(line.geometry.coordinates)]);

  // dispatch all intersections
  const intersections = lineIntersect(line, splitter).features;
  for (let i = 0; i < intersections.length; i++) {
    let point = intersections[i];

    // check if intersection is on line
    for (let j = 0; j < splitOwn.features.length; j++) {
      const lineString = splitOwn.features[j];

      if (!point) {
        break;
      }

      if (pointToLineDistance(point, lineString) > 0.00001) {
        // Too far, this point is not on this segment
        continue;
      }

      // split line into two
      splitOwn.features.splice(j, 1);
      const pointStart = turfPoint(lineString.geometry.coordinates[0]);
      const pointStop = turfPoint(
        lineString.geometry.coordinates[
          lineString.geometry.coordinates.length - 1
        ]
      );
      splitOwn.features.push(lineSlice(pointStart, point, line));
      splitOwn.features.push(lineSlice(point, pointStop, line));

      point = null;
    }
  }

  // remove short splits
  for (let i = splitOwn.features.length - 1; i >= 0; i--) {
    if (length(splitOwn.features[i]) < 0.00001) splitOwn.features.splice(i, 1);
  }

  return splitOwn;
};

[crubier]

Related issue: #2023

The function above uses lineSlice, but lineSlice is super imprecise

[hanneshdc]

I've found the cause of this issue, but don't have a solution yet. The line split algorithm is missing segments to split as they aren't being found by the rbush.search query.

For more detail, the line split algorithm seems to work like this:

1. Find all intersections between lines using turf's lineIntersect method. We call these the "splitters"
2. For each splitter, find the feature and the line segment within that feature to split on
3. Perform the split, saving the features

In step 2, the algorithm, uses the geojson-rbush package to perform the point-on-line search. No "epsilon" is being applied here, so any numerical drift will cause that check to miss. This isn't a bug with rbush, it's just that it shouldn't be used this way. I've attached a failing test that shows how a point on line check in rbush will miss features.

EDIT: Actually, it's due to the bbox of linesegments being calculated with turf-square, which will in many cases make a bbox that is smaller than the input bbox. This is due to how it calculates the aspect ratio in real distance, but then applies the square-ing in WGS-84.

This makes it an easy fix, remove the square step, and in fact the entire bbox calculation step, as it is already handled by geojson-rbush. I will make a PR.

[smallsaucepan]

Actually, it's due to the bbox of linesegments being calculated with turf-square, which will in many cases make a bbox that is smaller than the input bbox. This is due to how it calculates the aspect ratio in real distance, but then applies the square-ing in WGS-84.

Thanks for finding the root cause @hanneshdc. Do you know of an existing issue describing that problem in turf-square? Does #1727 cover it?

[hanneshdc]

No problem, I'm glad it's a reasonably simple fix.

Yes, #1727 describes the same issue, and fixing that will likely fix this as well. Though, I haven't tested that.

[hf-farmqa]

Time for me to pile on.
We are also running into this same issue.
Example:

const splitter = {
    "type": "Feature",
    "geometry": {
        "type": "LineString",
        "coordinates": [[-111.57071881384209, 49.58746705929172], [-111.57072743959235, 49.587462], [-111.57106608768505, 49.58726337153985], [-111.57109709453526, 49.587212], [-111.5711022620136, 49.58720343862349]]
    }
}

const line = {
      "type": "Feature",
      "geometry": {
        "type": "LineString",
        "coordinates": [[-111.570323, 49.587462], [-111.570824, 49.587462], [-111.571218, 49.587212], [-111.571075, 49.587212], [-111.566432, 49.584359]]
      }
}

const result = turf.lineSplit(line, splitter);

result should contain 3 line strings but ends up only having two.

The fix proposed by @hanneshdc within PR #2460 solves the issue for us in this case. As they call out, this is possibly better achieved via #1727.

Is there any follow up on this issue? Or hope of it getting merged into an upcoming release?

[kudlav]

Another case. Removing bbox proposed by @hanneshdc within PR #2460 solves this case.

const line = {
  type: "Feature",
  properties: {},
  geometry: {
    type: "LineString",
    coordinates: [ [0, 44], [25, 38], [27, 40], [0, 62] ],
  },
};

const splitter = {
  type: "Feature",
  properties: {},
  geometry: {
    type: "Polygon",
    coordinates: [[ [0, 20], [42, 20], [42, 39], [28, 39], [0, 52], [0, 20] ]],
  },
};

turf.lineSplit(line, splitter); // returns single line

https://gist.github.com/kudlav/3ce18d90d6eca7ea2712a8b1794b14eb

[alanwhy]

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "coordinates": [
          115.83114410065377,
          40.37506121019869
        ],
        "type": "Point"
      }
    },
    {
      "type": "Feature",
      "properties": {
        "length": 629.28
      },
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [
            115.83057570721067,
            40.37506120837617,
            50
          ],
          [
            115.83057571943345,
            40.373461821449645,
            50
          ],
          [
            115.83114371137842,
            40.37346182327095,
            50
          ],
          [
            115.83114371186996,
            40.37506121019994,
            50
          ],
          [
            115.83171171915369,
            40.375061208376245,
            50
          ],
          [
            115.83171170594777,
            40.37346182144974,
            50
          ]
        ]
      }
    }
  ]
}

Use this point to divide the line below and return only one feature