
Geometry : 
Subject: Re: [geometry] Algorithm used in boost::geometry::buffer
From: Barend Gehrels (barend_at_[hidden])
Date: 20180905 20:15:47
Hi Santanu,
>
>
> >
> > I'm trying to understand the algorithm underlying the buffer API
> in Boost.Geometry. The toplevel headers don't seem to have any
> citations (apologies if I've missed it still).
> >
> > I've the following queries:
> > 1) What is the worstcase complexity of the buffer algorithm for
> a poly line / polygon? I would imagine it depends on the
> convex/reflex vertices in the input, so feel free to state the
> complexity in those terms.
>
I can't tell the complexity (yet) in detail. It does not only depend on
the input, it also depends on the number of vertices (in corners) you
specify, and how many corners there are, so it depends mostly on the
number of vertices in the output.
> >
> > 2) What is the overall strategy used for getting the offset
> curve? Is it a variant of the pairwise offset strategy mentioned
> in "A pairwise offset algorithm for 2D pointsequence curve B.K.
> Choi*, S.C. Park (CAD 99), or something else ? I would really
> appreciate some pointers in this regard?
> >
>
It is not a variant of the source you mention. The buffer generation is
coupled to all set operations (union, intersection and difference).
Which use a variant of the graph traversal algorithm. There are a few
steps before, to generate polygons (here called pieces) adjacent to
input lines and corners. From those pieces intersection points are
calculated (roughly a n log n operation) to calculate selfintersections
(per polygon, for concavities or deflated buffers  and amongst polygons
within a multiline or multipolygon). Calculating intersection points
is the most time consuming step, a spatial partitioning algorithm is
used to make this logarithmic. After that intersection points are
traversed and final output is generated.
The generic intersection algorithm is roughly based on Greiner / Hormann
and Weiler / Atherton
https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm
https://en.wikipedia.org/wiki/Weiler%E2%80%93Atherton_clipping_algorithm
Hope this helps,
Regards, Barend
Geometry list run by mateusz at loskot.net