home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2701 < prev    next >
Encoding:
Text File  |  1992-12-15  |  1.4 KB  |  39 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!munnari.oz.au!metro!usage!usage.csd!lambert
  3. From: lambert@spectrum.cs.unsw.oz.au (Tim Lambert)
  4. Subject: Re: comp geometry
  5. In-Reply-To: bross@splatter.nas.nasa.gov's message of Mon, 7 Dec 92 21:51:44 GMT
  6. Message-ID: <LAMBERT.92Dec15202435@nankeen.spectrum.cs.unsw.oz.au>
  7. Sender: news@usage.csd.unsw.OZ.AU
  8. Nntp-Posting-Host: nankeen.spectrum.cs.unsw.oz.au
  9. Organization: CS&E, Uni of NSW, Australia
  10. References: <1992Dec7.215144.962@nas.nasa.gov>
  11. Date: Tue, 15 Dec 1992 10:24:35 GMT
  12. Lines: 25
  13.  
  14. >>>>> On Mon, 7 Dec 92 21:51:44 GMT, bross@splatter.nas.nasa.gov (Bill Ross) said:
  15.  
  16. > Does anyone have a formula or algorithm for calculating the biggest
  17. > sphere that can fit in an irregular hexahedron? 
  18.  
  19. If the hexahedron is convex, then the sphere will touch four faces, so
  20. you could test all 6_choose_4 subsets of the faces to see if the
  21. sphere touching the four support planes is inside the hexahedron and
  22. take the largest such sphere.
  23.  
  24. If it is not convex then you have to worry about spheres tangent to
  25. concave vertices and edges.
  26.  
  27. > How about an n-sided  figure?
  28.  
  29. If it is convex, you could take the dual, and find the smallest
  30. enclosing sphere by the obvious generalization of of the smalles
  31. enclosing circle algorithm.
  32.  
  33. If not convex, then the centre of the sphere lies on Voronoi diagram
  34. of the polyhedron, so searching that should do it, but I don't know of
  35. a published algorithm for this...
  36.  
  37. Tim
  38.  
  39.