Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!pyramid!prls!philabs!micomvax!vedge!lurch
From: lurch@vedge.UUCP (Lurch)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <254@vedge.UUCP>
Date: 14 Apr 88 18:25:17 GMT
References: <496@etn-rad.UUCP> <494@eos.UUCP>
Organization: Visual Edge Software, St. Laurent, Quebec
Lines: 21
Summary: Improvement on algorithm (maybe)

> In article <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> mp1u+@andrew.cmu.edu (Michael Portuesi) writes:
> >I am looking for an efficient algorithm that, given a set of points, finds the
> >smallest circle enclosing them and its center.  Pseudocode, actual code (C,
> 
In article <494@eos.UUCP>, jbm@eos.UUCP (Jeffrey Mulligan) responds:
> 1)  Make a list of all triples of points (there are N choose 3 of them).
> 2)  Treating each triple of points as the vertices of a triangle,
> 	compute the radius of the circumscribing circle.
> 3)  The largest circumcircle is the desired result.


Seems to me that rather than use the set of all possible triplets,
just using the points from the convex hull would speed this up 
greatly. Obviously, the three points Jeff M. refers to must lie
on the hull. 

-- 
| "I gave you seven children woman...Now you want to give 'em back!" -BB King |
+-----------------------------------------------------------------------------+
|  Jeff Smith  Visual Edge Software, Montreal, Quebec                         |
|               ....sun!decwrl!decvax!watmath!onfcanim!vedge!lurch            |