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