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