| Home | Libraries | People | FAQ | More

#### Polygon Concept

###### Description

The Polygon Concept describes the requirements for a polygon type. All algorithms in Boost.Geometry will check any geometry arguments against the concept requirements.

A polygon is A polygon is a planar surface defined by one exterior boundary and zero or more interior boundaries (OGC Simple Feature Specification).

So the definition of a Boost.Geometry polygon differs a bit from e.g. Wiki, where a polygon does not have holes. A polygon of Boost.Geometry is a polygon with or without holes. (A polygon without holes is a helper geometry within Boost.Geometry, and referred to as a ring.)

###### Concept Definition

The Polygon Concept is defined as following:

- there must be a specialization of `traits::tag` defining `polygon_tag` as type
- there must be a specialization of `traits::ring_type` defining the type of its exterior ring and interior rings as type
- this type defined by `ring_type` must fulfill the Ring Concept
- there must be a specialization of `traits::interior_type` defining the type of the collection of its interior rings as type; this collection itself must fulfill a Boost.Range Random Access Range Concept
- there must be a specialization of `traits::exterior_ring` with two functions named `get`, returning the exterior ring, one being const, the other being non const
- there must be a specialization of `traits::interior_rings` with two functions named `get`, returning the interior rings, one being const, the other being non const

###### Rules

Besides the Concepts, which are checks on compile-time, there are some other rules that valid polygons must fulfill. This follows the opengeospatial rules (see link above).

- Polygons are simple geometric objects (See also wiki but holes are allowed in Boost.Geometry polygons).
- If the polygons underlying `ring_type` is defined as clockwise, the exterior ring must have the clockwise orientation, and any interior ring must be counter clockwise. If the `ring_type` is defined counter clockwise, it is vice versa.
- If the polygons underlying `ring_type` is defined as closed, all rings must be closed: the first point must be spatially equal to the last point.
- The interior is a connected point set.
- There should be no self intersections, but self tangencies (between exterior/interior rings) are allowed (as long as the interior is a connected point set.
- There should be no cut lines, spikes or punctures.
- The interior rings should be located within the exterior ring. Interior rings may not be located within each other.

The algorithms such as intersection, area, centroid, union, etc. do not check validity. There will be an algorithm is_valid which checks for validity against these rules, at runtime, and which can be called (by the library user) before.

If the input is invalid, the output might be invalid too. For example: if a polygon which should be closed is not closed, the area will be incorrect.

###### Available Models

- polygon
- a Boost.Polygon polygon_with_holes_data (requires `#include boost/geometry/geometries/adapted/boost_polygon/polygon.hpp>`)