CGAL::is_simple_2

Definition

The function is_simple_2 computes if a polygon is simple, that is, does not self-intersect.

#include <CGAL/Polygon_2_algorithms.h>

template <class ForwardIterator, class Traits>
inline bool	is_simple_2 ( ForwardIterator first, ForwardIterator last, Traits traits)

A polygon is called simple if the edges do not intersect, except consecutive edge in their common vertex. This function checks if the polygon defined by the range first ... last is simple.

Requirements

1. Traits is a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:
   • Point_2
   • Less_xy_2
   • Orientation_2
   • less_xy_2
   • orientation_2
2. ForwardIterator::value_type should be Traits::Point_2,

Implementation

The simplicity test is implemented by means of a plane sweep algorithm. The algorithm is quite robust when used with inexact number types. The running time is O(n log n), where n is the number of vertices of the polygon.

See Also

PolygonTraits_2
CGAL::Polygon_2<PolygonTraits_2, Container>