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>

Counter-Clockwise Ordered Adjacency Lists

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.

See also:

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


Algorithmic Solutions Software GmbH