 CGAL 4.7 - 2D Visibility
CGAL::Triangular_expansion_visibility_2< Arrangement_2_, RegularizationCategory > Class Template Reference

#include <CGAL/Triangular_expansion_visibility_2.h>

Definition

template<typename Arrangement_2_, typename RegularizationCategory = Tag_true> class CGAL::Triangular_expansion_visibility_2< Arrangement_2_, RegularizationCategory >

This class is a model of the concept Visibility_2 can answer visibility queries within a polygon that may have holes.

The algorithm obtains a constrained triangulation from the input arrangement, then computes visibility by expanding the triangle that contains the query point. Preprocessing takes $$O(n)$$ time and $$O(n)$$ space, where $$n$$ is the number of vertices of input polygon. The query time is $$O(nh)$$, where $$h$$ is the number of holes+1 of input polygon. Thus, for simple polygons (or a polygon with a constant number of holes) the algorithm complexity is linear, but it is $$O(n^2)$$ in the worst case, as the number of holes can be linear in $$n$$.

Template Parameters
 Arrangement_2_ is the type used to represent the input environment. It must be an instance of CGAL::Arrangement_2, where its CGAL::Arrangement_2::Traits_2 must be an instance of CGAL::Arr_segment_traits_2, or of CGAL::Arr_non_caching_segment_traits_2. RegularizationCategory indicates whether the output should be regularized. It can be specified by one of the following: Tag_true or Tag_false, where Tag_false is the default value.
Is Model Of:
Visibility_2
CGAL::Simple_polygon_visibility_2
CGAL::Rotational_sweep_visibility_2
Examples:
Visibility_2/general_polygon_example.cpp.

Types

typedef Arrangement_2_ Arrangement_2
The type of the input arrangement.

Tags

typedef RegularizationCategory Regularization_category
identifies whether the regularized visibility area is computed (either Tag_true or Tag_false). More...

typedef Tag_true Supports_general_polygon_category
See Visibility_2::Supports_general_polygon_category.

typedef Tag_true Supports_simple_polygon_category
See Visibility_2::Supports_simple_polygon_category.

Functions

void attach (const Arrangement_2 &arr)
Attaches the given arrangement to the visibility object and computes the restricted triangulation. More...

Member Typedef Documentation

template<typename Arrangement_2_ , typename RegularizationCategory = Tag_true>
 typedef RegularizationCategory CGAL::Triangular_expansion_visibility_2< Arrangement_2_, RegularizationCategory >::Regularization_category

identifies whether the regularized visibility area is computed (either Tag_true or Tag_false).

Member Function Documentation

template<typename Arrangement_2_ , typename RegularizationCategory = Tag_true>
 void CGAL::Triangular_expansion_visibility_2< Arrangement_2_, RegularizationCategory >::attach ( const Arrangement_2 & arr)

Attaches the given arrangement to the visibility object and computes the restricted triangulation.

This takes $$O(n)$$ time, where $$n$$ is the number of vertices.

From this moment on the class observes changes in the arrangement. If the arrangement changes a new restricted triangulation is computed. Re-attaching forces re-computation.

In case the object is already attached to another arrangement, the visibility object gets detached before being attached to arr.