Abstract
A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity ofO(n 2). It is the interent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho A, Hopcroft J, Ullman J (1974) The Design and Analysis of Computer Algorithms, Addison Wesley
Avis D, Toussaint GT (1981) An Optimal Algorithm for Determining the Visibility of a Polygon from an Edge. IEEE Trans Comp, vol C-30, no 12
nEl Gindy H, Avis D (1981) A Linear Algorithm for Computing the Visibility Polygon from a Point. J Algorithms 2:186–197
Franklin WR (1978) 3-D Graphic Display of Discrete Spatial Data by Prism Maps. SIGGRAPH '78 Conference Proceedings
Franklin WR (1981) An Exact Hidden Sphere Algorithm that Operates in Linear Time. Comput Graph Image Process 15:364–379
Graham RL, Yao FF (1984) Finding the Convex Hull of a Simple Polygon. J Algorithms 4:324–331
Klein F (1939) Elementary Mathematics From an Advanced Standpoint, Geometry. Dover, New York
Lee DT (1980) On Finding the Convex Hull of a Simple Polygon. Tech Rep, no. 80-03-FC-01, Northwestern University
Loutrel PP (1970) A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra. IEEE Trans Comp, vol C-19 3
McCallum D, Avis D (1979) A Linear Time Algorithm for Finding the Convex Hull of a Simple Polygon. Inf Process Lett, 9:201–207
Ottmann Th, Widmayer P, Wood D (1982) A Worst-Case Efficient Algorithm for Hidden-Line Elimination. Comput Sci Tech Rep CS-82-33, University of Waterloo, Waterloo
Preparata FP, Supowit KJ (1981) Testing a Simple Polygon for Monotonicity. Inf Process Lett, vol 12, no 4
Rappaport D (1982) Visibility in Restricted Classes of Polyhedra. Master's Thesis, McGill University
Sutherland IE, Sproull RF, Schumacker RA (1974) A Characterization of Ten-Hidden Surface-Algorithms. Comput Surv ACM, vol 6, no 1
Yao FF (1980) On the Priority Approach to Hidden-Surface Algorithms. Proc 21st Ann Symp Found Comput Sci
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rappaport, D. A linear algorithm for eliminating hidden-lines from a polygonal cylinder. The Visual Computer 2, 44–53 (1986). https://doi.org/10.1007/BF01890987
Issue Date:
DOI: https://doi.org/10.1007/BF01890987