CGAL 6.1.1 - 2D Visibility

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

`#include <CGAL/Simple_polygon_visibility_2.h>`

## Definition

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

This class is a model of the concept `Visibility_2` can answer visibility queries within a simple polygon with no holes.

This class implements the algorithm of B.Joe and R.B.Simpson [4]. The algorithm is a modification and extension of the linear time algorithm of Lee [5]. It computes the visibility region from a viewpoint that is in the interior or on the boundary of the polygon.

While scanning the boundary the algorithm uses a stack to manipulate the vertices, and ultimately yields the visibility region. For each scanned edge, at most 2 points are pushed onto the stack. Overall, at most 2 \( n \) points are pushed or popped. Thus, the time and space complexities of the algorithm are \(O(n)\)$ even in case of degeneracies such as needles, where \( n \) is the number of the vertices of the polygon.

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::Rotational_sweep_visibility_2`
  `CGAL::Triangular_expansion_visibility_2`

Examples
  Visibility_2/simple_polygon_visibility_2.cpp.

## Types
typedef Arrangement_2 | Arrangement_2
| The arrangement type is used for input.

## Tags
typedef RegularizationCategory | Regularization_category
| identifies whether the regularized visibility area is computed (either `#Tag_true` or `#Tag_false`).
typedef Tag_false | 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.

## Member Typedef Documentation

## ◆ Regularization_category

template<typename Arrangement_2_ , typename RegularizationCategory = Tag_true>

typedef RegularizationCategory CGAL::Simple_polygon_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::Simple_polygon_visibility_2< Arrangement_2_, RegularizationCategory >::attach | ( | const Arrangement_2 & | arr | ) |

Attaches the given arrangement to the visibility object.

This operation takes \(O(1)\) as the class does no preprocessing.

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