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

Subject: Re: [geometry] warnings with gcc
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-01-19 13:37:26

>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).

The basic idea of the proof is that if I could more quickly do resizing without needing to make use of straight skeleton type approach then I could use that to solve straight skeleton, a contradiction.  It turns out that there is nothing a about resizing (bounded property) that makes it a special case.  The problem is that if you assume angles can be arbitrarily acute then there is effectively no bound on how far they travel during the resize.  Given that there can be "ties" where vertices reach the same point at the same time and merge to form a new vertex there is no way to bound how many cascading merging of vertices could occur in the worst case.  Even if you construct the bounded motorcycle graph for reflex vertices and solve for line segment intersections the worst case bound on how many times you may need to introduce new segments due to "ties" generating new reflex vertices is O(n).  That implies worst case complexity worse than line segment intersection.

However, if we are optimistic, a resizing algorithm based on building a bounded motorcycle graph and solving with line segment intersection will have runtime similar to polygon clipping in the common case where we assume the number of extra iterations due to ties is bounded to a small constant factor.  The easy way to implement it is just re-rerun line segment intersection with the addition of new segments for ties found in the previous iteration until no ties are detected then write out the bounded straight skeleton and use it to resize the polygon.  I found this algorithm appealing because it reuses the existing line segment intersection algorithm, so could be implemented more quickly than other approaches.  Even so I judged it too much work to take on myself without being compensated for my time.  Nor is it publishable.

As far as I know the best known straight skeleton algorithm is O(n^(17/11+epsilon)) time, which is indistinguishable from O(n^2) for practical purposes, while being complicated to implement.

My preference would be to use an algorithm that has higher worst case complexity but lower expected complexity in the common case.

Regards,
Luke