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

[max-mapper]

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]

👍 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.

[max-mapper]

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.

[max-mapper]

@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]

👍 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 ☝️ ☝️, it's more the latter

[yocontra]

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 (#702, #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: rowanwins/geojson-buffer#4 Hope it helps migrating out of it

[sipris]

I use the JTS BufferOp also in a Java app and like to rely on it's battle-tested buffering implementation also in the frontend. Only the huge size of the JSTS dependency bothers me, so I thinned out the auto-port turf-jsts (see stats below) and made it work with GeoJSON directly. Now, I would like to contribute the code to the turf project.

The problem is that I can't build the customized lib inside turf-buffer, because of the strict building rules: the customized lib must be build with buble but MonorepoLint check enforces to use the rollup configuration from the root directory.

What is the best way to deal with the issue described above in order to contribute the new code?

Short stats

• previous source code required about 1.3 MB, now it only requires 230.9 kB
• all tests are green (when running them from turf-buffer)
• the performance is generally not affected by the change (partly a bit better, probably because we don't convert between JTS and GeoJSON)

You can find the current state of the code here:
https://github.com/DisyInformationssysteme/turf/tree/buffer-reduce-jsts

[JamesLMilner]

@rycgar thanks for doing that work. When you say you can't do the build you mean a separate build process that strips out the turf-jsts build? Because I was able to build turf-buffer on your branch without any issues. Ultimately I'm not sure there's a big harm in checking in your stripped down lib folder because I'd say it's actually better than depending on turf-jsts which hasn't been touched in 4 years.

I did some test builds with microbundle, esentially i just imported buffer and used it for one calculation. Here's what I found from the different JSTS library options:

Current import of buffer as it stands with turf-jsts:

Changing out turf-jsts for direct ESM imports from jsts:

@rycgar branch with the custom build:

Using @rycgar custom build brings down the final bundle size used in the test app to less than half. My recommendation would be as a minimum we just move to using jsts directly rather than turf-jsts, or potentially if people are happy with it we use @rycgar's custom build which will bring down build sizes even more and remove any external dependencies.

[sipris]

@JamesLMilner thank you for your effort. Sorry for the late response, I am kind of busy right now :)

I am able to build just the turf-buffer module, however, building the whole turf project (with the refactored turf-jsts lib) fails because of the MonorepoLint check that enforces to use the rollup configuration from the root directory. Build log from your PR:

build (14.x)

monorepolint (mrl) v0.5.0-alpha.20+fb5a530

npm WARN lifecycle The node binary used for scripts is /tmp/yarn--1624810873951-0.3124830336399751/node but npm is using /opt/hostedtoolcache/node/14.17.0/x64/bin/node itself. Use the `--scripts-prepend-node-path` option to include the path for the node binary npm was executed with.

> @ lint:escheck-js /home/runner/work/turf/turf
> es-check es5 packages/*/dist/js/index.js packages/turf/turf.min.js

ES-Check: there were 2 ES version matching errors.

          ES-Check Error:
          ----
          · erroring file: packages/turf-buffer/dist/js/index.js
          · error: SyntaxError: The keyword 'class' is reserved (77:0)
          · see the printed err.stack below for context
          ----

          SyntaxError: The keyword 'class' is reserved (77:0)
    at Parser.pp$4.raise (/home/runner/work/turf/turf/node_modules/es-check/node_modules/acorn/dist/acorn.js:2825:15)

With some hacks, it is possible to build it, but I do not want to mess with the implemented building procedure.

I hope for a solution or a hint towards the solution, how we can make it possible.

[smallsaucepan]

Looks like JSTS is still used in:

• boolean-contains
• boolean-touches
• boolean-valid
• boolean-within
• buffer

Is a) removing JSTS still a goal, and b) if yes do we want to track its removal from these last few packages in individual issues? Perhaps labelled so they stand a better chance of being picked up as people are working in those modules?