"Fossies" - the Fresh Open Source Software Archive

Member "doc_html/Visibility_2/classCGAL_1_1Triangular__expansion__visibility__2.html" (8 Nov 2019, 20315 Bytes) of package /linux/misc/CGAL-5.0-doc_html.tar.xz:


Caution: In this restricted "Fossies" environment the current HTML page may not be correctly presentated and may have some non-functional links. You can here alternatively try to browse the pure source code or just view or download the uninterpreted raw source code. If the rendering is insufficient you may try to find and view the page on the project site itself.

\( \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 5.0 - 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.
RegularizationCategoryindicates 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). 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

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