Newsgroups: comp.graphics Path: utzoo!utgpu!jarvis.csri.toronto.edu!dgp.toronto.edu!juancho From: juancho@dgp.toronto.edu (John Buchanan) Subject: Re: Algorithm wanted: Circle enclosing points Message-ID: <8804041445.AA12683@explorer.dgp.toronto.edu> Organization: University of Toronto, CSRI References: <496@etn-rad.UUCP> Date: Mon, 4 Apr 88 08:45:38 EDT In article <496@etn-rad.UUCP> jru@etn-rad.UUCP (John Unekis) writes: >In article 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, > ... > Try finding the maximum and minimum x coordinates, then average to get the > center x. Do the same for y coordinates to get the center for y. Then look > at the distances to those four points {sqrt((x1-x2)2 +(y1-y2)2)} from the > center x,y and take the largest distance as the radius. This will give you a circle that encloses the points but I think that a tighter circle can be found by looking at the furthest point which lies near the eigenvector that corresponds to the largest valued eigenvalue of the data. Right now I can not remember how to construct the matrix that is required to find the appropriate eigen[values|vectors]. Any good book on pattern recognition will have this.