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

David Rappaport; Godfried T. Toussaint

doi:10.1016/0167-8655(85)90040-6

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

David Rappaport, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	35-39
Number of pages	5
Journal	Pattern Recognition Letters
Volume	3
Issue number	1
DOIs	https://doi.org/10.1016/0167-8655(85)90040-6
State	Published - 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

Access to Document

10.1016/0167-8655(85)90040-6

Cite this

@article{05f4ecf9a09240a6872395bf3e83b230,

title = "A simple linear hidden-line algorithm for star-shaped polygons",

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.",

keywords = "Algorithms, complexity, computational geometry, discrete geometry, hidden-line problem, star-shaped polygons, visibility",

author = "David Rappaport and Toussaint, {Godfried T.}",

note = "Funding Information: research was supported by FCAC grant no. EQ1678.",

year = "1985",

month = jan,

doi = "10.1016/0167-8655(85)90040-6",

language = "English (US)",

volume = "3",

pages = "35--39",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

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

AU - Rappaport, David

AU - Toussaint, Godfried T.

N1 - Funding Information: research was supported by FCAC grant no. EQ1678.

PY - 1985/1

Y1 - 1985/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - complexity

KW - computational geometry

KW - discrete geometry

KW - hidden-line problem

KW - star-shaped polygons

KW - visibility

UR - http://www.scopus.com/inward/record.url?scp=46549104526&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46549104526&partnerID=8YFLogxK

U2 - 10.1016/0167-8655(85)90040-6

DO - 10.1016/0167-8655(85)90040-6

M3 - Article

AN - SCOPUS:46549104526

SN - 0167-8655

VL - 3

SP - 35

EP - 39

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this