CGAL::Simple_polygon_visibility_2< Arrangement_2_, RegularizationCategory > Class Template Reference

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