CGAL 5.6.3 - 2D Polygons

Loading...
Searching...
No Matches
User Manual

Authors
  Geert-Jan Giezeman and Wieger Wesselink

# Introduction

A polygon is a closed chain of edges. Several algorithms are available for polygons. For some of those algorithms, it is necessary that the polygon is simple. A polygon is simple if edges don't intersect, except consecutive edges, which intersect in their common vertex.

The following algorithms are available:

- find the leftmost, rightmost, topmost and bottommost vertex.
- compute the (signed) area.
- check if a polygon is simple.
- check if a polygon is convex.
- find the orientation (clockwise or counterclockwise)
- check if a point lies inside a polygon.

All those operations take two forward iterators as parameters in order to describe the polygon. These parameters have a point type as value type.

The type `Polygon_2` can be used to represent polygons. Polygons are dynamic. Vertices can be modified, inserted and erased. They provide the algorithms described above as member functions. Moreover, they provide ways of iterating over the vertices and edges.

The `Polygon_2` class is a wrapper around a container of points, but little more. Especially, computed values are not cached. That is, when the `Polygon_2::is_simple()` member function is called twice or more, the result is computed each time anew.

# Examples

## The Polygon Class

The following example creates a polygon and illustrates the usage of some member functions.

File Polygon/Polygon.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;
using std::cout; using std::endl;
int main()
{
Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
Polygon_2 pgn(points, points+4);
// check if the polygon is simple.
cout << "The polygon is " <<
(pgn.is_simple() ? "" : "not ") << "simple." << endl;
// check if the polygon is convex
cout << "The polygon is " <<
(pgn.is_convex() ? "" : "not ") << "convex." << endl;
return 0;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::Polygon_2
The class Polygon_2 implements polygons.
Definition: Polygon_2.h:64

Figure 15.1 A polygon and some points

## Algorithms Operating on Sequences of Points

The following example creates a polygon and illustrates the usage of some global functions that operate on sequences of points.

File Polygon/polygon_algorithms.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
using std::cout; using std::endl;
void check_inside(Point pt, Point *pgn_begin, Point *pgn_end, K traits)
{
cout << "The point " << pt;
switch(CGAL::bounded_side_2(pgn_begin, pgn_end,pt, traits)) {
case CGAL::ON_BOUNDED_SIDE :
cout << " is inside the polygon.\n";
break;
case CGAL::ON_BOUNDARY:
cout << " is on the polygon boundary.\n";
break;
case CGAL::ON_UNBOUNDED_SIDE:
cout << " is outside the polygon.\n";
break;
}
}
int main()
{
Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
// check if the polygon is simple.
cout << "The polygon is "
<< (CGAL::is_simple_2(points, points+4, K()) ? "" : "not ")
<< "simple." << endl;
check_inside(Point(0.5, 0.5), points, points+4, K());
check_inside(Point(1.5, 2.5), points, points+4, K());
check_inside(Point(2.5, 0), points, points+4, K());
return 0;
}
CGAL::bounded_side_2
Bounded_side bounded_side_2(ForwardIterator first, ForwardIterator last, const Point &point, const PolygonTraits &traits)
Computes if a point lies inside a polygon.
CGAL::is_simple_2
bool is_simple_2(ForwardIterator first, ForwardIterator last, const PolygonTraits &traits)
Checks if the polygon defined by the iterator range [first,last) is simple, that is,...
CGAL::ON_BOUNDARY
ON_BOUNDARY
CGAL::ON_UNBOUNDED_SIDE
ON_UNBOUNDED_SIDE
CGAL::ON_BOUNDED_SIDE
ON_BOUNDED_SIDE

## Polygons in 3D Space

Sometimes it is useful to run a 2D algorithm on 3D data. Polygons may be contours of a 3D object, where the contours are organized in parallel slices, generated by segmentation of image data from a scanner.

In order to avoid an explicit projection on the `xy` plane, one can use the traits class `Projection_traits_xy_3` which is part of the 2D and 3D Linear Geometric Kernel.

File Polygon/projected_polygon.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Projection_traits_yz_3.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point_3;
int main()
{
Point_3 points[4] = { Point_3(0,1,1), Point_3(0,2,1), Point_3(0,2,2), Point_3(0,1,2) };
bool b = CGAL::is_simple_2(points,
points+4,
CGAL::Projection_traits_yz_3<K>());
if (!b){
std::cerr << "Error polygon is not simple" << std::endl;
return 1;
}
return 0;
}
CGAL::Projection_traits_yz_3

## Iterating over Vertices and Edges

The polygon class provides member functions such as `Polygon_2::vertices_begin()` and `Polygon_2::vertices_end()` to iterate over the vertices. It additionally provides a member function `Polygon_2::vertices()` that returns a range, mainly to be used with modern `for` loops. The same holds for edges and for the holes of the class `Polygon_with_holes_2`.

File Polygon/ranges.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;
int main()
{
// create a polygon and put some points in it
Polygon_2 p;
p.push_back(Point_2(0,0));
p.push_back(Point_2(4,0));
p.push_back(Point_2(4,4));
for(const Point_2& p : p.vertices()){
std::cout << p << std::endl;
}
// As the range is not light weight, we have to use a reference
const Polygon_2::Vertices& range = p.vertices();
for(auto it = range.begin(); it!= range.end(); ++it){
std::cout << *it << std::endl;
}
for(const Segment_2& e : p.edges()){
std::cout << e << std::endl;
}
return EXIT_SUCCESS;
}
CGAL::Polygon_2::push_back
void push_back(const Point_2 &x)
Has the same semantics as p.insert(p.vertices_end(), q).
Definition: Polygon_2.h:233
CGAL::Polygon_2::Vertices
Container Vertices
a range type to iterate over the vertices
Definition: Polygon_2.h:123

## Draw a Polygon

A polygon can be visualized by calling the CGAL::draw<P>() function as shown in the following example. This function opens a new window showing the given polygon. A call to this function is blocking, that is the program continues as soon as the user closes the window (a version exists for polygon with holes, cf. CGAL::draw<PH>() ).

File Polygon/draw_polygon.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/draw_polygon_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Point_2<K> Point;
int main()
{
// create a polygon and put some points in it
Polygon_2 p;
p.push_back(Point(0,0));
p.push_back(Point(4,0));
p.push_back(Point(4,4));
p.push_back(Point(2,2));
p.push_back(Point(0,4));
CGAL::draw(p);
return EXIT_SUCCESS;
}
CGAL::Point_2
CGAL::draw
void draw(const P &ap)
opens a new window and draws ap, an instance of the CGAL::Polygon_2 class.

This function requires `CGAL_Qt5`, and is only available if the macro `CGAL_USE_BASIC_VIEWER` is defined. Linking with the cmake target `CGAL::CGAL_Basic_viewer` will link with `CGAL_Qt5` and add the definition `CGAL_USE_BASIC_VIEWER`.

Figure 15.2 Result of the run of the draw_polygon program. A window shows the polygon and allows to navigate through the scene.