1[/============================================================================ 2 Boost.Geometry (aka GGL, Generic Geometry Library) 3 4 Copyright (c) 2009-2012 Mateusz Loskot, London, UK. 5 Copyright (c) 2009-2012 Barend Gehrels, Amsterdam, the Netherlands. 6 Copyright (c) 2009-2012 Bruno Lalande, Paris, France. 7 8 Use, modification and distribution is subject to the Boost Software License, 9 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 10 http://www.boost.org/LICENSE_1_0.txt) 11=============================================================================/] 12 13[section:concept_polygon Polygon Concept] 14 15[heading Description] 16[concept Polygon..polygon] 17 18A polygon is ['A polygon is a planar surface defined by one exterior boundary and zero or more interior boundaries] 19(__ogc_sf__). 20 21So the definition of a Boost.Geometry polygon differs a bit from e.g. Wiki, where a polygon does not have holes. A 22polygon of Boost.Geometry is a polygon with or without holes. 23['(A polygon without holes is a ['helper geometry] within Boost.Geometry, and referred to as a ring.)] 24 25[heading Concept Definition] 26 27The Polygon Concept is defined as following: 28 29* there must be a specialization of `traits::tag` defining `polygon_tag` as type 30* there must be a specialization of `traits::ring_type` defining the type of its exterior ring and interior rings as type 31* this type defined by `ring_type` must fulfill the [link geometry.reference.concepts.concept_ring Ring Concept] 32* there must be a specialization of `traits::interior_type` defining the type of the collection of its interior rings as type; 33 this collection itself must fulfill a Boost.Range Random Access Range Concept 34* 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 35* 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 36 37[heading Rules] 38 39Besides the Concepts, which are checks on compile-time, there are some other 40rules that valid polygons must fulfill. This follows the opengeospatial rules (see link 41above). 42 43* Polygons are simple geometric objects (See also [@http://en.wikipedia.org/wiki/Simple_polygon wiki] 44 but holes are allowed in __boost_geometry__ polygons). 45* If the polygons underlying `ring_type` is defined as clockwise, the exterior 46 ring must have the clockwise orientation, and any interior ring must be 47 reversed w.r.t. the defined orientation (so: counter clockwise for clockwise exterior rings). 48 If the `ring_type` is defined counter clockwise, it is vice versa. 49* If the polygons underlying `ring_type` is defined as closed, all rings must be 50 closed: the first point must be spatially equal to the last point. 51* The interior is a connected point set. 52* There should be no self intersections, but self tangencies (between 53 exterior/interior rings) are allowed (as long as the interior is a connected 54 point set. 55* There should be no cut lines, spikes or punctures. 56* The interior rings should be located within the exterior ring. Interior rings 57 may not be located within each other. 58 59The algorithms such as intersection, area, centroid, union, etc. do not check 60validity. There will be an algorithm is_valid which checks for 61validity against these rules, at runtime, and which can be called (by the library 62user) before. 63 64If the input is invalid, the output might be invalid too. For example: if a polygon 65which should be closed is not closed, the area will be incorrect. 66 67[heading Available Models] 68* [link geometry.reference.models.model_polygon polygon] 69* a Boost.Polygon polygon_with_holes_data (requires `#include boost/geometry/geometries/adapted/boost_polygon/polygon.hpp>`) 70 71[endsect] 72