Article View: comp.theory
Article #1715Re: comp geometry
From: Tim Lambert
Date: Tue, 15 Dec 1992 10:24
Date: Tue, 15 Dec 1992 10:24
24 lines
1479 bytes
1479 bytes
>>>>> On Mon, 7 Dec 92 21:51:44 GMT, bross@splatter.nas.nasa.gov (Bill Ross) said: > Does anyone have a formula or algorithm for calculating the biggest > sphere that can fit in an irregular hexahedron? If the hexahedron is convex, then the sphere will touch four faces, so you could test all 6_choose_4 subsets of the faces to see if the sphere touching the four support planes is inside the hexahedron and take the largest such sphere. If it is not convex then you have to worry about spheres tangent to concave vertices and edges. > How about an n-sided figure? If it is convex, you could take the dual, and find the smallest enclosing sphere by the obvious generalization of of the smalles enclosing circle algorithm. If not convex, then the centre of the sphere lies on Voronoi diagram of the polyhedron, so searching that should do it, but I don't know of a published algorithm for this... Tim
Technical Details
Message-ID:
<LAMBERT.92Dec15202435@nankeen.spectrum.cs.unsw.oz.au>Path:
arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!metro!usage!usage.csd!lambertReferences:
<1992Dec7.215144.962@nas.nasa.gov>Show Full Headers
Complete Article Headers
Newsgroups: comp.theory Path: arc1-ca.pugleaf.net!sparky!uunet!munnari.oz.au!metro!usage!usage.csd!lambert From: lambert@spectrum.cs.unsw.oz.au (Tim Lambert) Subject: Re: comp geometry In-Reply-To: bross@splatter.nas.nasa.gov's message of Mon, 7 Dec 92 21:51:44 GMT Message-ID: <LAMBERT.92Dec15202435@nankeen.spectrum.cs.unsw.oz.au> Sender: news@usage.csd.unsw.OZ.AU Nntp-Posting-Host: nankeen.spectrum.cs.unsw.oz.au Organization: CS&E, Uni of NSW, Australia References: <1992Dec7.215144.962@nas.nasa.gov> Date: Tue, 15 Dec 1992 10:24:35 GMT Lines: 25