Delaunay Triangulations (delaunay_triang)

Definition

An instance T of data type delaunay_triang is a planar embedded bidirected graph (map) representing the Delaunay Triangulation of its vertex set. The position of a vertex v is given by T.pos(v) and we use $S = \{ T.pos(v) \mid v \in T \}$ to denote the underlying point set. Each face of T (except for the outer face) is a triangle whose circumscribing circle does not contain any point of S in its interior. For every edge e, the sequence e, T.face_cycle_succ(e), T.face_cycle_succ(T.face_cycle_succ(e)),... traces the boundary of the face to the left of e. The edges of the outer face of T form the convex hull of S; the trace of the convex hull is clockwise. The subgraph obtained from T by removing all diagonals of co-circular quadrilaterals is called the Delaunay Diagram of S.

delaunay_triang provides all constant graph operations, e.g., T.reversal(e) returns the reversal of edge e, T.all_edges() returns the list of all edges of T, and forall_edges(e,T) iterates over all edges of T. In addition, delaunay_triang provides operations for inserting and deleting points, point location, nearest neighbor searches, and navigation in both the triangulation and the diagram.

delaunay_triangs are essentially objects of type GRAPH<POINT,int>, where the node information is the position of the node and the edge information is irrelevant. For a graph G of type GRAPH<POINT,int> the function Is_Delaunay(G) tests whether G is a Delaunay triangulation of its vertices.

The data type delaunay_triang is illustrated by delaunay_demo in the LEDA demo directory.

Creation

delaunay_triang	T;	creates an empty Delaunay Triangulation T.
delaunay_triang	T(list<POINT> S);	creates a Delaunay Triangulation T of the points in S. If S contains multiple occurrences of points only the last occurence of each point is retained.
delaunay_triang	T(GRAPH<POINT,int> G);	initializes T with a copy of G. Precondition: Is_Delaunay(G) is true.

Operations

void	T.init(list<POINT> L)	makes T a Delaunay Triangulation of the points in S.
POINT	T.pos(node v)	returns the position of node v.
POINT	T.pos_source(edge e)	returns the position of source(e).
POINT	T.pos_target(edge e)	returns the position of target(e).
SEGMENT	T.seg(edge e)	returns the line segment corresponding to edge e (SEGMENT(T.pos_source(e),T.pos_target(e))).
LINE	T.supporting_line(edge e)	returns the supporting line of edge e (LINE(T.pos_source(e),T.pos_target(e))).
int	T.orientation(edge e, POINT p)
		returns orientation(T.seg(e),p).
int	T.dim()	returns -1 if S is empty, returns 0 if S consists of only one point, returns 1 if S consists of at least two points and all points in S are collinear, and returns 2 otherwise.
list<POINT>	T.points()	returns S.
node	T.insert(POINT p)	inserts point p into T and returns the corresponding node. More precisely, if there is already a node v in T positioned at p (i.e., pos(v) is equal to p) then pos(v) is changed to p (i.e., pos(v) is made identical to p) and if there is no such node then a new node v with pos(v) = p is added to T. In either case, v is returned.
void	T.del(node v)	removes node v, i.e., makes T a Delaunay triangulation of $S-\{pos(v)\}$.
edge	T.locate(POINT p)	returns an edge e of T that contains p or that borders the face that contains p. In the former case, the edge is either a hull edge or an edge in the interior of the triangulation (i.e., neither the edge nor its reversal is a hull edge). In the latter case we have orientation(e,p) > 0 except if all points of T are collinear and p lies on the induced line. In this case target(e) is visible from p. The function returns nil if T has no edge.
node	T.lookup(POINT p)	if T contains a node v with pos(v) = p the result is v otherwise the result is nil.
node	T.nearest_neighbor(POINT p)
		computes a node v of T that is closest to p, i.e., $dist(p,pos(v)) = \min\{\ dist(p,pos(u)) \mid u\in T\ \}$.
list<node>	T.range_search(CIRCLE C)	returns the list of all nodes contained in the closure of disk C. Precondition: C must be a proper circle (not a straight line).
list<node>	T.range_search(POINT a, POINT b, POINT c)
		returns the list of all nodes contained in the closure of the triangle (a,b,c). Precondition: a, b, and c must not be collinear.
list<node>	T.range_search(POINT a, POINT b)
		returns the list of all nodes contained in the closure of the rectangle with diagonal (a,b).
edge	T.get_hull_edge()	returns an edge of the outer face of T (i.e., an edge of the convex hull).
bool	T.is_hull_edge(edge e)	decides whether e belongs to the convex hull of T.
bool	T.is_diagram_edge(edge e)	decides whether e is an edge of the Delaunay diagram of T.
edge	T.d_face_cycle_succ(edge e)
		returns face cycle successor of e in the Delaunay diagram of T. Precondition: e belongs to the Delaunay diagram.
edge	T.d_face_cycle_pred(edge e)
		returns the face cycle predecessor of e in the Delaunay diagram of T. Precondition: e belongs to the Delaunay diagram.
void	T.compute_voronoi(GRAPH<CIRCLE,POINT>& V)
		computes the corresponding Voronoi diagram V. Each node of VD is labeled with its defining circle. Each edge is labeled with the site lying in the face to its left.
list<edge>	T.minimum_spanning_tree()	returns the list of edges of T that comprise a minimum spanning tree of S.
bool	T.empty()	decides whether T is empty.
void	T.clear()	makes T empty.

Drawing Routines

void	T.draw_nodes(void (*draw_node)(POINT ))
		draws all nodes of T by calling draw_node(pos(v)) for every node v.
void	T.draw_edge(edge e, void (*draw_diagram_edge)(POINT, POINT ), void (*draw_triang_edge) (POINT, POINT ), void (*draw_hull_edge) (POINT, POINT ))
		draws edges e of T by calling draw_diagram_edge(pos_source(e),pos_target(e) if e is a diagram edge, draw_hull_edge(pos_source(e),pos_target(e) if e is a hull edge and draw_triang_edge(pos_source(e),pos_target(e) if e is a non-diagram edge.
void	T.draw_edges(void (*draw_diagram_edge)(POINT, POINT ), void (*draw_triang_edge) (POINT, POINT ), void (*draw_hull_edge) (POINT, POINT ))
		draws all edges of T by calling the corresponding draw function.
void	T.draw_edges(list<edge> L, void (*draw_edge)(POINT, POINT ))
		draws all edges in L by calling draw_edge(pos_source(e),pos_target(e) for every edge e in L.
void	T.draw_voro_edges(void (*draw_edge)(POINT, POINT ), void (*draw_ray) (POINT, POINT ))
		draws the edges of the Vorononoi Diagram of T by calling ...
void	T.draw_hull(void (*draw_poly)(list<POINT> ))
		draws the convex hull of T by calling ...

Implementation

The main ingredients for the implementation are Delaunay flipping, segment walking, and plane sweep.

The constructor delaunay_triang(list<POINT> S) first constructs a triangulation of S by sweeping and then makes the triangulation Delaunay by a sequence of Delaunay flips.

Locate walks through the triangulation along the segment from some fixed point of T to the query point. Insert first locates the point, then updates the triangulation locally, and finally performs flips to reestablish the Delaunay property. Delete deletes the node, retriangulates the resulting face, and then performs flips. Nearest neighbor searching, circular range queries, and triangular range queries insert the query point into the triangulation, then perform an appropriate graph search on the triangulation, and finally remove the query point.

All algorithms show good expected behaviour.

For details we refer the reader to the LEDA implementation report "Delaunay triangulations".