Function Documentation

◆ area_2()

#include <CGAL/Polygon_2_algorithms.h>

Computes the signed area of the polygon defined by the range of points [first,last) .

The area is returned in the parameter result . The sign is positive for counterclockwise polygons, negative for clockwise polygons. If the polygon is not simple, the area is not well defined. The functionality is also available by the polygon_area_2() function, which returns the area instead of taking it as a parameter.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:

• Compute_area_2 : Computes the signed area of the oriented triangle defined by 3 Point_2 passed as arguments.
• compute_area_2_object()
ForwardIterator must have Traits::Point_2 as value type.

See also

CGAL::polygon_area_2()

PolygonTraits_2

CGAL::orientation_2() CGAL::Polygon_2

#include <CGAL/Polygon_2_algorithms.h>

Returns an iterator to the bottommost point from the range [first,last) .

In case of a tie, the point with the smallest x -coordinate is taken.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the members Less_yx_2 and less_yx_2_object() are used. ForwardIterator must have Traits::Point_2 as value type.

See also

CGAL::left_vertex_2()

CGAL::right_vertex_2()

CGAL::top_vertex_2() CGAL::Polygon_2 PolygonTraits_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.

Template Parameters

Traitsis 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 must have Traits::Point_2 as value type.

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 CGAL::Bounded_side

Examples

Polygon/polygon_algorithms.cpp .

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:

• Less_xy_2
• Orientation_2
• less_xy_2_object
• orientation_2_object
ForwardIterator must have PolygonTraits::Point_2 as value type.

See also

PolygonTraits_2

CGAL::Polygon_2

#include <CGAL/Polygon_2_algorithms.h>

Checks if the polygon defined by the iterator range [first,last) is simple, that is, if the edges do not intersect, except consecutive edges in their common vertex.

Template Parameters

Traitsis 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()
ForwardIterator must have PolygonTraits::Point_2 as value type.

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

Examples

Polygon/polygon_algorithms.cpp , and Polygon/projected_polygon.cpp .

#include <CGAL/Polygon_2_algorithms.h>

Returns an iterator to the leftmost point from the range [first,last) .

In case of a tie, the point with the smallest y -coordinate is taken.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the members Less_xy_2 and less_xy_2_object() are used. ForwardIterator must have Traits::Point_2 as value type.

See also

CGAL::right_vertex_2()

CGAL::top_vertex_2()

CGAL::bottom_vertex_2() CGAL::Polygon_2

#include <CGAL/Polygon_2_algorithms.h>

Computes if a polygon is clockwise or counterclockwise oriented.

Precondition

is_simple_2(first, last, traits);

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:

• Less_xy_2
• less_xy_2_object()
• orientation_2_object()
ForwardIterator must have Traits::Point_2 as value type.

See also

PolygonTraits_2

CGAL::is_simple_2()

CGAL::Polygon_2 CGAL::Orientation

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:

• Less_xy_2
• Compare_x_2
• Compare_y_2
• Orientation_2
• less_xy_2_object()
• compare_x_2_object()
• compare_y_2_object()
• orientation_2_object()
ForwardIterator must have PolygonTraits::Point_2 as value type.

See also

PolygonTraits_2

CGAL::bounded_side_2()

CGAL::is_simple_2() CGAL::Polygon_2 Oriented_side

#include <CGAL/Polygon_2_algorithms.h>

Computes the signed area of the polygon defined by the range of points [first,last) .

The sign is positive for counterclockwise polygons, negative for clockwise polygons. If the polygon is not simple, the area is not well defined.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the following members of this traits class are used:

• Compute_area_2 : Computes the signed area of the oriented triangle defined by 3 Point_2 passed as arguments.
• compute_area_2_object
ForwardIterator must have Traits::Point_2 as value type.

See also

PolygonTraits_2

CGAL::orientation_2()

CGAL::Polygon_2

#include <CGAL/Polygon_2_algorithms.h>

Returns an iterator to the rightmost point from the range [first,last) .

In case of a tie, the point with the largest y -coordinate is taken.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . In fact, only the members Less_xy_2 and less_xy_2_object() are used. ForwardIterator must have Traits::Point_2 as value type.

See also

CGAL::left_vertex_2()

CGAL::top_vertex_2()

CGAL::bottom_vertex_2() CGAL::Polygon_2

#include <CGAL/Polygon_2_algorithms.h>

Returns an iterator to the topmost point from the range [first,last) .

In case of a tie, the point with the largest x -coordinate is taken.

Template Parameters

Traitsis a model of the concept PolygonTraits_2 . Only the members Less_yx_2 and less_yx_2_object() are used. ForwardIterator must have Traits::Point_2 as value type.

See also

CGAL::left_vertex_2()

CGAL::right_vertex_2()

CGAL::bottom_vertex_2() CGAL::Polygon_2