Point Sets (Dynamic Delaunay Triangulations)
The class POINT_SET maintains a set of points
in the plane under insertions and deletions. A POINT_SET is
maintained as a Delaunay
Triangulation of its elements and hence the class may equally well
be called Dynamic Delaunay Triangulations.
Remark: We use the notation POINT_SET to indicate that there is
a version point_set in the floating point kernel and a version
rat_point_set in the rational kernel of LEDA.
Example
of How to Use POINT_SET
Example of
Point Location and Drawing Operations
Representation of a Point Set
A POINT_SET is maintained as a Delaunay
Triangulation and, therefore, has the same representation by a parameterized
graph GRAPH<POINT,int> G:
G is a straight line embedded plane map. It corresponds
to a Delaunay Triangulation T of the set of points L
as follows:
- Nodes of
G are in one-to-one correspondence with the
points in L
G is bidirected - For each node
v of G the list A(v)
of edges out of v is ordered cyclically. This cyclic ordering
agrees with the counter-clockwise ordering of the edges incident to
the point in L corresponding to v.
- Each edge
e of G has an integer label that
gives information about the edge.
Strengths of POINT_SET
- nearest neighbor queries
- point location queries
- circular, triangular, and rectangular range queries
- operations lookup, insert, del and many more
- functions that support drawing of Delaunay triangulations, Delaunay
Diagrams, and Voronoi Diagrams
- all graph operations and all graph algorithms available
Remark: Only graph operations and graph algorithms that do not
modify the graph should be used as other may destroy the additional invariants
imposed by POINT_SET.
|
See also:
Data Types for 2D Geometry
Delaunay Triangulations
Parameterized Graphs
Delaunay Diagrams
Convex Hulls
Graphs and Related Data Types
Graph Algorithms
Geometry
Geometry Algorithms
GeoWin
Manual Entries:
Manual
Page Point Sets
|