0
$\begingroup$

Computing an axis aligned bounding box of a point set is trivial. Computing a bounding sphere of a point set is also trivial when the center is known. Computing the center of the bounding sphere is not-so-trivial, as far as I see. So my plan is to approximate the center of the bounding sphere by the center of the bounding box.

Are there any situations where this approach will lead to silly results?

$\endgroup$
2
$\begingroup$

The book "Real-Time Collision Detection" suggests that the AABB centroid is a decent approximation to the bounding sphere. In fact, the AABB centroid is much more accurate than the center of mass of the points, in general.

A quick survey of the techniques mentioned in the book (Chapter 4):

  • Centroid of AABB: quick and dirty, not terrible
  • Center of data in direction of maximum variance (eigenvalue/eigenvector of covariance matrix) --> This method seems like it could generalize to find a good bounding ellipsoid of your data, potentially better for high aspect-ratio point sets
  • Randomized O(N) algorithm (Welzl's algorithm) which maintains a set of points which must lie on the minimum sphere boundary. An implementation is available in CGAL.

The book is written toward video game programmers, so there is an emphasis on being "good enough" quickly rather than necessarily correct. A typical use-case for these bounding volumes in this context is for collision detection. Since the goal is to minimize the overall time to do the collision detection, having exact bounding volumes that are potentially expensive to compute is counter-productive, hence the emphasis on approximate methods.

Here's an official link to the book, but there are other "less official" links floating around the internet as well...

http://www.sciencedirect.com/science/book/9781558607323

$\endgroup$
2
$\begingroup$

I am almost certain that a literature review will find an algorithm that is exact. But I would also suggest to start with the center of mass of the convex hull -- which is easy to compute.

$\endgroup$
1
$\begingroup$

Off-hand, I think the more skewed your point distribution, the worse this approximation would be. Example, say in 2D you have a point at $[x,y]=(0,0)$, and points along the vertical line $(1,-1) \rightarrow (1,1)$, the bounding box would be $(0,-1)\times(1,1)$ with a centroid at $(0.5,0)$, but the centroid of the bounding circle would be at $(1,0)$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.