Boost logo

Geometry :

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



Geometry list run by mateusz at loskot.net