CGAL 4.7 - 2D Visibility: User Manual

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 2D Visibility

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
User Manual

Authors
  Michael Hemmer, Kan Huang, Francisc Bungiu, Ning Xu

# Introduction

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 \)

## Degeneracies and Regularization

Figure 23.1 Non-regularized visibility and regularized visibility.

As illustrated in Figure 23.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 23.1 (2). For more information about regularization, refer to Chapter 2D Regularized Boolean Set-Operations.

# Classes and Algorithms

Answering visibility queries is, in many ways, similar to answering point-location 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 design-pattern taxonomy~ghjv-dpero-95. 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 point-location 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[3]
`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.

# Running Time in Practice

Figure 23.2 Example representing a cathedral.

The left hand side of Figure Figure 23.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.

# Example of Visibility in a Simple Polygon

The following example shows how to obtain the regularized and non-regularized visibility regions.

Figure 23.3

The visibility region of \( q \) in a simple polygon: (1) non-regularized visibility; and (2) regularized visibility.

File Visibility_2/simple_polygon_visibility_2.cpp
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Simple_polygon_visibility_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arr_naive_point_location.h>
#include <istream>
#include <vector>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
typedef Arrangement_2::Face_handle Face_handle;
typedef Arrangement_2::Edge_const_iterator Edge_const_iterator;
typedef Arrangement_2::Ccb_halfedge_circulator Ccb_halfedge_circulator;
int main() {
//create environment
Point_2 p1(0,4), p2(0,0), p3(3,2), p4(4,0), p5(4,4), p6(1,2);
std::vector<Segment_2> segments;
segments.push_back(Segment_2(p1, p2));
segments.push_back(Segment_2(p2, p3));
segments.push_back(Segment_2(p3, p4));
segments.push_back(Segment_2(p4, p5));
segments.push_back(Segment_2(p5, p6));
segments.push_back(Segment_2(p6, p1));
Arrangement_2 env;
CGAL::insert_non_intersecting_curves(env,segments.begin(),segments.end());
// find the face of the query point
// (usually you may know that by other means)
Point_2 q(0.5, 2);
Arrangement_2::Face_const_handle * face;
CGAL::Arr_naive_point_location<Arrangement_2> pl(env);
CGAL::Arr_point_location_result<Arrangement_2>::Type obj = pl.locate(q);
// The query point locates in the interior of a face
face = boost::get<Arrangement_2::Face_const_handle> (&obj);
// compute non regularized visibility area
// Define visibiliy object type that computes non-regularized visibility area
typedef CGAL::Simple_polygon_visibility_2<Arrangement_2, CGAL::Tag_false> NSPV;
Arrangement_2 non_regular_output;
NSPV non_regular_visibility(env);
non_regular_visibility.compute_visibility(q, *face, non_regular_output);
std::cout << "Non-regularized visibility region of q has "
<< non_regular_output.number_of_edges()
<< " edges:" << std::endl;
for (Edge_const_iterator eit = non_regular_output.edges_begin(); eit != non_regular_output.edges_end(); ++eit)
std::cout << "[" << eit->source()->point() << " -> " << eit->target()->point() << "]" << std::endl;
// compute non regularized visibility area
// Define visibiliy object type that computes regularized visibility area
typedef CGAL::Simple_polygon_visibility_2<Arrangement_2, CGAL::Tag_true> RSPV;
Arrangement_2 regular_output;
RSPV regular_visibility(env);
regular_visibility.compute_visibility(q, *face, regular_output);
std::cout << "Regularized visibility region of q has "
<< regular_output.number_of_edges()
<< " edges:" << std::endl;
for (Edge_const_iterator eit = regular_output.edges_begin(); eit != regular_output.edges_end(); ++eit)
std::cout << "[" << eit->source()->point() << " -> " << eit->target()->point() << "]" << std::endl;
return 0;
}

# Example of Visibility in a Polygon with Holes

The following example shows how to obtain the regularized visibility region using the model `Triangular_expansion_visibility_2`, see Figure 23.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.

Figure 23.4 The visibility region of \( q \) in a polygon with two holes.
File Visibility_2/general_polygon_example.cpp
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Triangular_expansion_visibility_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <iostream>
#include <vector>
// Define the used kernel and arrangement
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
typedef Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
typedef Arrangement_2::Face_handle Face_handle;
// Define the used visibility class
typedef CGAL::Triangular_expansion_visibility_2<Arrangement_2> TEV;
int main() {
// Defining the input geometry
Point_2 p1(1,2), p2(12, 3), p3(19,-2), p4(12,6), p5(14,14), p6( 9,5);
Point_2 h1(8,3), h2(10, 3), h3( 8, 4), h4(10,6), h5(11, 6), h6(11,7);
std::vector<Segment_2> segments;
segments.push_back(Segment_2(p1,p2));
segments.push_back(Segment_2(p2,p3));
segments.push_back(Segment_2(p3,p4));
segments.push_back(Segment_2(p4,p5));
segments.push_back(Segment_2(p5,p6));
segments.push_back(Segment_2(p6,p1));
segments.push_back(Segment_2(h1,h2));
segments.push_back(Segment_2(h2,h3));
segments.push_back(Segment_2(h3,h1));
segments.push_back(Segment_2(h4,h5));
segments.push_back(Segment_2(h5,h6));
segments.push_back(Segment_2(h6,h4));
// insert geometry into the arrangement
Arrangement_2 env;
CGAL::insert_non_intersecting_curves(env,segments.begin(),segments.end());
//Find the halfedge whose target is the query point.
//(usually you may know that already by other means)
Point_2 query_point = p4;
Halfedge_const_handle he = env.halfedges_begin();
while (he->source()->point() != p3 || he->target()->point() != p4)
he++;
//visibility query
Arrangement_2 output_arr;
TEV tev(env);
Face_handle fh = tev.compute_visibility(query_point, he, output_arr);
//print out the visibility region.
std::cout << "Regularized visibility region of q has "
<< output_arr.number_of_edges()
<< " edges." << std::endl;
std::cout << "Boundary edges of the visibility region:" << std::endl;
Arrangement_2::Ccb_halfedge_circulator curr = fh->outer_ccb();
std::cout << "[" << curr->source()->point() << " -> " << curr->target()->point() << "]" << std::endl;
while (++curr != fh->outer_ccb())
std::cout << "[" << curr->source()->point() << " -> " << curr->target()->point() << "]"<< std::endl;
return 0;
}

# Implementation History

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.