Visibility between two edges of a simple polygon
One of the most recurring themes in many computer applications such as graphics automated cartography, image processing and robotics is the notion of visibility. We are concerned with the visibility between two edges of a simple n-vertex polygon. Four natural definitions of edge-to- edge visibility are proposed. There exist O(n log n) algorithms and complicated O(n log log n) algorithms to solve this problem partially and indirectly. A linear running time, and thus optimal algorithm is presented to determine edge-to-edge visibility under any of the four definitions. This simple, efficient, and direct algorithm without computing the triangulation of the simple polygon also identifies the visibility region if it exists.
- A combinational approach to polygon similarity
- A combinatorial theorem in plane geometry
- A linear algorithm for computing the visibility polygon from a point
- A linear algorithm for eliminating hidden-lines from a polygonal cylinder
- A new data structure for representing sorted lists
- A simple linear hidden-line algorithm for star-shaped polygons
- An Algorithm for the Solution of the Two-Dimensional ``Hidden-Line Problem
- An Optimal Algorithm for Finding the Kernel of a Polygon
- Applications of a two-dimensional hidden-line algorithm to other geometric problems
- Design and Analysis of a Data Structure for Representing Sorted Lists
- Euclidean shortest paths in the presence of rectilinear barriers
- scientific article; zbMATH DE number 3887060 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3323651 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Shortest paths in the plane with convex polygonal obstacles
- Triangulating a simple polygon
- Visibility of a simple polygon
- Visibility of disjoint polygons
- Reconstructing visible regions from visible segments
- Corrections to Lee's visibility polygon algorithm
- Three-dimensional weak visibility: Complexity and applications
- Line segment visibility with sidedness constraints
- Characterizing and recognizing LR-visibility polygons
- Computing the visibility polygon from an edge
- Visibility of a simple polygon
- Shortest path solves edge-to-edge visibility in a polygon
- scientific article; zbMATH DE number 4050998 (Why is no real title available?)
- scientific article; zbMATH DE number 4078149 (Why is no real title available?)
- Reasoning about visibility
- Computing Visibility Information in an Inaccurate Simple Polygon
- Open guard edges and edge guards in simple polygons
- scientific article; zbMATH DE number 1424307 (Why is no real title available?)
- Visibility Algorithms in the Plane
- Tracing compressed curves in triangulated surfaces
- Three dimensional weak visibility: Complexity and applications
- An optimal algorithm for finding the edge visibility polygon under limited visibility
- Computing shortest transversals
- Some chain visibility problems in a simple polygon
This page was built for publication: Visibility between two edges of a simple polygon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1096432)
