Geometry Boost List: [ggl] Voronoi diagram code?

Subject: [ggl] Voronoi diagram code?
From: Andrii Sydorchuk (sydorchuk.andriy)
Date: 2011-09-05 06:20:28

In our implementation we also use floating-point arithmetic with computed
relative error as the first step. After that we check if the result could be
undefined (having it's value and relative error). If the result is defined
we output it, else evaluate predicate using exact arithmetic. We call this
approach lazy arithmetic. It involves implementation of some special data
structures to handle relative errors. This approach is also used to compute
coordinates of the voronoi vertices.

Thanks for the article, I'll have a look.

Andrii

On Mon, Sep 5, 2011 at 8:11 AM, Anders Wallin
<anders.e.e.wallin_at_[hidden]>wrote:

> There is a recent conference paper by Held et al where floating-point
> algorithms are compared to exact arithmetic/predicates, which you may
> find interesting:
> http://2011.cccg.ca/PDFschedule/papers/paper77.pdf
>
> It's quite clear how to interpret the runtime results (exact
> arithmetic slows down the vroni algorithm by a factor of 50-70).
> However it's less clear to me how to interpret the accuracy data.
>
> If anyone builds a set of test-cases and makes these publicly
> available it would be interesting to redo these benchmarks. My code is
> similar to vroni, but handles only point-generators at the moment.
>
> Anders
>
> > 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.
> _______________________________________________
> 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/20110905/ee0d6537/attachment.html