Geometry Boost List: [ggl] Proposal for Delauney triangulation algorithm

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: Andrii Sydorchuk (sydorchuk.andriy)
Date: 2011-10-20 13:17:02

Hi John,

I had a brief look through the c++ code of the CDT. Here are the conclusions
that I made:
1) The implementation is not robust. It uses double type for all the
computations. It uses epsilons for the comparison decisions. You should
investigate if this might corrupt algorithm internal structures states.
2) The complexity seems to be ?(N^2), that is not the best case (N*log(N) is
possible). At least advancing front doesn't implement BST (looks like doubly
linked list). It might be possible to use std::map or std::set instead of
that data structure, but I am not sure that they are suitable for the
algorithm needs. Also you might need to check complexity requirements for
all the other structures and operations.

Andrii

On Wed, Oct 19, 2011 at 2:18 PM, John Swensen <jpswensen_at_[hidden]> wrote:

>
> On Oct 19, 2011, at 8:07 AM, Bruno Lalande wrote:
>
> > Hi John,
> >
> > Ii could be interesting.
> >
> > First, have you checked that the license used by this library is
> compatible with what you want to do?
> >
> > Second, not sure you get well what implementing a Boost.Geometry
> algorithm really is about. You're talking about replacing the classes in the
> library (point, polygon) by the ones provided by Boost.Geometry. But that's
> not the point: the purpose of Boost.Geometry algorithms is to be able to
> work on any data type, as long as it meets some requirements. So basically
> your algorithm will not know/use geometries from Boost.Geometry directly,
> but its concepts. You'll have to use all the metafunctions and other
> mechanisms that allow us to manipulate our data through concepts and not
> directly. Was this your intention?
> >
> > Regards
> > Bruno
>
> I guess maybe I don't understand the architecture of Boost.Geometry very
> well.  How do you differentiate between algorithms that only work on
> polygons or only work on sets of points (using the term "algorithm" loosely
> here to describe the mathematical definition rather than the Boost.Geometry
> definition)?  Or do operations that are specific to a very specific
> instantiation of a template not belong in Boost.Geometry?
>
> I was proposing to create a class that takes a  model::polygon or
>  model::multi_polygon (regardless of the point type) and performs Delauney
> triangulation on the polygon(s) and spits out a  model::multi_polygon
> containing the resulting triangles as model::polygon's.  Does such a thing
> belong in Boost.Geometry or does it not fit the paradigm of having an
> operation work on any data type?  If it doesn't fit into Boost.Geometry,
> then I can easily just start a github project for the purpose of
> "algorithms" that operate on Boost.Geometry objects but don't meet the
> generic-ness requirements.  Either way is fine with me, but let me know.
>
> John
>
> P.S. It is BSD license and the two core maintainers think it is an awesome
> idea._______________________________________________
> 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/20111020/eb3ce59e/attachment.html