Smallest circle covering set of points
in [General Programming]
|
Prev: Heathfield: You're wrong: here's proof: (WAS: Re: Welcome To The Word Wide Mirror Sci.Math)
Next: SETP-10 Call for papers
From: Andrew Tomazos on 14 Nov 2009 23:29 Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a good algorithm for determining the centerpoint and radius of the smallest circle that will cover all the points? Thanks, Andrew.
From: Andrew Tomazos on 14 Nov 2009 23:54 On Nov 15, 5:29 am, Andrew Tomazos <and...(a)tomazos.com> wrote: > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a > good algorithm for determining the centerpoint and radius of the > smallest circle that will cover all the points? Thanks, Andrew. (some thoughts) If the centerpoint is (x,y), than the distance to each point k is given by sqrt((x-ak)^2 + (y-bk) ^2) so we want to select (x,y) such as to minimize the largest element of the set: { (x-a1)^2 + (y-b1)^2 , (x-a2)^2 + (y-b1)^2 , ... , (x-an)^2 + (y-bn)^2 } But how to do that? -Andrew.
From: Andrew Tomazos on 14 Nov 2009 23:57 On Nov 15, 5:54 am, Andrew Tomazos <and...(a)tomazos.com> wrote: > (x-a2)^2 + (y-b1)^2 , typo (x-a2)^2 + (y-b2)^2 ,
From: Dave Eberly on 15 Nov 2009 00:31 "Andrew Tomazos" <andrew(a)tomazos.com> wrote in message news:6bc4f385-4b1d-4c1e-b558-37479c4dad9f(a)k17g2000yqh.googlegroups.com... > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a > good algorithm for determining the centerpoint and radius of the > smallest circle that will cover all the points? Thanks, Andrew. The algorithm is called Welzl's algorithm (see the Miniball reference posted by zwim). I also have an implementation, http://www.geometrictools.com/LibFoundation/Containment/Containment.html files Wm4ContCircle2.{h,cpp} -- Dave Eberly http://www.geometrictools.com
From: Chip Eastham on 15 Nov 2009 08:43
On Nov 14, 11:54 pm, Andrew Tomazos <and...(a)tomazos.com> wrote: > On Nov 15, 5:29 am, Andrew Tomazos <and...(a)tomazos.com> wrote: > > > Given a set of points (a1,b1) (a2,b2)..(an,bn) in the plane - what's a > > good algorithm for determining the centerpoint and radius of the > > smallest circle that will cover all the points? Thanks, Andrew. > > (some thoughts) > > If the centerpoint is (x,y), > > than the distance to each point k is given by sqrt((x-ak)^2 + (y-bk) > ^2) > > so we want to select (x,y) such as to minimize the largest element of > the set: > > { (x-a1)^2 + (y-b1)^2 , > (x-a2)^2 + (y-b1)^2 , > ... , > (x-an)^2 + (y-bn)^2 > } > > But how to do that? > -Andrew. The short answer is to check out Dave Eberly's implementation linked below in the thread! From what I remember there is a "naive" strategy that involves pivoting. First find the pair of points farthest apart; the circle must have at least this diameter. If that diameter (between two points farthest apart) yields a containing circle, we're done. If not, the minimum circle will have (at least) three points on its circumference. Pick a point outside the given "two point" circle, and see if the circle one that and the first two points contains all the points. If so, done. Then you have a sequence of three-point circles to consider until you find one that contains all the points. Here's where "pivoting" comes into the picture. We have three points A,B,C that determine my current circle, and a point D not contained by the circle. Which point A,B,C is to be replaced by D? A simple way to answer this is by trying all three and comparing which has the smallest radius yet still contains the replaced point. IIRC a slightly more efficient check is based on the angles of the resulting triangle. The inscribed triangle (of three points on the circle) must be acute, else the circle's radius isn't minimal (having already ruled out the two-point circle using two farthest apart). The right choice for D to replace is that point which results in the triangle with the minimal maximum angle (whose largest angle is the smallest among 3 possibilities). Since the largest angle opposes the longest side, this check can be done via the cosine formula for triangles. regards, chip |