Reconstructing visible regions from visible segments

DOI10.1007/BF01935050MaRDI QIDQ1090463zbMATH OpenOpenAlexWikidataFDO

Authors Varol Akman, William Randolph Franklin

Publication date 1986

Published in BIT (Search for Journal in Brave)

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

zbMATH Keywords

cartographycomputer graphicsgraph problemhidden surface algorithmsobject spacepoint-locationpolyhedral scenesreconstructing visible regions from visible edge segmentsstraight-edge planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99) Computing methodologies and applications (68U99)

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.

Recommendations

• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
• Visibility between two edges of a simple polygon
• Visible surface calculation for complex unstructured polygonal scenes
• scientific article; zbMATH DE number 3876624
• Visibility of a simple polygon

Cites work

• A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra
• Finding the intersection of two convex polyhedra
• scientific article; zbMATH DE number 3958767 (Why is no real title available?)
• scientific article; zbMATH DE number 3451445 (Why is no real title available?)
• Plane-sweep algorithms for intersecting geometric figures
• Reconstructing visible regions from visible segments

Cited in

(5)

• Reconstructing visible regions from visible segments
• Visibility extension via mirror-edges to cover invisible segments
• REGION COLORING, EDGE COLORING, AND SCAN-CONVERSION OF MAPS
• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
• scientific article; zbMATH DE number 1931930 (Why is no real title available?)

This page was built for publication: Reconstructing visible regions from visible segments

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