lineSplit doesn't split correctly #1232

andersfalk · 2018-01-22T15:55:25Z

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.

The text was updated successfully, but these errors were encountered:

rowanwins · 2018-01-22T20:03:16Z

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 · 2018-01-31T15:38:13Z

@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 · 2018-01-31T16:04:06Z

@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 · 2018-01-31T16:26:11Z

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 · 2018-01-31T16:52:53Z

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 · 2019-08-15T23:36:55Z

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 · 2019-08-15T23:41:08Z

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

crubier · 2021-01-27T19:39:12Z

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 · 2021-01-27T21:31:58Z

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 · 2021-01-27T23:55:32Z

Related issue: #2023

The function above uses lineSlice, but lineSlice is super imprecise

hanneshdc · 2023-07-20T12:59:13Z

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:

Find all intersections between lines using turf's lineIntersect method. We call these the "splitters"
For each splitter, find the feature and the line segment within that feature to split on
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 · 2023-11-10T05:10:03Z

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 · 2023-11-12T19:03:02Z

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 · 2024-04-02T22:03:39Z

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 · 2024-05-06T13:20:14Z

Even after removing the square, it's not working properly for large geometries. I've created a related ticket #2604

rowanwins added the bug label Jan 28, 2018

crubier mentioned this issue Jan 28, 2021

nearestPointOnLine deviation #1440

Open

mfedderly added the @turf/line-split label Aug 3, 2021

This was referenced Jul 20, 2023

Return more information rowanwins/sweepline-intersections#13

Open

Fix Issue #1232 - Bug in turf-line-split #2460

Open

kudlav mentioned this issue May 7, 2024

splitLineWithPoints doesn't split correctly #2604

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

lineSplit doesn't split correctly #1232

lineSplit doesn't split correctly #1232

andersfalk commented Jan 22, 2018

rowanwins commented Jan 22, 2018

sroettering commented Jan 31, 2018 •

edited

andersfalk commented Jan 31, 2018

sroettering commented Jan 31, 2018

andersfalk commented Jan 31, 2018

jonsadka commented Aug 15, 2019

jonsadka commented Aug 15, 2019

crubier commented Jan 27, 2021 •

edited

crubier commented Jan 27, 2021

crubier commented Jan 27, 2021

hanneshdc commented Jul 20, 2023 •

edited

smallsaucepan commented Nov 10, 2023

hanneshdc commented Nov 12, 2023

hf-farmqa commented Apr 2, 2024

kudlav commented May 6, 2024 •

edited

lineSplit doesn't split correctly #1232

lineSplit doesn't split correctly #1232

Comments

andersfalk commented Jan 22, 2018

rowanwins commented Jan 22, 2018

sroettering commented Jan 31, 2018 • edited

andersfalk commented Jan 31, 2018

sroettering commented Jan 31, 2018

andersfalk commented Jan 31, 2018

jonsadka commented Aug 15, 2019

jonsadka commented Aug 15, 2019

crubier commented Jan 27, 2021 • edited

crubier commented Jan 27, 2021

crubier commented Jan 27, 2021

hanneshdc commented Jul 20, 2023 • edited

smallsaucepan commented Nov 10, 2023

hanneshdc commented Nov 12, 2023

hf-farmqa commented Apr 2, 2024

kudlav commented May 6, 2024 • edited

sroettering commented Jan 31, 2018 •

edited

crubier commented Jan 27, 2021 •

edited

hanneshdc commented Jul 20, 2023 •

edited

kudlav commented May 6, 2024 •

edited