Geometry buffering

[urschrei]

Overview

The ability to buffer geometries is fundamental to a high-quality geometry library. Thus far, we lack that ability. This is a kind of tracking issue for the implementation of this functionality in geo. This is the most simple explanation I could find.

The more technical term for this functionality is inward or outward polygon offsetting, though for the purposes of this issue we include 1D geometries such as Point and LineString as entities that we wish to buffer.

Background

This page provides a good overview of the problem, and some strategies for implementing the functionality, as well as references in the literature. In particular, the ability to quickly and robustly compute a straight skeleton is the fundamental first step to producing offset curves, and many straight-skeleton algorithms require a fast, robust sweep-line algorithm. This paper by Chen and McMains (2005) provides a more in-depth overview of existing methodologies before presenting a new (in 2005) approach to computing raw offset curves.

This more recent paper by Palfrader and Held (2015) presents a Voronoi-based straight skeleton approach to computing offsets.

The even more recent post provides an up-to-date overview of the relationship between the straight skeleton and the offset curve.

Implementations

CGAL

As ever, CGAL is a useful source of data on how one might approach the design of the API. Here's the overview of the CGAL approach.

Note that the half-edge data structure described above is more usually known as a Doubly-connected edge list (DCEL), and that the Spade library includes a robust (though non-public?) implementation of this (see the tests for an example of its API).

JTS

???

GEOS

???

Clipper

Angus Johnson's Clipper library (Clipper 2, in beta):

https://sourceforge.net/p/polyclipping/code/HEAD/tree/sandbox/Clipper2/cpp/

Mapnik's Clipper implementation

https://github.com/mapnik/angus-clipper, which is based on the Chen and McMains paper used in Angus Johnson's Clipper library. Note that this example is very much a kitchen-sink approach and includes a lot of functionality already present in geo.

JS Clipper

Based on Angus Johnson's Clipper library: https://github.com/junmer/clipper-lib/blob/master/clipper.js. Note that offsetting is only a component of this library.

[urschrei]

This is an interesting comment: https://github.com/anvaka/isect#bush-algorithm, especially considering that we have a spatial index library at our disposal, and this should work to locate overlapping bounding boxes. @michaelkirk this might also work as a replacement for your brute-force intersection-check?

[michaelkirk]

Sorry, I'm just now finally spending a little time reading some of these resources @urschrei. Thank you for gathering them!

In taking a look at GEOS, it appears to be (unsurprisingly) a straight port of JTS.

I dug through the JTS code for a bit, but not long enough to offer a concise description of the overall algorithm.

It relies on a topology graph - for which we could likely re-use (some) of our existing implementation, plus an Overlay operation. We don't currently have something like this in the geo crate - so we'd either need to implement something, or rely on something like geo-booleanop to do it for us, provided its sufficiently robust.

points of interest

Entry point: https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/operation/buffer/BufferBuilder.java

Driven largely by:
https://github.com/locationtech/jts/blob/462d6c288162920bd128e6fe75f3ece0db4d00ff/modules/core/src/main/java/org/locationtech/jts/operation/buffer/OffsetCurveSetBuilder.java#L50

/** 
* Creates all the raw offset curves for a buffer of a {@link Geometry}. 
* Raw curves need to be noded together and polygonized to form the final buffer area. 
*/
public class OffsetCurveSetBuilder

Which is in turn largely driven by

https://github.com/locationtech/jts/blob/462d6c288162920bd128e6fe75f3ece0db4d00ff/modules/core/src/main/java/org/locationtech/jts/operation/buffer/OffsetCurveBuilder.java#L32

 /**
 * Computes the raw offset curve for a
 * single {@link Geometry} component (ring, line or point).
 * A raw offset curve line is not noded -
 * it may contain self-intersections (and usually will).
 * The final buffer polygon is computed by forming a topological graph
 * of all the noded raw curves and tracing outside contours.
 * The points in the raw curve are rounded 
 * to a given {@link PrecisionModel}.
 * /
public class OffsetCurveBuilder

[michaelkirk]

This is an interesting comment: https://github.com/anvaka/isect#bush-algorithm

Indeed it is interesting!

I don't know that those benchmarks are authoritative, but that tldr seems to be:

• BO is good when intersections are sparse
• naive approach is good when intersections are dense
• r-tree backed approach offers balanced performance for both cases, which makes it a compelling choice for a default implementation (doubly so, since, as you point out we already have one at our disposal!)

I'll make an issue to track that task... here: #649

[Nevsden]

Using the available geo-clipper library, which wraps the AngusJ clipping algorithm, we could add the functionality with very little overhead and almost no work on the algorithm for geometry buffering itself.
The AngusJ clipping library is very stable as it internally converts to integer precision. Also all the edge cases arriving are well-documented. In my field of work we are using the library for a CAM-software application for several years now.

I would suggest to add the functionality using the geo-clipper library as a version 1.0. We could implement our own algorithm ourselves as a version 2.0 in the future. In the meantime the feature is stable, available and relatively fast.

I can make a sketch and send a PR.

[michaelkirk]

I would suggest to add the functionality using the geo-clipper library as a version 1.0. We could implement our own algorithm ourselves as a version 2.0 in the future.

So as not to duplicate discussion, I think the same critiques of geo-clipper mentioned after #620 (comment) apply

[Nevsden]

Using the available geo-clipper library, which wraps the AngusJ clipping algorithm, we could add the functionality with very little overhead and almost no work on the algorithm for geometry buffering itself. The AngusJ clipping library is very stable as it internally converts to integer precision. Also all the edge cases arriving are well-documented. In my field of work we are using the library for a CAM-software application for several years now.

I would suggest to add the functionality using the geo-clipper library as a version 1.0. We could implement our own algorithm ourselves as a version 2.0 in the future. In the meantime the feature is stable, available and relatively fast.

I can make a sketch and send a PR.

Currently I'm too occupied with work so that I could not yet present a sketch on this matter.

[michaelkirk]

@Nevsden - as I mentioned, see the conversation in #620. We won't merge a c/c++ dependency into this repository.

[thehappycheese]

Hi there :) Is anyone actively working on this? I am revisiting an old project nicklinref_rust and its dependancy nicks_line_tools_rust which did not use the geo library. At the time I was learning rust so I opted to roll my own linestring types and basic offset algorithm so I could more easily port my python offset algorithm (https://github.com/thehappycheese/nicks_line_tools) which followed Xu-Zheng Liu, Jun-Hai Yong, Guo-Qin Zheng, Jia-Guang Sun. An offset algorithm for polyline curves. Computers in Industry, Elsevier, 2007, 15p. inria-00518005

Now I am considering revisiting the challenge with geo-types. I don't think I am capable of porting C++ code, but perhaps I am able to follow those voronoi papers linked a the top of this page. I might be a bit out of my depth when it comes to super robust methods but i'd love to contribute something if I manage it.

[dabreegster]

I am revisiting an old project nicklinref_rust and its dependancy nicks_line_tools_rust which did not use the geo library.

I don't know anyone actively working on this, but I just wanted to mention I might be interested in using your initial Rust crates. I have my own ad-hoc code for offsetting linestrings and doing other operations, and it doesn't use geo internally. The code is here and a description here. The implementation has many problems, and I really want to switch to something more robust. I've been keeping an eye on https://github.com/jbuckmccready/cavalier_contours, but from a first attempt to use it, the API has been hard to understand.

What's the license on your Rust experiments? If I initially hook things up and get good results, I'd be happy to spend a little of my time helping to clean up your crate, if needed.

[thehappycheese]

Hi @dabreegster thanks for the response and the links to your code :)

You are welcome to my code and I am open to pull requests... though don't trouble yourself too much, I may be slow to respond anyway. I am starting fresh with a rust-powered python library megalinref.

I have slapped an MIT licence on those for you, hope it works for you. I really only needed a super fast non-robust output at the time, so I didn't implement all the bells and whistles. I went a bit further on my python version which may be helpful... I think I did a decent-ish job of transcribing the paper into pseudo-code in the readme.

cavalier_contours looks great. I wonder if it only works for polygons though... I need something for LineStrings, I will look into it :)

[H-Plus-Time]

What's the general mood of maintainers vis Geodesic vs Euclidean buffering/offset curves? Should these be separate traits (similar to GeodesicDistance vs EuclideanDistance)?

There's also the matter of incremental support - would it be worthwhile defining the bare-minimum form of the Buffer (or GeodesicBuffer) trait, with the necessary parameters to cover the Point/MultiPoint type?

As far as I can tell, the implementation of Buffer (OffsetCurve is undefined for points) would always involve a strict subset of parameters introduced by any of the competing higher-dimensional implementations, and would effectively share no code in common.

[urschrei]

Should these be separate traits (similar to GeodesicDistance vs EuclideanDistance)?

Yes, definitely.

There's also the matter of incremental support - would it be worthwhile defining the bare-minimum form of the Buffer (or GeodesicBuffer) trait, with the necessary parameters to cover the Point/MultiPoint type?

I think so. But note that the planar buffer is the priority, and there'll be a certain amount of bikeshedding about the trait as a whole because we're introducing a new public API, even if it only applies to a single geometry.

As far as I can tell, the implementation of Buffer (OffsetCurve is undefined for points) would always involve a strict subset of parameters introduced by any of the competing higher-dimensional implementations, and would effectively share no code in common.

I'm not sure what you mean by this. Could you clarify?

[ILmoshe]

I found buffer functionality really necessary, and I couldn't find any library which provides buffers for points. The Crate geo_buffer doesn't actually implement a buffer for points (correct me if I am wrong). I am dropping here a simple straightforward implementation of buffer for points, and I hope one day we will see a buffer for every type of geometry, here in geo Crate.

use geo::{Point, Polygon, LineString};
use geo::algorithm::haversine_destination::HaversineDestination;

pub fn create_buffer(point: Point<f64>, radius: f64, resolution: usize) -> Polygon<f64> {
    let mut coordinates = Vec::with_capacity(resolution + 1);
    
    for i in 0..=resolution {
        let angle = i as f64 * 360.0 / resolution as f64;
        let dest = point.haversine_destination(angle, radius);
        coordinates.push((dest.x(), dest.y()));
    }

    let line_string = LineString::from(coordinates);
    Polygon::new(line_string, vec![])
}

fn main() {
    let point = Point::new(-73.9857, 40.7484);
    let radius = 1000.0; // in meters
    let resolution = 36; // 36 points around the circle

    let buffer = create_buffer(point, radius, resolution);
    println!("Buffer Polygon: {:?}", buffer);
}