Crate spade [−] [src]

Spade

Spade (SPAtial DatastructurEs, obviously!) implements a few nifty datastructures optimized for spatial access operations. The first major datastructure is an n-dimensional r*-tree (wikipedia) for efficient nearest-neighbor and point lookup queries. The second datastructures implements a 2D delaunay triangulation (wikipedia) backed by an r-tree for fast nearest neighbor lookup. The triangulation also implements natural neighbor interpolation (wikipedia) which offers a smooth interpolation in a delaunay triangulation. All classes are purely written in (safe) rust, the package currently supports vectors from the nalgebra and cgmath crates.

Features

An n-dimensional R-Tree: RTree
A 2D delaunay triangulation: DelaunayTriangulation
- Supports integral and floating point vectors as input
- Uses exact predicates to avoid floating point rounding issues, see: FloatKernel
- Natural neighbor interpolation

Modules

primitives	Contains some useful primitives that can be inserted into r-trees.
testutils

Structs

AdaptiveIntKernel	Delaunay kernel for integral coordinates with a larger value range.
AllEdgesIterator	An iterator over all edges contained in a subdivision.
AllVerticesIterator	An iterator over all vertices in a subdivision.
BoundingRect	An axis aligned minimal bounding rectangle.
DelaunayTriangle	Represents a triangle in a delaunay triangulation.
DelaunayTriangleIterator	Iterator over all triangles in a delaunay triangulation.
DelaunayTriangulation	A 2D Delaunay triangulation.
FloatKernel	Offers a fast, precise kernel working with `f64` coordinates.
RTree	A rust implementation of n dimensional r*-trees
RTreeIterator	Iterates over all entries in an r-tree. Returned by `RTree::iter()`
TrivialKernel	Offers fast, possibly approximative and possibly inaccurate geometric calculations.
VertexHandle	A reference to a vertex in a triangulation. Note that this handle dereferences to the data it represents.

Enums

PositionInTriangulation	Yields information about a point's position in triangulation.
RTreeNodeIterator

Traits

DelaunayKernel	Determines how a delaunay triangulation performs its basic geometry computation.
HasPosition	An object with a well defined location. Since this trait also implements `SpatialObject`, `HasPosition` can serve as a quick and easy implementation of your own pointlike objects that can be inserted into r-trees:
HasPosition2D	Like `HasPosition`, but will only work for two dimensional vectors.
SpadeFloat	Trait for `SpadeNum`s that are also a floating point number. Used by all operations that require precise division.
SpadeNum	Scalar that can be used for spade's datastructures will need to implement this trait. Can be an integer or floating point type. Note that `copy` is not necessary.
SpatialObject	Describes objects that can be located by r-trees.
TwoDimensional	Only implemented by two dimensional vectors. Some datastructures won't work for if 3 or more dimensional vectors are used, this trait will ensure that they all have the correct dimension.
VectorN	Abstraction over vectors in different dimensions.

Type Definitions

FixedVertexHandle

A 'static handle to a vertex. This handle can be made persistent and will remain valid until the vertex it refers to is removed.