CGAL users discussion list

[Andreas Fabri <>]

James Le Cuirot wrote:
> On Tue, 17 Nov 2009 10:33:54 +0100, "Andreas Fabri"
> <>
>  said:
> > James Le Cuirot wrote:
> > > Hello,
> > >
> > > Before I start, please excuse my lack of mathematical knowledge in this
> > > area. I need to create a Delaunay graph to generate a Vonoroi diagram from.
> > > The examples are very helpful but I need to add one extra constraint. The
> > > graph will be built from geographical points across the UK but I don't want
> > > edges to cross over the water, at least not by a large amount. If I have an
> > > outline of the UK as a polygon, can I somehow use this to constrain the
> > > resulting graph? I know about the constrained triangulations mentioned in
> > > the manual but I don't think they will work. Any help would be much
> > > appreciated. :)
> > >
> > > Cheers,
> > > James
> > Hello James,
> >
> > You mean you want to clip Voronoi cells at borders ?
> >
> > andreas
>
> I understand that Voronoi cells extend to infinity around the outside so
> yes but not only that. Where parts of the UK are concave (e.g. between
> Wales and South-West England), the cells will cross over the water here
> too. Now you mention the word "clip" though, I guess I could just clip
> the resulting Voronoi afterwards? I think I was thinking about this too
> hard. :)

Clipping is not the only thing you need here. When  you have a point in
South-West England then you don't want it to have any Voronoi cell in
Wales.  There is a prototype floating around that does what you want to do,
but I am not sure that it has an API stable enough to be distributed.

andreas