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`` 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

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.

Data Types for 2-D Geometry

Linear Lists

Convex Hulls

Parameterized Graphs

Writing Kernel Independent Code

Geometry Algorithms

Geometry

Graphs and Related Data Types

GeoWin

Number Types