Abstract
A set of spanning line segments ℊ in a polyhedronP preserves the property of intersection; that is, a plane intersectsP if and only if it also intersects ℊ. This paper gives a linear time algorithm for constructing ℊ for a polyhedron withN extreme vertices. IfN is odd, the algorithm is optimal in yielding [N/2] + 1 spanning line segments. IfN is even, it gives (N/2) + 1, which is optimal in some cases and nearly optimal in others.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Blum H (1967) A transform for extracting new descriptors of shape. In: Whaten-Dunn W (ed) Models for the perception of speech and visual form. MIT Press, Cambridge, Mass
Blum H, Nagel R (1977) Shape description using weighted symmetric axis features. Patt Recogn 10: 167–180
Bookstein FL (1979) The line skeleton. Comput Graph Image Processing 11: 123–137
Edelsbrunner H (1987) Algorithms in combinatorial geometry, Springer, Berlin Heidelberg New York
Goldak JA, Yu X, Knight A, Dong L (1991) Constructing discrete medial axis of 3-D objects. Int J Comput Geom Appl 1: 327–339
Hoffmann CM (1989) Geometric and solid modeling: an introduction. Morgan Kaufmann, San Mateo, Calif
Hoffmann CM (1990) How to construct the skeleton of CSG objects. Technical Report CSD-TR-1014, Computer Science Department, Purdue University, West Lafayette, IN 47907, USA
Kirkpatrick DG (1979) Efficient computation of continuous skeletons. IEEE 20th Annual Symposium on Foundations of Computer Science. San Juan, Puerto Rico: 18–27
Lee DT (1982) Medial axis transformation of a planar shape. IEEE Trans Patt Anal Machine Intell 4: 363–369
Matheron G (1988) Examples of topological properties of skeletons. In: Serra J (ed) Image analysis and mathematical morphology, vol 2: theoretical advances. Academic Press, London, pp 217–238
Mckenna M (1987) Worst-case optimal hidden-surface removal. ACM Trans Graph 6: 19–28
O'Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press, Oxford, UK
O'Rourke J (1994) Computational geometry in C, Cambridge University Press, Cambridge, UK
Ratschek H, O'Rourke J (1993) Test for intersection between plane and box. Comput Aided Design 25: 249–250
Wang JY, Yuen LD, Woo TC (1993a) A method for testing intersection between plane and polyhedron. Technical Report, GINTIC Institute of Manufacturing Technology, Nanyang Technological University, Singapore
Wang JY, Yuen LD, Woo TC, Chen XM (1993b) The spanning line sgments of a polyhedron. To appear: ASME Trans J Mechanical Design (March 1996) Vol. 118 also available as Technical Report TR93-42, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, Mich
Wu AY, Bhaskar SK, Rosenfeld A (1986) Computation of geometric properties from the medial axis transform inO(n logn) time. Comput Vision Graph Image Processing 34: 76–92
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wang, ME., Woo, T.C., Chen, LL. et al. Computing spanning line segments in three dimensions. The Visual Computer 12, 173–180 (1996). https://doi.org/10.1007/BF01782320
Issue Date:
DOI: https://doi.org/10.1007/BF01782320