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

DOI10.1007/BF01890987MaRDI QIDQ1099952zbMATH OpenFDO

Authors David Rappaport

Publication date 1986

Published in The Visual Computer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01890987

zbMATH Keywords

computational geometrygeometric algorithmshidden-line eliminationworst case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Review text

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 of \(O(n^ 2)\). It is the intent 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.

Recommendations

• A worst-case efficient algorithm for hidden-line elimination^†
• New algorithms for special cases of the hidden line elimination problem
• scientific article; zbMATH DE number 3974354
• A simple linear hidden-line algorithm for star-shaped polygons
• Space reduction and an extension for a hidden line elimination algorithm

Cites work

• A linear algorithm for computing the visibility polygon from a point
• A linear algorithm for finding the convex hull of a simple polygon
• A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra
• Finding the convex hull of a simple polygon
• scientific article; zbMATH DE number 3780616 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)

Cited in

(13)

• Visibility between two edges of a simple polygon
• Hidden-surface removal in polyhedral cross-sections
• Hidden-line algorithm for curved surfaces
• Space reduction and an extension for a hidden line elimination algorithm
• Hidden-line algorithm based on range searching
• A simple linear hidden-line algorithm for star-shaped polygons
• scientific article; zbMATH DE number 3974354 (Why is no real title available?)
• On the hidden line removal problem
• Perspective projection of non-convex polyhedra
• A worst-case efficient algorithm for hidden-line elimination^†
• scientific article; zbMATH DE number 645774 (Why is no real title available?)
• A simplified technique for hidden-line elimination in terrains
• Space-optimal hidden line elimination for rectangles

This page was built for publication: A linear algorithm for eliminating hidden-lines from a polygonal cylinder

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099952)