CGAL users discussion list

[Monique Teillaud <>]

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/