Date: Sat, 1 Mar 1997 08:20:35 -0500
Message-Id: <199703011320.IAA23334@delorie.com>
From: DJ Delorie <dj AT delorie DOT com>
To: ao950 AT FreeNet DOT Carleton DOT CA
CC: djgpp AT delorie DOT com
In-reply-to: <5f8aob$93q@freenet-news.carleton.ca> (ao950@FreeNet.Carleton.CA)
Subject: Re: bounding circle vs. bounding boxes


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

Another step you could do afterwards to optimize the centroid (which
is just a mathematical average, where what you really want is a 2D
median).  The pseudo-code below can be used after the centroid
algorithm, or you can just start at the center of the bounding box.

loop {
  for step in ((-1,0), (1,0), (0,-1), (0,1))
  {
    new center = old center + step
    new radius = max radius (set of points, new center)
    remember if smallest radius of the four
  }

  if (smallest new radius < old radius)
    set new centroid and radius
  else
    done
}

You could optimize the first part by only stepping towards the point
that corresponded to the max radius in the previous iteration, since
you know that moving away from it will only make it worse.

As for an example of when this optimization helps, consider a sprite
that is a large circle with a line extending out one side.  the bulk
of the circle keeps the average centroid near its own center, but the
line moves the max radius way out.  The closest-fitting circle has a
center halfway between the tip of the line and the other side of the
circle.

Of course, none if this should be done on the fly.  It's best to do
them at compile time if you can (compiled sprites) or once at program
startup.