Geometry Boost List: Re: [geometry] Algorithm used in boost::geometry::buffer

Subject: Re: [geometry] Algorithm used in boost::geometry::buffer
From: Barend Gehrels (barend_at_[hidden])
Date: 2018-09-05 20:15:47

Hi Santanu,

>
>
>     >
>     > I'm trying to understand the algorithm underlying the buffer API
>     in Boost.Geometry. The top-level headers don't seem to have any
>     citations (apologies if I've missed it still).
>     >
>     > I've the following queries:
>     > 1) What is the worst-case 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 pair-wise offset strategy mentioned
>     in "A pair-wise offset algorithm for 2D point-sequence 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 self-intersections 
(per polygon, for concavities or deflated buffers - and amongst polygons 
within a multi-line or multi-polygon). 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