Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Verification of Geometric Structures

## Verification of Geometric Structures

### What is a Geometric Graph?

In this section we present procedures to verify properties of geometric graphs . A geometric graph is a straight line embedded map. Every node is mapped to a point in the plane and every edge is mapped to a line segment connecting its endpoints.
We use `geo_graph` as a template parameter for geometric graphs. An instantiation of `geo_graph` must provide a function
`	VECTOR edge_vector(const geo_graph& G, const edge& e)`
that returns a vector from the source to the target of `e`.
We use two instantiations of `geo_graph`
We use the notation `POINT (CIRCLE)` to indicate that the algorithm works both for `points` (`circles`) and `rat_points` (`rat_circles`). See also Writing Kernel Independent Code.

### Usage of Check Functions

To use a function that checks the property of a geometric graph, use
`	#include <LEDA/templates/geo_check.t>`

The functions
```	bool Is_CCW_Ordered(const geo_graph& G)
bool Is_CCW_Weakly_Ordered(const geo_graph& G)```
return `true`, if for all nodes `v` of `G` the neighbors of `v` are in increasing, respectively non-decreasing, counter-clockwise order around `v`, and the functions
```	bool Is_CCW_Ordered_Plane_Map(const geo_graph& G)
bool Is_CCW_Weakly_Ordered_Plane_Map(const geo_graph& G)```
return `true`, if, in addition, `G` is a plane map.
The function
`	void SORT_EDGES(geo_graph& G)`
reorders the adjacency lists such that for every node `v` of `G` the edges in ``` A(v)``` are in non-decreasing counter-clockwise order.

### Convex Faces

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`. Consider any face cycle f of a geometric graph `G`; f defines a closed polygonal chain `C` in the plane. We want to know whether the polygonal chain is the boundary of a convex region.
`C` is called weakly convex if it is simple, and convex if, additionally, any two consecutive edges of `C` do not have the same direction.
In a convex subdivision, e.g., a triangulation, all face cycles of all bounded faces form convex polygonal chains and the unbounded face forms a weakly convex polygonal chain.

The functions

```	bool Is_CCW_Convex_Face_Cycle(const geo_graph& G, edge e)
bool Is_CCW_Weakly_Convex_Face_Cycle(const geo_graph& G, edge e)
bool Is_CW_Convex_Face_Cycle(const geo_graph& G, edge e)
bool Is_CW_Weakly_Convex_Face_Cycle(const geo_graph& G, edge e)```
return `true`, if the face cycle of `G` containing e has the stated property, that is, counter-clockwise, respectively clockwise, (weakly) convex.

### Convex Subdivisions and Triangulations

A set of points` C` is called convex if for any two pointsp and q in `C` the entire segmentis contained in `C`. A geometric graph `G` is a convex subdivision, if `G` is a plane map and if the positions assigned to the nodes define a straight line embedding of `G` in which all bounded faces are strictly convex and in which the unbounded face is weakly convex.

The functions

```	bool Is_Convex_Subdivision(const geo_graph& G)
bool Is_Triangulation(const geo_graph& G)```
return `true`, if `G` is a convex planar subdivision, respectively a triangulation. A triangulation is a convex planar subdivision in which every bounded face is a triangle.

### Delaunay Triangulations

The function
```
bool Is_Delaunay_Triangulation(const GRAPH<POINT,SEGMENT>& G,
delaunay_voronoi_kind kind)```
checks whether `G` is a Delaunay Triangulation of the points associated with its nodes. The flag kind allows to choose between the nearest (=NEAREST) and furthest (=FURTHEST) site version.

### Delaunay Diagrams

The function
```
bool Is_Delaunay_Diagram(const GRAPH<POINT,SEGMENT>& G,
delaunay_voronoi_kind kind)```
checks whether `G` is a Delaunay Diagram diagram of the points associated with its nodes. The flag kind allows to choose between the nearest (=NEAREST) and furthest (=FURTHEST) site version.

### Voronoi Diagrams

The function
```
bool Is_Voronoi_Diagram(const GRAPH<CIRCLE,POINT>& G,
delaunay_voronoi_kind kind)```
checks whether `G` is a Voronoi Diagram of the points associated with its nodes. The flag kind allows to choose between the nearest (=NEAREST) and furthest (=FURTHEST) site version.

Data Types for 2-D Geometry

Graphs

Parameterized Graphs

Triangulations

Delaunay Triangulations

Delaunay Diagrams

Voronoi Diagrams

Writing Kernel Independent Code

Geometry Algorithms

Geometry

Graphs and Related Data Types

GeoWin

Number Types

### Manual Entries

Manual Page of Geometry Algorithms