CGAL users discussion list

["James Le Cuirot" <>]

On Tue, 17 Nov 2009 10:55:09 +0100, "Andreas Fabri"
<>
 said:
> 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

There should be enough points to cover the entire country so I don't
think that will be a problem? There will be cells on both sides and
that's fine as long as they don't join over the water. Thanks for your
help, btw.

James