Turf: removing jsts dependency

[tmcw]

I see some TODO-like comments in the source https://github.com/morganherlocker/turf/blob/4a4772433b3deb6ae5f8dc9d24afbdd9c6555911/lib/erase.js#L4 but it seems like a good idea to veer away from too much jsts lineage since it's a rather huge project with its own lingo and internal formats.

---

• Polygon clipping modules require a new clipping algorithm like greiner-hormann. Greiner-Hormann is approaching release readiness, but still has some outstanding clipping issues.
  
  
  
  • [ ] turf-intersect
  
  
  • [ ] turf-difference
  
  
  • [ ] turf-union
  
  
• Buffering requires a solution to buffering arbitrary polygons. @morganherlocker has made progress buffering other geometries, but polygons are still not ready.
  
  
  
  • [ ] turf-buffer
  
  

Evaluate this for an implementation guide:

https://github.com/akavel/polyclip-go/blob/master/clipper.go

[tmcw]

jsts's portion of the browserified version, via disc:

[morganherlocker]

Completely agree. I am using jsts very reluctantly at this point, as I have found it pretty challenging to debug and its size really hurts client-side viability (I personally only use turf in node.js, so this is less of a problem for me). Nonetheless, using it allowed me to wrap a high level api around a set of features that would have taken me months to develop on my own.

To get off jsts, we would need the following (I think this is a complete list):

• buffer (I wrote one that works with points, but lines and polygons are a lot more difficult)
• union
• difference
• intersect

I attempted to do a bit of reverse engineering from jsts, but these algorithms are pretty complex, and the fact that jsts uses a very "enterprisey" style makes it difficult to just pluck out the relevant bits. It might be much easier to borrow some ideas (or code) from one of the many geometry libraries out there such as jsclipper. It might not be the cleanest way to implement these features, but it has worked for others (like the bezier function, which was adapted from a canvas library) and I try not to let perfect be the enemy of good.

TLDR: I really want to do this, but am a bit swamped at the moment. I am getting close to feature completeness though, so I may have time to circle back to this in a couple months if no one else decides to tackle it before then.

[morganherlocker]

I have started porting jsclipper to node (the current implementation is heavily tied to the browser and contains a lot of code that optimizes it for various browsers).

Minified, I currently have it at 93kb, which is a lot better than the 500kb+ of jsts. This issue has become a big deal due to other issues relating to jsts using globals that blow up the browserify build for turf. Being clunky in the browser is one thing, but not working at all is unacceptable IMO. One big plus side to this approach is that jsclipper is blazing fast, and on top of that it has more buffer options than just about any "gis" type lib I have seen.

The downside is that the underlying code in turf will need to transform geojson to the jsclipper data structure, then transform the results back to geojson. I don't see this as a huge issue though in lieu of an existing geojson-oriented module... or me knowing how the hell to do it myself :)

The jsclipper code is a bit odd (ported from a C++, C#, & Delphi lib!), but still seems far more easy to read than the equivalent jsts internals, so this should not hurt "debugability" too much by comparison. Since I have started really using turf with the jsts dependencies, I have found it almost impossible to figure out what is going on when something goes wrong in jsts, which seems to be a symptom of a near direct Java to Javascript transformation with not much consideration of idioms. Jsts probably just needs some love, but I think the goal was simply a minimal port, so we might as well build something geared towards this problem space.

TLDR: Solution to this issue coming ASAP

[morganherlocker]

I have successfully forked jsClipper to a node compatible version:

https://github.com/morganherlocker/clipsy

Also, I have completed a conversion module for getting from geojson to jsclipper data and back.

https://github.com/morganherlocker/clipsy-geojson

The results look very promising, and I think I now have everything I need to implement this within turf for the functions listed above.

[tmcw]

Wow, jsClipper is some insane code

[maxogden]

unsolicited feedback:

in general I'd love to see more small modules for doing geo stuff and less grab-bags. e.g. there are nice simplification implementations in turf, topojson and mapshaper but they are part of much bigger coarse grained frameworks which doesn't work as well with browserify.

it might seem like more work to publish 30 modules instead of 1 but in practice I've tried both approaches many times and when you try and build something complex having fine grained dependencies (small modules) helps out a lot

[tmcw]

:+1: to that - the good thing is that turf right now is pretty decoupled internally so it's a good fit for splitting into little bits.

[morganherlocker]

@maxogden Unsolicited feedback is usually the best kind ;)

I tend to prefer the small module approach as well, and have thought about it from the beginning with turf. As @tmcw mentioned, the code structure is about as simple as it gets. Index.js is just a list of functions being gathered up, and if each of them pointed out to separate installed modules, it would work the same.

At the same time, I do think there is a balance between a framework that curates a set of utilities, and the more granular approach that lets people in the know build things however they want.

Perhaps a compromise might be to break out submodules automatically as part of each release. There would still be the full turf module, but if you wanted the minimum dependencies, you could just use turf-isoband, turf-smooth, turf-buffer, etc.

I have never tried this approach, so it may be totally zany. Any thoughts or suggestions would be appreciated.

Also, my main reason for wanting a single point of development (even with the submodule options) is that it makes testing much easier, and it minimizes duplicated browserify dependencies if you needed to use multiple submodules. The actual turf code accounts for a pretty small percentage of the browserified file, especially in comparison to jsts and topojson. I am pretty green though, and I am open to advice on this.

[maxogden]

I like the hybrid approach you proposed, it enables both modular and old school consumers. Re: duplicated subdependencies, npm dedupe will fix most of the issues there, assuming your shared dependencies don't make breaking changes that often.

In a scenario like this I think its best to attempt to minimize the number of shared dependencies. Implementations of low-level geo algorithms are probably a good place to start by breaking out into individual modules that don't have any dependencies, and then requiring those in the higher level turf APIs.

It's the conflation of these low-level algorithms and the high level APIs that is the most commonly frustrating thing that I see frameworks doing.

[morganherlocker]

@maxogden, @tmcw Quick update:

I am coming into the final stretch of fully modularizing turf. On the dependency front:

• Lodash is gone
• Async is gone
• simple-statistics stays (it is only 42kb unminified, and seems justified considering how much it is used)
• JSTS is gone. I have decided to take the JSTS code and extract the bare minimum for each of the transformation modules. This will allow me to gradually refactor the code to a more literate style, without having to spend 6 months writing all of these algos from scratch and retaining the ability to release turf. Also, other work has been in progress to refactor these algos for geodesic calculations, instead of 2d planar geometry.
• Topojson is gone. Topojson should be its own thing, and the turf topo function was just a wrapper. I was using it for simplification, but I will be switching that over to mourner's implementation. It will probably lose topology preservation, but users can always use the topojson version if they can swallow the overhead (mostly d3). I am still exploring this, however, so suggestions are welcome.
• Internal dependencies stay, but I will document best practices with npm-dedupe for optimizing custom builds

This has all been quite a bit of work, but I think the payoff will be huge. After the modules are complete:

• Re-document everything. I switched everything over to sync interfaces, so I will need to document the new usage patterns.
• CLI interfaces. I will create CLI interfaces for each of the modules. The end result (I hope) will be a badass, scriptable usage pattern, that will allow for turf to be used as a sort of super geo-REPL, or in makefiles the way @mbostocks sets up data visualizations.
• I will work on making turf "proper" a convenience lib that will package everything together. This will include npm deduping for builds, installing all of the cli modules in one place, and building docs/examples that show new users what you can do with turf in a holistic fashion for general analysis. People who know about these sorts of operations could already use other tools. I want to make turf the accessible solution that is beginner friendly.
• Setup some sort of CI environment that can handle this many modules all working in harmony. I am not sure about the specifics on this yet, but I would like turf "proper" to be able to get all of the latest versions of each of the module, run tests on travis for node, run tests in testling with most of the browsers on the browserify build, run perf benchmarks, etc.. We do not want an update to a submodule to break the larger build. @maxogden, do you have any good examples for this sort of thing, that I might be able to immitate?
• I will start to explore options with alternate streaming modules. The main win here would be reporting progress mid-process, since large datasets could take minutes/hours/days to run.

To be honest, I was a bit skeptical of the modular approach for this at first. Now that most of the work is done, I am optimistic that this will allow for the most flexible usage, which should lead to an increase in usability, and make it easier to contribute.

[maxogden]

@morganherlocker I think https://github.com/Raynos/mercury is a pretty cool example of a modular 'framework'. You can also run highly modular things on testling CI or travis pretty easily

[tmcw]

Adding to the 3.0.0 milestone: @morganherlocker can you top-edit this so that it describes the current overall state of this task - which turf modules still need de-JSTS'ing and what algorithms are required to do it, and what state are those tasks in?

[korczis]

Any news?

[tcql]

@tmcw edited OP to list which modules need de-JSTSing, and a bit about what the state of those solutions are.

@korczis It hasn't moved too much lately. We'll be working on scheduling time to knock out the remaining algorithmic challenges soon

[gajus]

We are only using turf-buffer to describe a circle around a point:

import turfPoint from 'turf-point';
import turfBuffer from 'turf-buffer';
import turfInside from 'turf-inside';

type TypePoint = [number, number];

/**
 * Check if `point` is within the circle with center `center` and radius `radius`
 */
export default (point: TypePoint, center: TypePoint, radius: number) : boolean => {
    let centerPoint,
        circleAroundCenter,
        insidePoint;

    centerPoint = turfPoint(center);
    insidePoint = turfPoint(point);

    circleAroundCenter = turfBuffer(centerPoint, radius, 'meters');

    return turfInside(insidePoint, circleAroundCenter);
};

Is there a away to do it without turfBuffer and get rid off jsts?

[tmcw]

turf-buffer depends on jsts, so, unfortunately, no

[gajus]

How would such a thing be called? "A function to generate a polygon describing a circle of certain radius using points as latitude and longitude"

I will do my research and see if I can put one together.

[tmcw]

For geodesic circles, you can use the radial method from https://github.com/mapbox/spherical to draw a circle around a point.

[gajus]

I just realised that since I simply need to check if a point is within a circle, all I need to do is check if distance from centre of the circle to the target is lesser than the radius, i.e.

import turfPoint from 'turf-point';
import turfDistance from 'turf-distance';
import turfInside from 'turf-inside';

type TypePoint = [number, number];

/**
 * Check if `point` is within the circle with center `center` and radius `radius`
 */
export default (point: TypePoint, center: TypePoint, radius: number) : boolean => {
    let centerPoint,
        insidePoint;

    centerPoint = turfPoint(center);
    insidePoint = turfPoint(point);

    return turfDistance(centerPoint, insidePoint, 'kilometers') * 1000 < radius;
};

[tmcw]

I'm moving this out of the 3.0.0 milestone. Removing JSTS continues to be Turf's excalibur. Whoever completes this task earns first-dibs when my mom sends cookies to the office.

[morganherlocker]

:+1: For anyone up for the challenge, I can verify that the cookies are _very_ good.

[anandthakker]

Couple questions for would-be seekers of the cookie:

Greiner-Hormann is approaching release readiness, but still has some outstanding clipping issues.

@tcql Is this still accurate? If so, are these outstanding issues atomic, squashable bugs, or more like high level revisions/refactors of the g-h module?

@morganherlocker has made progress buffering other geometries, but polygons are still not ready.

Is this the place to look?

[morganherlocker]

Is this the place to look?

correct @anandthakker. The most promising offset/buffer algorithm has been http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf

I've also looked into straight skeleton offset algorithms, but I have not had much luck getting any working, since the skeleton algorithm is a challenging lift by itself.

[tcql]

@tcql Is this still accurate?

@anandthakker We're looking into some alternatives to degeneracy handling that would simplify and theoretically get rid of remaining failures in GH. @mourner is using some tangential approaches to work on polygon fixing (kind of similar to ST_MakeValid), which could easily help us ditch remaining degeneracy issues.

are these outstanding issues atomic, squashable bugs, or more like high level revisions/refactors

per :point_up: :point_up:, it's more the latter

[ThomasG77]

You may not need to remove JSTS now.
Why? Because it seems the project is full ES6 compatible and you can use rollup.js to minimized the build size for buffer in particular.
You also do not use all JSTS buffer possibilities e.g http://bl.ocks.org/ThomasG77/31037a8897b4980a0818 (illustrated with OpenLayers 3)

[mourner]

@ThomasG77 oh, nice to see that it switched to ES6 modules! We should consider using rollup.js short term. The main reason to switch is performance though, not bundle size, so we're still pursuing our own implementation of polygon boolean operations.

[anandthakker]

@tcql @morganherlocker Just stumbled across https://github.com/w8r/polygon-offset, which certainly looks pretty lightweight. Haven't investigated the g-h implementation it relies on, but it seems promising. Readme cites the winding number paper that @morganherlocker referenced above

[aakashsigdel]

I think they have removed jsts.io.GeoJSONParse(); you will need to do jsts.io.GeoJSONWrite()

Changing this line in the index.js makes everything work :)

[bjornharrtell]

JSTS 1.1.0 is still a port of the original Java code but made with automatic translation this time. Since it has the Java heritage it is of course not optimal when it comes to size/performance but I wager it will be hard to beat its robustness and rigorous test suite. The full minimized build is 447 kB (old 0.x version was 575 kB). If using rollup to single out the buffer operation the build size will be about 227 kB. Still big but a significant improvement and it should also produce more reliable results overall.

[tmcw]

Is JSTS still generated AST->AST, or are you modifying the generated JS? codemods might help out with converting some Java-isms to more normal JavaScript across the entire codebase.

[bjornharrtell]

It's now AST->AST with no modifications plus supporting handwritten code. The old version that turf is using was actually a completely manual effort.

[jljorgenson18]

+1

[rowanwins]

cc @tcql @tmcw @morganherlocker

So I've just been taking a look at this and it looks like there appear to be a few robust options out there for this as mentioned by @anandthakker above.

These couple tackle intersects, difference and union
https://github.com/w8r/martinez
https://github.com/w8r/GreinerHormann

This one tackles buffering
https://github.com/w8r/polygon-offset

All of the above are light-weight, have test suites, are original js code (rather than ports of things) and are reasonably new.

If people were happy with them I'd be happy to rejig the existing turf modules to make use of these.

Cheers

[mourner]

I met the author of the above modules. They are great in-progress implementations, but as far as I know, they're not robust yet — they still have bugs and unhandled edge cases. @w8r want to weigh in?

[w8r]

Absolutely, i know more or less where the problem lies in my version of Martinez algorithm, w8r/martinez#8, I could use some help with that

[w8r]

I truly believe it can be fine-tuned
and there are plenty of test-cases for the buggy behaviour provided by the community

Aslo, I believe that the first two steps of the algorithm can be used for another algorithm that concerns offsetting http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf

[contra]

Current state of jsts in webpack:

jsts has a module attribute in the package.json to enable code splitting - couldn't a temporary workaround be for turf to also export this attribute (and use destructuring to get what it needs), so that only the parts of JSTS turf actually uses are included in the output?

[DenisCarriere]

It's not so much the filesize that worries me, the last time I attempted to use these so called code splitted modules I had tons of errors that depend on other external jsts modules, in the end I had to import the entire jsts library to make anything "complex" work.

Also, there's been a few reported issues with handling MultiPolygon geometries (https://github.com/Turfjs/turf/issues/702, https://github.com/Turfjs/turf/pull/674).

Instead of having a massive jsts library, it would be better to have different specialized libraries to handle those individual spatial operations (such as martinez) or have 100% internal TurfJS modules with zero external dependencies. @rowanwins is heading in the right direction to support @turf/boolean operations which will help significantly creating/updating TurfJS modules with controlled Input/Output types.

[bjornharrtell]

While I would welcome something more modern and modular (and in some cases faster) to replace jsts it has proven to be difficult, especially considering robustness. I would also like to see a replacement implemented in a high level language that can target multiple VMs, but mabye that's just an utopic dream.. :)

On "code splitting" (or rather dead code elimination or tree shaking) it should at least work. I do it with several internal projects using jsts, using https://github.com/rollup/rollup as the bundler. However the gain is not very large because jsts internally has very far reaching dependencies so it will end up including a large part of the library anyway with only a small variation depending on what operations are actually included.

[codeofsumit]

Just want to +1 on this. I just spent quite some time to figure out why my very small leaflet plugin became so big and when checking all modules that were included in the build, jsts came up.
Definitely a welcome change to move away from it - this is way too big.

[sheerun]

I've sent PR that mostly implements buffer without JSTS: https://github.com/rowanwins/geojson-buffer/pull/4 Hope it helps migrating out of it