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>

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_object()
   • orientation_2_object()
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>