Turf-buffer

Implementing a geodesic buffering algerithm in NodeJS

Buffering a point, line or polygon is a very common task in geometric and geographic work-flows. It means delineating the collection of points that is within a certain distance of a given object. It can be used, for example, in a geometric context to draw halo’s around objects or, in a geographic context, to compute the number of houses within a certain distance to a river.

The algorithm to efficiently compute a buffer in a plane (a two dimensional euclidean space) is well studied in computational geometry and is implemented in all popular spatial libraries. In the geographic context, however, distances are drawn on the curved surface of the earth, where a different metric holds, and the computation is much less straight-forward. In the simple case of buffering a point (which yields a circle), drawing a circle around a point on the earth’s curved surface will, in general, not give the same result as geometrically buffering that circle on a flat map projecting and reverse-projecting the result to the sphere. — One special case where this does correspond is when using a conformal projection and small buffer distances. For large distance, the collection of points at a certain distance from a centerpoint on the earth’s sphere will start to look like a disformed circle. So, geographic buffers are challenging.

TurfJS is a popular JavaScript Library that was created for geospatial analysis in the context of webmaps; e.g. geojson data loaded into a Mapbox JS map. It’s modular, user-friendly and compact, and has navtive implementations for many common geospatial algorithms. It has included a buffer function for a long time, but only as a wrapper around the buffer function from the popular and well established geometrict library JSTS - the JavaScript Topology Suite. This approach computed the geometric buffer of the geojson data in the plane of the WGS84 map projection, in which the data’s coordinates are stored. This projection not being conformal, the result doesn’t look like what you would expect: point buffers are circles in the WGS84 projection, but are rendered as ellipses in the Mercator projection common to webmaps. For a JS decent geographic library like Turf JS, this was unacceptable. Also, the dependence of TurfJS on an extensive external library like JSTS was not in line with its aim.

I came across this issue in the spring of 2016, and for someone like me with a cartographic background and a love for geometry this felt like a triggering challenge, so I decided to spend two full weeks trying to give this a shot. It was quite a quest, with detours to the CGAL documentation and Simple Feature land. I dove into the sea of buffer ellipses, took on the winding number snake and sword-fought with edge-intersections. I wrote two small helper-libraries - one to break self-intersecting GeoJSON polygons down in their constituent non-self-intersecting parts (simplepolygon), and one to compute all self-intersections in a GeoJSON polygon (geojson-polygon-self-intersections). The final algorithm creates offset buffer polygons by making arcs around every vertex of a line, polygon, … and use the Turf-destination package to ensure geodesicness. It then passes the offset polygon to simplepolygon, and filters out the constituent non-self-intersecting parts with the correct winding numbers and unions and subtracts those in the correct way. The result is a geodesic buffer!

My pull was considered by the community and I got some interesting feedback. It did not (yet) make it into TurfJS. More optimising of speed and testing on robustness would have been required - but that was beyond my capabilities. Last time I checked (January 2019) TurfJS is still, pragmatically, using JSTS to perform buffering operations in Turf. The current implementation does, however, take the far more correct approach of computing buffers on the flat surface of the pseudo-Mercator map projection - the same as that in which the data is drawn, which means small point buffers look like circles!

Overall, I learned a lot from this small undertaking: how to start coding in a language you don’t know, how to survive alone in deep algorithmic weeds, what it’s like to contribute on GitHub and what I like (and what not) about focusing very intensely on coding for a while.

— @ Home, 2016