|
Verification of Geometric StructuresWhat 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
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 FunctionsTo use a function that checks the property of a geometric graph, use#include <LEDA/templates/geo_check.t> Counter-Clockwise Ordered Adjacency ListsThe functionsbool 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 FacesA set of pointsC 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 TriangulationsA 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 TriangulationsThe functionbool 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 DiagramsThe functionbool 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 DiagramsThe functionbool 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:Writing Kernel Independent Code Manual Entries |