From: "Dave Eberly" Subject: Re: Algorithm to find minimal circle which covers an irregular polygon Date: Wed, 31 Mar 1999 22:14:43 -0500 Newsgroups: alt.math,comp.graphics.algorithms,fido7.algorithms,sci.math Keywords: minimum bounding circle Ruud van der Ham wrote in message <01be7b55$10dd2e80$2921010a@pc3970>... >For a research project, I need to find the minimal circle which just covers >a polygon. The polygon is expressed as a number of points and is not >regular. This is equivalent to finding the minimum area circle containing the vertices of the polygon. Source code for this is at my web site, link Computer Graphics | Containment. The files mincirc.{h,cpp} use a randomized linear algorithm by Welzl. The files mincirci.{h,cpp} solve the same problem with a numerical minimizer (iterative scheme). -- Dave Eberly eberly@magic-software.com http://www.magic-software.com ============================================================================== From: "Dann Corbit" Subject: Re: Finding the smallest circle including N points. Date: Thu, 19 Aug 1999 22:25:16 -0700 Newsgroups: sci.math.num-analysis From the news:comp.graphics.algorithms FAQ: Subject 1.05: How can the smallest circle enclosing a set of points be found? This circle is often called the minimum spanning circle. It can be computed in O(n log n) time for n points. The center lies on the furthest-point Voronoi diagram. Computing the diagram constrains the search for the center. Constructing the diagram can be accomplished by a 3D convex hull algorithm; for that connection, see, e.g., [O'Rourke (C), p.195ff]. For direct algorithms, see: S. Skyum, "A simple algorithm for computing the smallest enclosing circle" Inform. Process. Lett. 37 (1991) 121--125. J. Rokne, "An Easy Bounding Circle" [Gems II] pp.14--16. -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm ============================================================================== From: zeisel@vai.co.at (Zeisel Helmut) Subject: Re: Finding the smallest circle including N points. Date: 19 Aug 1999 15:19:42 +0100 Newsgroups: sci.math.num-analysis In article <7pglkf$es$1@news.kren.nm.kr>, "Jinwook Kim" writes: >Question is as follow : > >1. Given N points in plane, how to find the smallest circle including all >given points? > Franco P. Preparata, Michal Ian Shamos: Coputational Geometry Springer Verlag Chapter 6.4: Gaps and Covers Helmut -- ============================================================================== From: Thomas Jespersen Subject: Re: Algorithm to find minimal circle which covers an irregular polygon Date: 31 Mar 1999 14:47:58 +0200 Newsgroups: alt.math,comp.graphics.algorithms,fido7.algorithms,sci.math "Ruud van der Ham" writes: > For a research project, I need to find the minimal circle which just covers > a polygon. The polygon is expressed as a number of points and is not > regular. > I think this problem is also addressed as an 'inscribed polygon'. > Response via email (Ruud.van.der.Ham@ect.nl) is highly appreciated. Fitting a circle to a set of points: http://www.numerik.uni-kiel.de/faqs/tda/q230.8.html