turf-clip for fast clipping to rectangular area

[mourner]

We need a new module for rectangular area clipping, turf-clip. Using turf-intersect for this purpose is extremely inefficient, since it both uses monstrous JSTS and is a generic clipping algorithm which is much slower than a simple axis-aligned rectangular clipping could have been.

Here is a sample use case where features are clipped to a tile bbox using turf-intersect, making things much slower than they could have been: https:/mapbox/tile-reduce/blob/be8be60d1c575514a9d4bda74d2d6ca6ab5f6854/index.js#L136

For LineString and MultiLineString, https:/mapbox/lineclip should be great. One recent place where I replaced turf-intersect with lineclip got from 1000ms to 20ms.

For Polygon and MultiPolygon, I suggest writing a Sutherland-Hodgeman implementation (related: #139) in a separate module, similar to lineclip. It makes degenerate edges, yes, but it's not important for a lot of cases (tile-reduce is one).

@morganherlocker @tcql

[anandthakker]

👍 x 💯 !

[rowanwins]

Gday @mourner

I've had a first crack at this
https:/rowanwins/turf-clip

Basically I've just implemented the Sutherland-Hodgeman js code here.

var turf = require('turf');

var inputPoly= {"type": "Feature", "properties": {}, "geometry": {"type": "Polygon", "coordinates": [[[60.46875, 45.089035564831036 ], [34.80468749999999, 30.44867367928756 ], [42.5390625, 21.28937435586041 ], [59.765625, 13.239945499286312 ], [74.1796875, 24.206889622398023 ], [68.90625, 37.71859032558816 ], [60.46875, 45.089035564831036 ] ] ] } }; 

var clipPoly = {"geometry": {"type": "Polygon", "coordinates": [[[42.1875, 19.31114335506464 ], [42.1875, 41.50857729743935 ], [71.71875, 41.50857729743935 ], [71.71875, 19.31114335506464 ], [42.1875, 19.31114335506464 ] ]] }};
var clipResult = turf.clip(inputPoly, clipPoly);

which returns the original feature with properties just trimmed to the new shape

{"type":"Feature","geometry":{"type":"Polygon","coordinates":[[[67.74511539957585,19.311143355064637],[46.77266970143686,19.311143355064637],[42.539062499999964,21.28937435586041],[42.18749999999999,21.705706143288925],[42.18750000000001,34.660284632663085],[54.19232695312729,41.50857729743936],[64.56756840926896,41.50857729743935],[68.90625,37.7185903255882],[71.71875,30.51234995055347],[71.71875,22.334484528208222],[67.74511539957585,19.311143355064637]]]},"properties":{}}

This seems to work ok for simple polygons but is failing for more complex polygons but Im not sure why at this stage... I think there is something wrong with the js from the site I referenced above as even their jsfiddle returns incorrect results depending on the inputs
eg http://jsfiddle.net/rowanwins/4x4jwnkL/

Anyway there is something off to a start... happy for any other contributors who know more about maths and algorithms :)

[mourner]

@rowanwins actually I have a solid and fast Sutherland-Hodgeman implementation that was battle-tested for 5 years as a part of Leaflet. I've been meaning to extract, clean up and release it as a separate module for some time. Maybe I'll do that today to go alongside my lineclip module.

[rowanwins]

No worries @mourner , let me know if I can assist otherwise I'll leave it with you

[mourner]

Added Sutherland-Hodgeman polygon to rectangle clipping to https:/mapbox/lineclip. The implementation is extremely fast and 100% test-covered. So what's left is simply a wrapper Turf module that would handle GeoJSON input and output GeoJSON.

[mourner]

Got some bugs fixed in lineclip with more test coverage so it should be all settled. BTW maybe turf-bbox-clip would be a better name (more explicit)?

[tcql]

maybe turf-bbox-clip would be a better name

💯 sounds great to me. I started pulling this together, will get it out today, probably.

[rowanwins]

fyi @tcql I've deleted my repo just for clarity

[tcql]

@mourner @rowanwins It's alive! Here's what I've got: https:/Turfjs/turf-bbox-clip

It also occurred to me that this could easily be extended to iteratively clip collections.

There are some quirks to results with polygons - notably S-H degeneracies, and issues where holes cross the bbox. See this which produces this when clipped. You would probably expect the hole to be dissolved into the polygon, but without adding more in depth clipping here, this is what we've got

[mourner]

@tcql great! This is all fully expected with Sutherland-Hodgeman clipping, I don't think it's a problem that should be addressed.

[morganherlocker]

I don't think it's a problem that should be addressed.

This would go outside the norm. I can definitely see this generating a lot issues from users who do not know or care about the algorithmic explanation for a degeneracy. Generally speaking, we shoot for the "just works as expected" level of use. Obviously, this is limiting in some ways, but it's a tradeoff we have made so far. I am open to tweaking this expectation, but if we do, we should keep in mind users with little to no level of computational geometry expertise (>95% of the users).

Also, users who need speed and understand algorithm minutiae tend to be much more amenable to integrating external modules.

[mourner]

I don't see it generating any issues if users are told what this module does exactly, e.g. using this illustration. Most users with little to no level of computational geometry expertise won't care for degenerate edges, it will just work.

We're talking about hundreds to thousands of times faster here, not just a minor performance tweak, and it more that justifies any ambiguity of edge handling in my opinion. Performance is Turf's feature. All users need it even if they don't know it. Placing this module outside of Turf will lead to people never knowing about it and continuing to use turf.intersect on a rect polygon because they don't know how horribly slow it is, and take this performance for granted.

[tcql]

@mourner @morganherlocker maybe an option long run (once we have turf-makevalid or something) is to provide a high-precision option. If you are working in cases where you know you won't have degenerate cases or you know you don't care, it'd be awesome to be as ⚡ fast as possible.

[anandthakker]

I don't see it generating any issues if users are told what this module does exactly, e.g. using this illustration. Most users with little to no level of computational geometry expertise won't care for degenerate edges, it will just work.

@mourner I think once jsts is removed you'll probably be right about that, but until then, note that I've definitely encountered a number of cases where, because of jsts, they cause things like turf-intersect, turf-union, etc. to blow up.

[DenisCarriere]

👍 Sounds like a good idea, once we finish @turf/polygon-slice I think this module would be relatively easy to create.

[mourner]

@DenisCarriere it was already built by @tcql a few years ago (https:/Turfjs/turf-bbox-clip), just needs an update and integration into the monorepo.

[DenisCarriere]

Yes for the bbox one is covered, however it would be nice to have both @turf/clip & @turf/bbox-clip, both of them would have drastically different dependencies.

The @turf/clip would most likely need @turf/polygon-slice.

👍 turf-bbox-clip

[DenisCarriere]

Closing in favor of PR #652