3
$\begingroup$

I have a frustum (truncated pyramid defined by six planes) and I need to compute a bounding sphere for this frustum that's as small as possible.

I can choose the centre of the sphere to be right in the centre of the frustum and the radius be the distance to one of the "far" corners (the base of the pyramid), but that usually leaves quite a lot of slack around the narrow end of the frustum. There must be a better way!

This seems like simple geometry, but I can't seem to figure it out. Any ideas?

Improve this question
$\endgroup$
5
  • $\begingroup$ That should be frustrum. Also, could you specify if the pyramid you're truncating has square base and is symmetric? If so then your problem simplifies. $\endgroup$
    – Yemon Choi
    Commented Feb 3, 2010 at 19:45
  • $\begingroup$ It's not square no, however I know that one of the sides will always be longer than the other. I think I've got it, actually. Simplifying it into 2D on the longest axis, and stipulating that the distance to the far vertex on the base and the far vertex on the truncated top should be equal (i.e. the bounding sphere touches the outside vertices), and the maths just kind of works out from there I think. I got that the distance from the base should be (Wn^s + Wf^2 +x^2)/2x, where Wn is the half-width of the narrow side, Wf is the half-width of the fat end, and x is distance from base to top. $\endgroup$
    – Bob
    Commented Feb 3, 2010 at 19:55
  • 7
    $\begingroup$ This problem seems like it would be better suited for one of the other sites mentioned in the FAQ. Anyway, whether it's symmetric or not, the smallest sphere should pass through some vertices of the object, so the center is the same distance from several vertices. The locus of points equidistant from two points is a plane defined by one linear equation. If there are 2 vertices, the sphere's center must be the midpoint of the line segment connecting them. If 3, the locus is a line which intersects the vertices' plane in one point. If there are 4 non-coplanar vertices, the locus is one point. $\endgroup$
    – Douglas Zare
    Commented Feb 3, 2010 at 19:56
  • $\begingroup$ I reverted an earlier edit, noting that there is only one 'r' in 'frustum' (confirmed using multiple sources). $\endgroup$
    – Darsh Ranjan
    Commented Feb 4, 2010 at 1:35
  • $\begingroup$ Ah, that was my fault, Darsh. Thanks for the correction $\endgroup$
    – Yemon Choi
    Commented Feb 4, 2010 at 2:25

1 Answer 1

Reset to default
5
$\begingroup$

I knew the answer was simple, but I just couldn't think of it, so I went and looked it up in some old course notes from a computational geometry course. This elegant solution is apparently due to Emo Welzl and finds the smallest enclosing ball of any number of points in any dimensionality. It should work nicely for you. Here it is, paraphrased in pseudo-Haskell from "Backwards Analysis of Randomized Geometric Algorithms," by Raimund Seidel: 

minidisk :: ({Point}, {Point}) -> Ball
minidisk({}, C) = primitive_ball(C)
minidisk(T, C)  = 
    let p  = uniformly_random_point(T)
        T' = T\{p}
        B' = minidisk(T', C)
    in 
        if contains(B', p) then B' 
        else minidisk(T', union(C, {p}))

Here T and C are finite sets. primitive_ball(C), as one would guess, is the ball whose center and radius are the circumcenter and circumradius of the points in C. minidisk(T, C) finds the smallest ball enclosing all the points of T and having all the points of C on its boundary. What you want is thus minidisk(T, {}), where T is the set of eight vertices of the frustum.

(Note that p is chosen uniformly at random to obtain a good expected running time for large T; you can actually choose p from T however you want without sacrificing correctness. In fact, in your case, I wouldn't be surprised if there were some particular ordering of the vertices that results in better performance. Experiment!)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .