Geometry Boost List: [ggl] Voronoi diagram code?

Subject: [ggl] Voronoi diagram code?
From: Andrii Sydorchuk (sydorchuk.andriy)
Date: 2011-09-03 20:31:30

Hi Anders,

As mentioned Mateusz it's a part of the Boost.Polygon library (not included
in the release yet). All the implementation details are done, however it
requires some code refactoring and documentation to suit Boost libraries
release requirements. At the moment the code is under
https://svn.boost.org/svn/boost/sandbox/SOC/2010/sweepline

There are three approaches used to build Voronoi diagram of points and line
segments: sweepline algorithm, divide and conquer and incremental
algorithms. We used sweepline algorithm because it doesn't have voronoi
diagram reconstruction step, thus it has simpler and clearer site processing
logic (especially for the voronoi of segments).

If this would help you, the incremental algorithm is implemented in the CGAL
library.

Regards,
Andrii

On Sat, Sep 3, 2011 at 8:23 PM, Anders Wallin
<anders.e.e.wallin_at_[hidden]>wrote:

> Hi all,
>
> What is the status of the voronoi diagram code described here:
>
> http://blip.tv/boostcon/sweep-line-algorithm-for-voronoi-diagrams-of-points-line-segments-and-medial-axis-of-polygons-in-the-plane-5368229
>
> I've been tinkering with an alternative approach (topology-based
> incremental algortihm), which looks like this:
> http://www.youtube.com/watch?v=5Rd-u5n0pQs
>
> I want to add line-segment and arc generators to my code, and I'm
> hoping if the boost-ggl voronoi diagram code was available I could get
> some help/insight on how to write the geometric predicates and
> voronoi-vertex positioning functions. For point generators there's
> essentially one determinant calculation that gives all the answers,
> but for lines and arcs it gets (much?) more complicated!
>
> regards,
> Anders
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20110904/5436b202/attachment.html