CGAL users discussion list

["naresh" <>]

Dear Monique


Thanx for the suggestion i will try to do that.

----- Original Message ----- 
From: "Monique Teillaud" <>
To: 
<>
Sent: Wednesday, August 25, 2010 6:10 PM
Subject: Re: [cgal-discuss] Largest Empty Circle with Voronoi


> Hi Naresh
>
> You can compute this easily with CGAL:
>
> First, compute the Delaunay triangulation of the points.
>
> Then, iterate on all the finite faces of the triangulation.
> For each finite face f
> - compute its circumcenter c
> - locate c in the triangulation (to speed up things, you can give one 
> vertex of f as starting hint for the point location)
> if the face returned by locate(c,hint) is finite, then the circumcenter c 
> lies in the convex hull of the points, so, f is a candidate
> - if f is such a candidate face, compute its squared circumradius
> keep only the face with minimum squared circumradius
>
> The CGAL manual (chapter 2D triangulation, together with a few things from 
> the kernel) shows every basic function to do this.
>
> Best regards,
> Monique Teillaud
>
> naresh wrote:
> > Dear Sebastien
> >
> > Actually  i am trying to find largest inscribed circle from pointset or 
> > may be counter sets in 2D.  in wikipedia and google i read voronoi 
> > diagram can my solve problem using largest empty circle very easily but 
> > not got any implmentation or any good papers.
> >
> >
> > Any idea how to do with CGAL ?
> >
> >
> > thanx in advance.
> >
> > Naresh
> >
> >
> >
> > ----- Original Message ----- From: "Sebastien Loriot (GeometryFactory)" 
> > <>
> > To: 
> > <>
> > Sent: Wednesday, August 25, 2010 5:14 PM
> > Subject: Re: [cgal-discuss] Largest Empty Circle with Voronoi
> >
> >
> > > naresh wrote:
> > > > Hi
> > > >
> > > > How can i find Larget Empty Circle with centered withthin their convex 
> > > > hull ?
> > > Are you looking for the functions circumcenter and squared_radius?
> > >
> > > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Kernel_23_ref/Function_circumcenter.html#Cross_link_anchor_398
> > > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Kernel_23_ref/Function_squared_radius.html#Cross_link_anchor_459
> > >
> > > S.
> > > > I checked the code but nothing found. While LEDA has some 
> > > > implementation. Does CGAL have anything ?
> > > >
> > > >
> > > > Naresh
> > >
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
> --
> Monique Teillaud
> INRIA Sophia Antipolis - Méditerranée
> http://www.inria.fr/sophia/members/Monique.Teillaud/
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss