CGAL 6.1  2D Visibility

This package provides functionality to compute the visibility region within polygons in two dimensions. The package is based on the package 2D Arrangements and uses CGAL::Arrangement_2 as the fundamental class to specify the input as well as the output. Hence, a polygon \( P \) is represented by a bounded arrangement face \( f \) that does not have any isolated vertices and any edge that is adjacent to \( f \) separates \( f \) from another face. Note that \( f \) may contain holes. Similarly, a simple polygon is represented by a face without holes.
Given two points \( p \) and \( q \) in \( P \), they are said to be visible to each other iff the segment \( pq \subset P \), where \( P \) is considered to be closed, that is, \(\partial P \subset P\). For a query point \( q \in P \), the set of points that are visible from \( q \) is defined as the visibility region of \( q \), denoted by \( V_q \)
As illustrated in Figure 24.1 (1) the visibility region \( V_q \) of a query point \( q \) may not be a polygon. In the figure, all labeled points are collinear, which implies that the point \( c \) is visible to \( q \), that is, the segment \( bc \) is part of \( V_q \). We call such low dimensional features that are caused by degeneracies needles
. However, for many applications these needles are actually irrelevant. Moreover, for some algorithms it is even more efficient to ignore needles in the first place. Therefore, this package offers also functionality to compute the regularized visibility area \( \overline{V_q} = closure(interior(V_q)) = (V_q\setminus\partial V_q) \cup \partial (V_q\setminus\partial V_q)\), as shown in Figure 24.1 (2). For more information about regularization, refer to Chapter 2D Regularized Boolean SetOperations.
Answering visibility queries is, in many ways, similar to answering pointlocation queries. Thus, we use the same design used to implement 2D Arrangements point location. Each of the various visibility class templates employs a different algorithm or strategy for answering queriesThe term strategy is borrowed from the designpattern taxonomy [3]. A strategy provides the means to define a family of algorithms, each implemented by a separate class. All classes that implement the various algorithms are made interchangeable, letting the algorithm in use vary according to the user choice.. Similar to the pointlocation case, some of the strategies require preprocessing. Thus, before a visibility object is used to answer visibility queries, it must be attached to an arrangement object. Afterwards, the visibility object observes changes to the attached arrangement. Hence, it is possible to modify the arrangement after attaching the visibility object. However, this feature should be used with caution as each change to the arrangement also requires an update of the auxiliary data structures in the attached object.
An actual query is performed by giving the view point \( p \) and its containing face \( f \) (which must represent a valid polygon) to a visibility object. For more details see the documentation of the overloaded member function Visibility_2::compute_visibility()
.
The following models of the Visibility_2
concept are provided:
Class  Function  Preprocessing  Query  Algorithm 

Simple_polygon_visibility_2  simple polygons  No  \(O(n)\)$ time and \(O(n)\)$ space  B. Joe and R. B. Simpson [4] 
Rotational_sweep_visibility_2  polygons with holes  No  \(O(n\log n)\)$ time and \(O(n)\)$ space  T. Asano [1] 
Triangular_expansion_visibility_2  polygons with holes  \(O(n)\)$ time and \(O(n)\)$ space  \(O(nh)\)$ time and \(O(n)\)$ space.  Bungiu et al. [2] 
Where \( n \) denotes the number of vertices of \( f \) and \( h \) the number of holes+1.
The left hand side of Figure Figure 24.2 depicts the outer boundary of a cathedral, which is a simple polygon with 565 vertices. The right hand side shows the cathedral also with its inner pillars, which is a polygon (with holes) with 1153 vertices. The following table shows the total running time consumption of the computation of all visibility polygons for all vertices of the cathedral.
Boundary Cathedral  total preprocessing time  total query time 

Simple_polygon_visibility_2    0.38 
Rotational_sweep_visibility_2    1.01 
Triangular_expansion_visibility_2  0.01  0.06 
The second table shows the same for the complete cathedral. The table does not report the time for Simple_polygon_visibility_2
as this algorithm can only handle simple polygons.
Complete Cathedral  total preprocessing time  total query time 

Rotational_sweep_visibility_2    1.91 
Triangular_expansion_visibility_2  0.01  0.04 
Thus, in general we recommend to use Triangular_expansion_visibility_2
even if the polygon is simple. The main advantage of the algorithm is its locality. After the triangle that contains the query point is located in the triangulation, the algorithm explores neighboring triangles, but only those that are actually seen. In this sense the algorithm can be considered as output sensitive. Note that the Triangular_expansion_visibility_2
algorithm performs better on the full cathedral since the additional pillars block the view early in many cases. However, if the simple polygon is rather convex (i.e., nearly all boundary is seen) or if only one (or very little) queries are required, using one of the algorithms that does not require preprocessing is advantageous.
The following example shows how to obtain the regularized and nonregularized visibility regions.
File Visibility_2/simple_polygon_visibility_2.cpp
The following example shows how to obtain the regularized visibility region using the model Triangular_expansion_visibility_2
, see Figure 24.4. The arrangement has six bounded faces and an unbounded face. The query point \( q \) is on a vertex. The red arrow denotes the halfedge \( \overrightarrow{pq} \), which also identifies the face in which the visibility region is computed.
File Visibility_2/general_polygon_example.cpp
This package was first developed during Google Summer of Code 2013: Francisc Bungiu developed the CGAL::Simple_polygon_visibility_2
, Kan Huang developed the CGAL::Rotational_sweep_visibility_2
, and Michael Hemmer developed the CGAL::Triangular_expansion_visibility_2
.
During Google Summer of Code 2014 Ning Xu fixed a bug in CGAL::Simple_polygon_visibility_2
and improved the testsuite.