Convex Components
Convex Components of a Polygon
The function
edge CONVEX_COMPONENTS(const polygon& P, GRAPH<POINT, SEGMENT>& G,
list<edge>& inner_edges,list<edge>& boundary)
decomposes the interior of polygon P into convex parts.
The decomposition is represented by a parameterized
GRAPH <POINT, SEGMENT> G . The
representation is the same as for Triangulations
. A set of points C is called convex if
for any two points p and q in C
the entire segment is contained in C . All inner edges
of the decomposition are returned in inner_edges .
boundary_edges
contains the edges of the boundary of P .

Remark:The reversals of boundary edges will be stored in
inner_edges .
The function returns an edge of the convex
hull if P is simple and nontrivial and nil
otherwise.
On the right there is a screenshot of the example
of how to compute convex components for a polygon.


Example of
how to compute convex components for a polygon
We use the notation POINT (SEGMENT) to indicate that the
algorithm works both for points (segments) and rat_points
(rat_segments) . See also Writing
Kernel Independent Code.
Convex Components of a Generalized Polygon
The function
edge CONVEX_COMPONENTS(const gen_polygon& GP, GRAPH<POINT,SEGMENT>& G,
list<edge>& inner_edges, list<edge>& boundary,
list<edge>& hole_edges)
decomposes the interior of the generalized polygon GP into
convex parts. Additionally to the function for polygons, the list hole_edges
contains the edges of every clockwise oriented boundary cycle of GP .
Remark: The reversals of boundary and hole edges will be stored
in inner_edges .
Running Time
The expected running time O(nlogn) for all inputs.

See also:
Data Types for 2D Geometry
Linear Lists
Convex Hulls
Triangulations
Parameterized Graphs
Writing Kernel Independent Code
Geometry Algorithms
Geometry
Graphs and Related Data Types
GeoWin
Number Types
Manual Entries
Manual
Page of Geometry Algorithms
