CGAL 5.3 - 2D Visibility
|
#include <CGAL/Simple_polygon_visibility_2.h>
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.
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. |
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 ). More... | |
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. More... | |
typedef RegularizationCategory CGAL::Simple_polygon_visibility_2< Arrangement_2_, RegularizationCategory >::Regularization_category |
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 pre-processing.
In case the object is already attached to another arrangement, the visibility object gets detached before being attached to arr
.