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

1. 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
2. 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