Point Sets and Delaunay Triangulations ( POINT_SET )

Definition

There are two instantiations of POINT_SET. The instantiation with the rational kernel is called rat_point_set and requires inclusion of rat_point_set.h and the instantiation with the floating point kernel is called point_set and requires inclusion of point_set.h.

An instance T of data type POINT_SET 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) | 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, \HTML{I}{T}.\HTML{I}{face{\_}cycle{\_}succ}(\HTML{I}{e}), \HTML{I}{T}.\HTML{... ...cycle{\_}succ}(\HTML{I}{T}.\HTML{I}{face{\_}cycle{\_}succ}(\HTML{I}{e})),\ldots$

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.

POINT_SET 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, POINT_SET provides operations for inserting and deleting points, point location, nearest neighbor searches, and navigation in both the triangulation and the diagram.

POINT_SETs 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 POINT_SET is illustrated by the point_set_demo in the LEDA demo directory.

Be aware that the nearest neighbor queries for a point (not for a node) and the range search queries for circles, triangles, and rectangles are non-const operations and modify the underlying graph. The set of nodes and edges is not changed; however, it is not guaranteed that the underlying Delaunay triangulation is unchanged.

#include < LEDA/generic/POINT _SET.h >

Creation

POINT_SET	T	creates an empty POINT_SET T.
POINT_SET	T(list<POINT> S)	creates a POINT_SET T of the points in S. If S contains multiple occurrences of points only the last occurrence of each point is retained.
POINT_SET	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 POINT_SET for 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.
edge	T.get_hull_dart()	returns a dart of the outer face of T (i.e., a dart of the convex hull).
edge	T.get_hull_edge()	as above.
bool	T.is_hull_dart(edge e)	returns true if e is a dart of the convex hull of T, i.e., a dart on the face cycle of the outer face.
bool	T.is_hull_edge(edge e)	as above.
bool	T.is_diagram_dart(edge e)	returns true if e is a dart of the Delaunay diagram, i.e., either a dart on the convex hull or a dart where the incident triangles have distinct circumcircles.
bool	T.is_diagram_edge(edge e)	as above.
edge	T.d_face_cycle_succ(edge e)
		returns the 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.
bool	T.empty()	decides whether T is empty.
void	T.clear()	makes T empty.
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, a hull dart is returned if p lies on the boundary of the convex hull. In the latter case we have T.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.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 the node v, i.e., makes T a Delaunay triangulation for S $\setminus$ {   pos(v)   }.
void	T.del(POINT p)	removes the node p, i.e., makes T a Delaunay triangulation for S $\setminus$ p.
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)) | u in T}. This is a non-const operation.
node	T.nearest_neighbor(node w)
		computes a node v of T that is closest to p = T[w], i.e., dist(p, pos(v)) = min{dist(p, pos(u)) | u in T}.
list<node>	T.nearest_neighbors(POINT p, int k)
		returns the k nearest neighbors of p, i.e., a list of the min(k,| S|) nodes of T closest to p. The list is ordered by distance from p. This is a non-const operation.
list<node>	T.nearest_neighbors(node w, int k)
		returns the k nearest neighbors of p = T[w], i.e., a list of the min(k,| S|) nodes of T closest to p. The list is ordered by distance from p.
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). This is a non-const operation.
list<node>	T.range_search(node v, POINT p)
		returns the list of all nodes contained in the closure of disk C with center pos[v] and having p in its boundary.
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. This is a non-const operation.
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). This is a non-const operation.
list<edge>	T.minimum_spanning_tree()	returns the list of edges of T that comprise a minimum spanning tree of S.
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.

Drawing Routines

The functions in this section were designed to support the drawing of Delaunay triangulations and Voronoi diagrams.

void	T.draw_nodes(void (*draw_node)(POINT ))
		calls draw_node(pos(v)) for every node v of T.
void	T.draw_edge(edge e, void (*draw_diagram_edge)(POINT, POINT ), void (*draw_triang_edge) (POINT, POINT ), void (*draw_hull_dart) (POINT, POINT ))
		calls draw_diagram_edge(pos_source(e),pos_target(e) if e is a diagram dart, draw_hull_dart(pos_source(e),pos_target(e) if e is a hull dart, 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_dart) (POINT, POINT ))
		calls the corresponding function for all edges of T.
void	T.draw_edges(list<edge> L, void (*draw_edge)(POINT, POINT ))
		calls 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 ))
		calls draw_edge and draw_ray for the edges of the Voronoi diagram.
void	T.draw_hull(void (*draw_poly)(list<POINT> ))
		calls draw_poly with the list of vertices of the convex hull.
void	T.draw_voro(GRAPH<CIRCLE,POINT>, void (*draw_node)(POINT ), void (*draw_edge)(POINT, POINT ), void (*draw_ray) (POINT, POINT ))
		calls ...

Implementation

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

The constructor POINT_SET(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 behavior.

For details we refer the reader to the LEDA implementation report "Point Sets and Dynamic Delaunay Triangulations".