Convex Components

Convex Components of a Polygon

    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 non-trivial 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

    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 2-D 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