Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

lineSplit doesn't split correctly #1232

Open
andersfalk opened this issue Jan 22, 2018 · 16 comments · May be fixed by #2460
Open

lineSplit doesn't split correctly #1232

andersfalk opened this issue Jan 22, 2018 · 16 comments · May be fixed by #2460

Comments

@andersfalk
Copy link

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
Copy link
Member

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.

@rowanwins rowanwins added the bug label Jan 28, 2018
@sroettering
Copy link

sroettering commented Jan 31, 2018

@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
Copy link
Author

@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
Copy link

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
Copy link
Author

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
Copy link

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
Copy link

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

@crubier
Copy link

crubier commented Jan 27, 2021

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
Copy link

crubier commented Jan 27, 2021

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
Copy link

crubier commented Jan 27, 2021

Related issue: #2023

The function above uses lineSlice, but lineSlice is super imprecise

@hanneshdc
Copy link

hanneshdc commented Jul 20, 2023

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
Copy link
Member

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
Copy link

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
Copy link

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
Copy link
Contributor

kudlav commented Jul 16, 2024

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
Copy link

alanwhy commented Jul 22, 2024

{
  "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
          ]
        ]
      }
    }
  ]
}
image

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.