turf
turf copied to clipboard
Turfjs
New module @turf/polygon-slice
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
Not a fan of bringing yet another computational geometry library as a dependency...
@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).
@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?
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.
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-sliceHad 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 aFeatureCollection<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
:) 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.
@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
@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.
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
Okay, thanks, that makes sense. I just wanted to make sure I wasn't missing something in what the function was supposed to do.
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?
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.
@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.
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.
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. 🤷♂️
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'.
@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. 👍
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.
Looking for this feature! It would be useful to split polygons that are too big.
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...
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!
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....
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.
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.
@alexgleith I downloaded from your repo but I don't know how to build it. Sorry, I'm a newb to this stuff.
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.