Geometry Boost List: Re: [geometry] warnings with gcc

Subject: Re: [geometry] warnings with gcc
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2012-01-19 12:51:00

Simonson, Lucanus J wrote:
> Forgot to mention, straight-skeleton is the basis for the "correct"
> polygon sizing algorithm.  In trying to implement polygon sizing in
> Polygon I found that offsetting is easy, but sizing is quite another
> story.  My current sizing algorithm is not "correct" because it is
> prone to artifacts that can only be solved in the general case by
> applying the straight-skeleton based "correct" algorithm (I tried to
> find a way around it and ended up proving that its impossible).

I would be interested in this proof. If I remember correctly, there is one type of acute corner (depending on whether shrinking or bloating is done) that couldn't be handled using only "local" information. I also believe that even the published straight-skeleton algorithms are not O(n log(n)) if the number of these "bad" corners is not O(1).

Regards,
Thomas