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