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