New module @turf/polygon-slice

[DenisCarriere]

New module @turf/slice @turf/polygon-slice, currently on slice branch

Contributions and comments are welcomed before we publish to TurfJS.

Example

var sliced = turf.polygonSlice(polygon, linestring);

Current fallbacks of PolyK

• Linestring is limited to two segments
• Coordinate precision is limited to a few decimal points.
• Output & Input is a very strange array [x1 y1, x2, y2, ...]

JSDocs

/**
 * Takes a {@link Polygon} and cuts it with a {@link Linestring}. Note the linestring must be a straight line (eg made of only two points).
 * Properties from the input polygon will be retained on output polygons. Internally uses [polyK](http://polyk.ivank.net/) to perform split.
 *
 * @name slice
 * @param {Feature<Polygon>} poly - single Polygon Feature
 * @param {Feature<LineString>} line - single Polyline Feature
 * @return {FeatureCollection<Polygon>} A FeatureCollection of polygons
 */

Input

Output

Benchmark

$ node bench.js
simple x 117,605 ops/sec ±0.57% (98 runs sampled)

CC: @Turfjs/ownership

[mourner]

Not a fan of bringing yet another computational geometry library as a dependency...

[DenisCarriere]

@mourner Thanks for your input, I totally agree with your comment. Recently I've sent over many commits to the library (https://github.com/MartyWallace/PolyK/commits/master) before including it as a dependency.

Mourner you are the expert in Javascript computational geo libraries (big fan).

I'm willing to "Turfify" this library to Zero dependency (only Turf dependencies).

@mourner Can you review it after it's done (~1-2 weeks).

[mourner]

@DenisCarriere oh, don't take my comment as the final word — it's just my first thought. Worth discussing. Additional questions that come to mind are:

• How much size does PolyK add to the bundle?
• How stable/robust/fast is the algorithm?
• How much of an overlap there is between JSTS (already a dependency) and PolyK?
• Is it really necessary to have this as a core package, or would it be easier to just publish as a separate module and free to use PolyK/any other deps needed?

@morganherlocker @tcql thoughts?

[morganherlocker]

Same questions as @mourner for me, and one more. I definitely think this could be useful as a core module.

What should the behavior be when a line partially slices a polygon, but does not fully cleave it into 2+ parts? I ask because this is a bit ambiguous and one seemingly intuitive behavior (it inserts a new self-touching edge(s)) would lead to invalid geometries.

[DenisCarriere]

Ok I've got a first draft (80% done), I really like the idea of having this as a core module without even the JSTS dependency.

I've built the @turf/slice @turf/polygon-slice module entirely from TurfJS modules.

TurfJS dependencies

• @turf/meta (iterate over coordinates)
• @turf/point-on-line (Detects edges where to cut)
• @turf/inside (Helps detect if line is inside polygon)
• @turf/helpers (duh)

Issues with TurfJS dependencies

• @turf/line-slice Had to refactor this one a bit, had issues when trying to match the exact coordinate of a line, the slice always had an offset. Also need to find a way to do a reverse slice, the linestring giving has the same start & end coordinate.

Next steps

• Cleaving into 2+ parts would definitely be a challenge, I don't think it's impossible. If a line cleaves 1 or 2 or 3 parts, the output will always be a FeatureCollection<Polygon> with the parts inside the collection. If the linestring did not slice any parts, the polygon is simply returned as a FeatureCollection<Polygon>. I also I think the properties of the original polygon should translate down into the sliced pieces (no additional properties).
• Slicing polygons with holes (donuts), big challenge 👍

Performance
As for performance, it's decent... (could always be faster).

complex x 2,752 ops/sec ±0.64% (98 runs sampled)
exact-coordinates x 2,825 ops/sec ±3.06% (92 runs sampled)
half-outside x 6,600 ops/sec ±0.67% (100 runs sampled)
outside x 17,133 ops/sec ±0.69% (98 runs sampled)
simple x 3,034 ops/sec ±0.99% (97 runs sampled)

Debugging

I've got some "fancy" looking debug geojson results.

https://github.com/Turfjs/turf/tree/slice/packages/turf-polygon-slice/test/out

Debug mode

Actual ouput

CC: @mourner @morganherlocker

[rowanwins]

Nice one @DenisCarriere - looks like you're making good progress!

[DenisCarriere]

:) thanks, it's definitely shaping up, I might need to take a step back and fix/improve/test some of the turfjs modules I'm using as dependencies.

[DenisCarriere]

@rowanwins Ok this module is long overdue... I'm going to work on this today/week.

A few modules I've needed before to make this possible:

• geojson-rbush (GeoJSON implementation of RBush)
• @turf/line-segment
• @turf/line-intersect

[erikh2000]

@DenisCarriere I just got done doing the "new project" setup stuff, and am digging into polygonSlice(). A thing that confuses me with the current implementation is that it returns a FeatureCollection of Linestrings. I thought it was supposed to return sliced polygons. Is that just "work in progress" status of the polygonSlice() function? Or maybe I'm confused about how the function is intended to work.

[DenisCarriere]

Polygon Slice should return a FeatureCollection of Polygons, it might of still been in Debugging mode.

In reality Polygons are simply just a collection of connected lines, only difference is the Inner & Outer rings which can be determined by the Winding.

The slice branch would be considered a "work in progress" (aka: full rewrite).

Ref:

• https://github.com/Turfjs/turf-is-clockwise => @turf/boolean-clockwise
• https://macwright.org/2015/03/23/geojson-second-bite.html#winding

[erikh2000]

Okay, thanks, that makes sense. I just wanted to make sure I wasn't missing something in what the function was supposed to do.

[stebogit]

Just as an update note, @turf/boolean-clockwise is now integrated as TurfJS module

[alexgleith]

Hey @DenisCarriere, I'm looking at this today, as I did have it working, but the @turf/polygonize function is no longer returning two features for the split... it seems to be cleverly dissolving the split line component.

So, I wonder if you have any thoughts about a way to go about re-uniting the lines that are output currently into polygon features?

Another thing, I think it should work for multi-polygon features. Not sure the best way to do that, but though having another path with some recursion would sort it out?

[alexgleith]

Hey @DenisCarriere

One more note. I realised that the issue causing the polygonize to fail is in line splitting. In the simple example in the test cases, the lines that are split up the top of the feature split differently depending on if you split the line with the polygon or the polygon with the line.

Evidence 1 - this is the difference between the split points:

Evidence 2 - this is the output of polygonize with the bad topology:

Evidence 3 - this is the output of polygonize after doing a truncate on the split features:

In running through the tests, I think my fix is a bad workaround to what is perhaps an issue in the line-splitter. I might put together a test case and a bug report.

[DenisCarriere]

@alexgleith Great job!

it seems to be cleverly dissolving the split line component.

🤔 That's annoying and good at the same time...

I think it should work for multi-polygon features.

👍 Agreed, however getting Polygon to work first would be the first step.

perhaps an issue in the line-splitter

🤔 Definitely submit a test case for the line splitter, we can look into fixing that first.

[alexgleith]

Definitely submit a test case for the line splitter, we can look into fixing that first.

Ok, I'll do that now.

I have some working code for handling MultiPolygons. Not sure if it fits into the Turf 'standard way of doing things' but it works. Will leave it for now, as it's pretty trivial, but I can put a PR together if you like.

[alexgleith]

Hey @DenisCarriere, here's an issue and it links a PR with a test case.

[DenisCarriere]

Thanks @alexgleith for submitting this, this will be useful as reference whenever someone tackles this issue.

At the moment I'm not too sure where to start with this issue. 🤷‍♂️

[skaletech]

We've added a function that may be of interest based on the original Turf-cut found here: https://github.com/Turfjs/turf-cut

Here it is: https://github.com/skaletech/turf-cut

It works by creating a small buffer around the linestring, then calling turf.difference, then zipping points near the line to the line, then filtering out duplicate points. This may not work for every use case, but it works well in our use case where points are usually much more distant than the tolerance input.

Also, one small improvement would be to test whether a point was in the original polygon before allowing it to be 'zipped'.

[DenisCarriere]

@skaletech Cool work! Seems like a nice hack around the solution, unfortunately I don't think we would adopt this approach for the Polygon Slice, but it's very cool to see that this works for your use case. 👍

[skaletech]

Yep, we needed to allow for multiple line segments and self intersection.

So for example:

We'd love to get a non-hack version if anyone has one.

[gdrouet]

Looking for this feature! It would be useful to split polygons that are too big.

[sroettering]

Any update on this?

[alexgleith]

I've had another look at the code, and ran it with the tests, and I have found that there are some issues.

I'm actually using it in production, with a couple of changes to the code here, including using polygonize on the output before it's returned and truncate on each of the features before they're polygonized. But with the test data, there are issues due to coordinate precision, where the polygonize process either fails or merges the split polygons back together! It's kind of hard to solve neatlly...

[rowanwins]

Gday @alexgleith

Can you put up a pull request to a new branch with your version and I should be able to take a look. It would be great to get this module going because people have already put alot of effort it, it's just that final push to get it over the line!

[rowanwins]

PS also dropping a note here about this blog post and associated repo

PPS which also reminds me that it would be cool to have a isConcave() module - if you know a poly is concave then you can use that information to determine which algorithm you might use....

[alexgleith]

Hey @rowanwins

My changes aren't significant, but here they are: https://github.com/alexgleith/turf/tree/slice

This commit captures it: alexgleith@1a47118

I really do think that this issue is part of the cause... I don't know how to fix it! Maybe implementing a more complex algorithm (as you've linked to) is the way to go.

[rowanwins]

Thanks for those links @alexgleith and your work on the module, will try and take a look this evening and see if I can find a clever way around it.

[daudihusbands]

@alexgleith I downloaded from your repo but I don't know how to build it. Sorry, I'm a newb to this stuff.

[rowanwins]

Hi @daudihusbands

You might be able to download @alexgleith repo - then

cd turf (where you downloaded the repo to)
npm install
rollup

This should generate a main.js file containing the bundled up version of Turf. The rollup command might require you to have rollup installed globally (eg npm install rollup -g). Hope that helps.

[rowanwins]

FYI I did look into this a little while back and the impression I got was that there would probably be benefit in moving to a more known algorithm like the one suggested above

[daudihusbands]

Thank you for your speedy response. Are you referring to the algorithm by @skaletech?

[alexgleith]

Hey @daudihusbands, the code I supplied does not work in all cases, so beware! It does work for most of my cases, though, and I'm using it in production.

[daudihusbands]

Thanks for the heads up @alexgleith. I am testing it out now. I'll post feedback if I run into any issues. Really appreciate your help. BTW, I didn't get rollup to work. I did notice that the config file is referring to index.js but I didn't find that file. No worries though, I copied the your code into my file.

[IsabellaCHY]

When is this module updated? Is there a better solution? This method is urgently needed now。

[avinashbitra]

Any timeline in when will this feature gets released ?

[morganherlocker]

When is this module updated? Is there a better solution? This method is urgently needed now。

Any timeline in when will this feature gets released ?

I am not aware of anyone working on this algorithm at the moment. The proposed solutions so far do not appear robust enough to make it to production. I would suggest using a lower level module or writing one yourself, and if that module works well, we can add it as a dependency in turf with a normalized interface.

[woodland-solutions-group]

Correct me if I'm wrong, but it seems like this feature was never added to Turf. We're simple in our Turf use so we updated the apparently abandoned Turf/turf-cut to work with the latest version of Turf and converted the module into a plain function. It's less elegant than @skaletech's solution above which you should review as well.

If it helps anyone who ends up here like we did, here's a link:
https://github.com/woodland-solutions-group/turf-cut

Since it's a hack I assume we should stop there. Please let me know if otherwise and we can try jumping the hoops to add it as a Turf module.

[eric-g-97477]

I too would like to see a supported way in turf to split a polygon instead of relying on another library.

Any chance this could happen?