A linear algorithm for eliminating hidden-lines from a polygonal cylinder | The Visual Computer Skip to main content
Springer Nature Link
Log in

A linear algorithm for eliminating hidden-lines from a polygonal cylinder

  • Published:
The Visual Computer Aims and scope Submit manuscript

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.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

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

    Google Scholar 

  • 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

    Google Scholar 

  • Graham RL, Yao FF (1984) Finding the Convex Hull of a Simple Polygon. J Algorithms 4:324–331

    Google Scholar 

  • Klein F (1939) Elementary Mathematics From an Advanced Standpoint, Geometry. Dover, New York

    Google Scholar 

  • 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

    Google Scholar 

  • McCallum D, Avis D (1979) A Linear Time Algorithm for Finding the Convex Hull of a Simple Polygon. Inf Process Lett, 9:201–207

    Google Scholar 

  • 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

    Google Scholar 

  • 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

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, McGill University, 805 Sherbroke St. West, H3A 2K6, Montreal, Quebec, Canada

    David Rappaport

Authors
  1. David Rappaport
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01890987

Key words

Search

Navigation