CGAL 6.1 - 2D Visibility

Loading...
Searching...
No Matches
List of all members
CGAL::Triangular_expansion_visibility_2< Arrangement_2_, RegularizationCategory > Class Template Reference
Reference Manual » Classes

`#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`

See also
  `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`).
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.

## Member Typedef Documentation

## ◆ Regularization_category

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

## ◆ attach()

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`.