polygonal labs » Bounding circle computation

Bounding circle computation

February 17, 2007 on 11:08 pm | In Actionscript | No Comments

Computing the smallest bounding circle from a set of points is a tricky task and it’s not as straightforward as creating a bounding box. Admittedly I can’t think of many applications for it – maybe you could use it for collision culling of soft-bodies, where you mostly get a tighter bounding representation than with a box. Now to the algorithms:

A rough, but very fast approximation. It basically just computes the minima/maxima points (like for a bounding box) and takes the average of all points to compute the circles center (red circle).
A near-optimal bounding circle [1], which produces a closer bounding circle than the first one, but also with twice the cost (green circle).
An exact bounding circle [2]. This is the slowest of the three (roughly 20x slower), but results in a perfect bounding circle. Ideal for precomputing static geometry (blue circle).

(press space for random data)

Download

All three algorithms are implemented in AS3. Grab them here.

Usage

Usage is very simple. Just create an array of flash.geom.Point instances and pass them to the bounding circle function to retrieve a circle instance.

import flash.geom.Point;

var points:Array = [new Point(5, 5), new Point(23, -7),...];
var circle:Circle = BoundingCircle.boundingCircle1(points);

trace("position=" + [circle.x, circle.y] + ", radius=" + circle.radius);