From: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire)
Newsgroups: comp.os.msdos.djgpp
Subject: Re:  bounding circle vs. bounding boxes
Date: 1 Mar 1997 04:19:23 GMT
Organization: The National Capital FreeNet
Lines: 57
Message-ID: <5f8aob$93q@freenet-news.carleton.ca>
References: <19970226 DOT 065019 DOT 4511 DOT 1 DOT fwec AT juno DOT com>
Reply-To: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire)
NNTP-Posting-Host: freenet5.carleton.ca
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp



Get the centroid of all your points. Then get the distance to the furthest
point. This gets you the center and radius.

e.g.

typedef struct point {
  int x;
  int y;
} POINT;

void get_bounding_circle (int *,int *,int *,int,POINT *);

/* Obtain the center x, y, and the radius of the bounding circle of many
   points. Accepts the number of points and a pointer to the first in an
   array of POINT structures. Returns the results in the ints whose
   addresses you pass as the first three parameters. Easily adapted to 3d:
   add an int z; to the struct, add an int *cz to the prototype and
   function declaration, add an rz in the function and add appropriate
   lines to the two loops to deal with rz and int *cz. Then it returns the
   center and radius of a bounding sphere. */

void get_bounding_circle (int *cx, int *cy, int *radius, int num_points,
 POINT *points) {
  int i;
  int rx;
  int ry;
  rx=0;
  ry=0;
  int r;
  int r1;
  for (i=0; i<num_points; i++) {
    rx+=points[i].x;
    ry+=points[i].y;
  }
  (*cx)=rx/num_points;
  (*cy)=ry/num_points;
  r=0;
  for (i=0; i<num_points; i++) {
    rx=(*cx)-points[i].x;
    ry=(*cy)-points[i].y;
    r1=rx*rx+ry*ry;
    if (r1>r) r=r1;
  }
  (*radius)=sqrt(r1);      
}


(note: might have minor bugs, I wrote this in a newsreader that doesn't
have syntax-checking ;))

--
    .*.  Where feelings are concerned, answers are rarely simple [GeneDeWeese]
 -()  <  When I go to the theater, I always go straight to the "bag and mix"
    `*'  bulk candy section...because variety is the spice of life... [me]
Paul Derbyshire ao950 AT freenet DOT carleton DOT ca, http://chat.carleton.ca/~pderbysh