Function

CGAL::is_simple_2

Definition

The function is_simple_2 computes if a polygon is simple, that is, if the edges do not intersect, except consecutive edges in their common vertex.

#include <CGAL/Polygon_2_algorithms.h>

template <class ForwardIterator, class Traits>
inline bool is_simple_2 ( ForwardIterator first, ForwardIterator last, Traits traits)
Checks if the polygon defined by the iterator 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:
  2. The value type of ForwardIterator must 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>