Reconstructing visible regions from visible segments
type: Item
instance of: scholarly article
title: Reconstructing visible regions from visible segments
zbMATH Open document ID: 0621.68045
DOI: 10.1007/BF01935050
author: Varol Akman
author: William Randolph Franklin
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: An algorithm is presented for reconstructing visible regions from visible edge segments in object space. This has applications in hidden surface algorithms operating on polyhedral scenes and in cartography. A special case of reconstruction can be formulated as a graph problem: ''Determine the faces of a straight-edge planar graph given in terms of its edges.'' This is accomplished in O(n log ) time using linear space for a graph with n edges, and is worst-case optimal. The graph may have separate components but the components must not contain each other. The general problem of reconstruction is then solved by applying our algorithm to each component in the containment relation.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4007739
zbMATH Keywords: point-location
zbMATH Keywords: computer graphics
zbMATH Keywords: reconstructing visible regions from visible edge segments
zbMATH Keywords: object space
zbMATH Keywords: hidden surface algorithms
zbMATH Keywords: polyhedral scenes
zbMATH Keywords: cartography
zbMATH Keywords: graph problem
zbMATH Keywords: straight-edge planar graph
Wikidata QID: Q57699723
MaRDI profile type: Publication
cites work: A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra
cites work: Finding the intersection of two convex polyhedra
cites work: Plane-sweep algorithms for intersecting geometric figures
cites work: Q3727415
cites work: Q4775467
full work available at URL: https://doi.org/10.1007/bf01935050
OpenAlex ID: W2008378065
description: scientific article; zbMATH DE number 4007739