Minimum Bounding Sphere

Today I was reading this article by Ericson. The article is on the derivation involved in writing a function to calculate the minimum bounding sphere of a set of three or four points. The topic itself isn’t very interesting (to me) when compared to the algebra itself. Ericson skips the algebra I had trouble with, so my article here will serve the purpose to record the algebra he skipped (in case other readers had trouble, or I ever want to reference the math again). The article I am writing here directly follows Ericson’s article, so I will assume readers have read and understood Ericson’s article.

Say we have a set of three points S = {A, B, C}, which can be thought of as a triangle. The problem of calculating the minimum bounding sphere of S involves checking to see if the circumcenter of S lies within or outside the triangle S. Lets name the circumcenter P. One immediate implementation involves computing P, followed by the computation of the barycentric coordinates of P with respect to S. These coordinates can be used check if P lay within S.

However computing P of S followed by the barycentric coordinates of P with respect to S involves a lot of redundant computations. Furthermore, if P does not lay within S then P itself does not need to be computed at all, since only the barycentric coordinates were needed.

It would be nice to compute barycentric coordinates of P with respect to S directly, and only if necessary construct P.

P in relation to S can be defined as:

\begin{equation}
\label{eq1}
P = A + s*(B – A) + t*(C – A)
\end{equation}

Where \(s\) and \(t\) are barycentric coordinates of S such that \(s – t – (1.0 – s – t) = 0\) if P is within S. Since P is equidistant from A, B and C, we can express P in relation to S with the following:

\begin{equation}
\label{eq2}
dot(P – B, P – B) = dot(P – A, P – A)
\end{equation}

\begin{equation}
\label{eq3}
dot(P – C, P – C) = dot(P – A, P – A)
\end{equation}

The interesting part involves plugging \eqref{eq1} into \eqref{eq2} and \eqref{eq3} followed by a collection of terms. Since I myself am a noob when it comes to algebra I had to go look up algebraic properties of the dot product to make sure I did not screw anything up. In particular these few rules are useful:

\begin{equation}
\label{eq4}
dot(u, v + w) = dot(u, v) + dot(u, w) \\
dot(s * u, v) = s*dot(u, v) \\
-dot(u – v, u – w) = dot(v – u, u – w)
\end{equation}

Lets go over substituting \eqref{eq1} into \eqref{eq2} directly, however lets only consider the first part of \eqref{eq2} \(Dot(P – B, P – B)\) to keep it simple:

\begin{equation}
\label{eq5}
dot(A + s*(B – A) + t*(C – A) – B, A + s*(B – A) + t*(C – A) – B)
\end{equation}

Since things immediately get really long some substitutions help to prevent errors:

\begin{equation}
\label{eq6}
u = A – B\\
v = s*(B – A) + t*(C – A)\\
w = u + v \\
\end{equation}

\begin{equation}
\label{eq7}
Dot(w, u + v)
\end{equation}

\begin{equation}
\label{eq8}
Dot(w, u) + Dot(w, v)
\end{equation}

\begin{equation}
\label{eq9}
Dot(u + v, u) + Dot(u + v, v)
\end{equation}

\begin{equation}
\label{eq10}
Dot(u, u) + Dot(v, u) + Dot(u, v) + Dot(v, v)
\end{equation}

If I were to expand \eqref{eq10} on this webpage it would not fit. Instead we will make use of a few more substitutions and then arrive in the final form:

\begin{equation}
\label{eq11}
x = s*(B – A) \\
y = t*(C – A) \\
x + y = v
\end{equation}

\begin{equation}
\label{eq12}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) + Dot(x + y, x + y)
\end{equation}

By following the same process we can finish the substitution and notice that:

\begin{equation}
\label{eq13}
Dot(P – A, P – A) = Dot(x + y, x + y)
\end{equation}

The final form of the substitution would be:

\begin{equation}
\label{eq14}
Dot(A – B, A – B) + \\ 2*Dot(A – B, x + y) + \\ Dot(x + y, x + y) = Dot(x + y, x + y)
\end{equation}

\begin{equation}
\label{eq15}
Dot(A – B, A – B) + 2*Dot(A – B, x + y) = 0
\end{equation}

\begin{equation}
\label{eq16}
Dot(A – B, A – B) + \\ 2*Dot(A – B, s*(B – A)) + \\ 2*Dot(A – B, t*(C – A)) = 0
\end{equation}

\begin{equation}
\label{eq17}
s*Dot(B – A, B – A) + t*Dot(B – A, C – A) = \\ (1/2)*Dot(B – A, B – A)
\end{equation}

This final equation \eqref{eq17} matches exactly what Ericson came up with on his own blog. Through a similar process \eqref{eq1} can be substituted into \eqref{eq3}, which would result in:

\begin{equation}
\label{eq18}
s*Dot(C – A, B – A) + t*dot(C – A, C – A) = \\ (1/2)*dot(C – A, C – A)
\end{equation}

TwitterRedditFacebookShare

One thought on “Minimum Bounding Sphere

  1. Adam

    Or, one can find the extents, find the largest distance from opposite extents, and use half that distance as the radius.

     

    This method doesn’t require finding the center as it is self-centering, and the complexity is O(n) with n being the number of vertices. If a concrete example is needed I can post one as a followup.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *