Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Convex Components

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 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 Convex Components

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

Linear Lists

Convex Hulls


Parameterized Graphs

Writing Kernel Independent Code

Geometry Algorithms


Graphs and Related Data Types


Number Types

Manual Entries

Manual Page of Geometry Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH