CGAL::bounded_side_2
Definition
The function bounded_side_2 computes if a point lies inside a polygon.
#include <CGAL/Polygon_2_algorithms.h>
|
template <class ForwardIterator, class Traits>
|
|
Bounded_side
|
bounded_side_2 ( ForwardIterator first, ForwardIterator last, Traits::Point_2 point, Traits traits)
|
The function bounded_side_2 computes if a point lies inside a polygon.
The polygon is defined by the sequence of points first...last.
Being inside is defined by the odd-even rule. If we take a ray starting at the
point and extending to infinity (in any direction), we count the number of
intersections. If this number is odd, the point is inside, otherwise it is
outside. If the point is on a polygon edge, a special value is returned. A
simple polygon divides the plane in an unbounded and a bounded region.
According to the definition points in the bounded region are inside the polygon.
Requirements
- Traits is a model of the concept
PolygonTraits_2
.
Only the following members of this traits class are used:
- Compare_x_2
- Compare_y_2
- Orientation_2
- compare_x_2_object
- compare_y_2_object
- orientation_2_object
- ForwardIterator::value_type should be Traits::Point_2,
Implementation
The running time is linear in the number of vertices of the polygon.
A horizontal ray is taken to count the number of intersections.
Special care is taken that the result is correct even if there are degeneracies
(if the ray passes through a vertex).
See Also
PolygonTraits_2
CGAL::oriented_side_2
CGAL::Polygon_2<PolygonTraits_2, Container>
CGAL::Bounded_side
