turf

turf copied to clipboard

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

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

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.

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

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.

Wow, jsClipper is some insane code

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

:+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.

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

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.

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

@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

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?

Any news?

@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

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?

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

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.

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

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;
};

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.

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

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?

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

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)

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

@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

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 :)

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.

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.