A simple linear hidden-line algorithm for star-shaped polygons

David Rappaport, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

A very simple, linear-running-time algorithm is presented for solving the hidden-line problem for star-shaped polygons. The algorithm first decomposes the visibility regions into edge-visible polygons and then solves the hidden-line problem for these simpler polygons. In addition to simplicity the algorithm possesses the virtue of affording a very easy proof of correctness. Some applications where this problem arises are mentioned.

Original languageEnglish (US)
Pages (from-to)35-39
Number of pages5
JournalPattern Recognition Letters
Volume3
Issue number1
DOIs
StatePublished - Jan 1985

Keywords

  • Algorithms
  • complexity
  • computational geometry
  • discrete geometry
  • hidden-line problem
  • star-shaped polygons
  • visibility

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A simple linear hidden-line algorithm for star-shaped polygons'. Together they form a unique fingerprint.

Cite this