next up previous contents index
Next: Point Location in Triangulations ( Up: Advanced Data Types for Previous: Two-Dimensional Dictionaries ( d2_dictionary   Contents   Index


Point Sets and Delaunay Triangulations ( POINT_SET )

Definition

There are three instantiations of POINT_SET: point_set (floating point kernel), rat_point_set (rational kernel) and real_point_set (real kernel). The respective header file name corresponds to the type name (with ``.h'' appended).

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, \mathit{T}.\mathit{face{\_}cycle{\_}succ}(\mathit{e}), \mathit{T}.\mathit{fa...
..._}cycle{\_}succ}(\mathit{T}.\mathit{face{\_}cycle{\_}succ}(\mathit{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/geo/generic/POINT_SET.h >

Creation

POINT_SET T creates an empty POINT_SET T.

POINT_SET T(const 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(const GRAPH<POINT,int>& G)
    initializes T with a copy of G.
Precondition Is_Delaunay(G) is true.

Operations

void T.init(const 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.

bool T.get_bounding_box(POINT& lower_left, POINT& upper_right)
    returns the lower left and upper right corner of the bounding box of T. The operation returns true, if T is not empty, false otherwise.

list<node> T.get_convex_hull() returns the convex hull of T.

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, edge loc_start = NULL)
    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. The optional second argument is an edge of T, where the locate operation starts searching.

edge T.locate(POINT p, const list<edge>& loc_start)
    returns locate(p,e) with e in loc_start. If loc_start is empty, we return locate(p, NULL). The operation tries to choose a good starting edge for the locate operation from loc_start. Precondition All edges in loc_start must be edges of T.

node T.lookup(POINT p, edge loc_start = NULL)
    if T contains a node v with pos(v) = p the result is v otherwise the result is nil. The optional second argument is an edge of T, where the locate operation starts searching p.

node T.lookup(POINT p, const list<edge>& loc_start)
    returns lookup(p,e) with e in loc_start. If loc_start is empty, we return lookup(p, NULL). The operation tries to choose a good starting edge for the lookup operation from loc_start. Precondition All edges in loc_start must be edges of T.

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(const 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, const 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(const POINT& a, const POINT& b, const 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_parallelogram(const POINT& a, const POINT& b, const POINT& c)
    returns the list of all nodes contained in the closure of the parallelogram (a, b, c, d ) with d = a + (c - b).
Precondition a, b, and c must not be collinear. This is a non-const operation.

list<node> T.range_search(const POINT& a, const 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.

list<edge> T.relative_neighborhood_graph()
    returns the list of edges of T that comprise a relative neighborhood graph 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)(const POINT& ))
    calls draw_node(pos(v)) for every node v of T.

void T.draw_edge(edge e, void (*draw_diagram_edge)(const POINT& , const POINT& ), void (*draw_triang_edge) (const POINT& , const POINT& ), void (*draw_hull_dart) (const POINT& , const 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)(const POINT& , const POINT& ), void (*draw_triang_edge) (const POINT& , const POINT& ), void (*draw_hull_dart) (const POINT& , const POINT& ))
    calls the corresponding function for all edges of T.

void T.draw_edges(const list<edge>& L, void (*draw_edge)(const POINT& , const POINT& ))
    calls draw_edge(pos_source(e),pos_target(e) for every edge e $ \in$ L.

void T.draw_voro_edges(void (*draw_edge)(const POINT& , const POINT& ), void (*draw_ray) (const POINT& , const POINT& ))
    calls draw_edge and draw_ray for the edges of the Voronoi diagram.

void T.draw_hull(void (*draw_poly)(const list<POINT>& ))
    calls draw_poly with the list of vertices of the convex hull.

void T.draw_voro(const GRAPH<CIRCLE,POINT>& , void (*draw_node)(const POINT& ), void (*draw_edge)(const POINT& , const POINT& ), void (*draw_ray) (const POINT& , const 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".


next up previous contents index
Next: Point Location in Triangulations ( Up: Advanced Data Types for Previous: Two-Dimensional Dictionaries ( d2_dictionary   Contents   Index
root 2008-01-09