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

Subject: Re: [geometry] warnings with gcc
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-01-19 15:39:10

>
> No holes doesn't really help, but the other property does.  I'm pretty
> sure that in that specific case the straight-skeleton is equivalent to the
> voronoi skeleton.  There is a voronoi diagram implementation done as the
> result of GSOC2010 checked into Boost.Polygon sandbox (under gtl directory
> in sandbox.)

 Voronoi skeleton (also known as medial axis) and straight-skeleton are
equal only for convex polygons. However topologically voronoi skeleton will
be very similar to straight skeleton for not convex polygons. I made
voronoi skeleton (attached to this email) for example from the wikipedia (
http://en.wikipedia.org/wiki/Straight_skeleton). As you might see the two
main differences are:
1) Voronoi skeleton may include parabolic arcs; 2) voronoi skeleton doesn't
contain edges going from angles that are more than 180 degrees.

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.

As far as I remember O(n^2) algorithm is not hard to implement. While it
still requires some robustness specific implementaiton checks.

Regards,
Andrii

On Thu, Jan 19, 2012 at 7:37 PM, Simonson, Lucanus J <
lucanus.j.simonson_at_[hidden]> wrote:

> >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
>
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>