New module @turf/polygon-slice

DenisCarriere commented 7 years ago

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 commented 7 years ago

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

DenisCarriere commented 7 years ago

@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 commented 7 years ago

@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 commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

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

DenisCarriere commented 7 years ago

:) 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 commented 7 years ago

@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 commented 7 years ago

@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 commented 7 years ago

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:

erikh2000 commented 7 years ago

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 commented 7 years ago

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

alexgleith commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

@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 commented 7 years ago

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 commented 7 years ago

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

DenisCarriere commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

@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 commented 7 years ago

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 commented 6 years ago

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

sroettering commented 6 years ago

Any update on this?

alexgleith commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

Hey @rowanwins

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

This commit captures it: https://github.com/alexgleith/turf/commit/1a47118892b5318bcc16aa3022a07c58b8d572b1

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 commented 6 years ago

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 commented 6 years ago

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

rowanwins commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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

alexgleith commented 6 years ago

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 commented 6 years ago

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 commented 5 years ago

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

avinashbitra commented 5 years ago

Any timeline in when will this feature gets released ?

morganherlocker commented 5 years ago

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 commented 2 years ago

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 commented 1 year ago

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?

Turfjs / turf

New module @turf/polygon-slice #580