Module voronator::delaunator

Implements the Delaunay triangulation algorithm.

This module was ported from the original Delaunator, by Mapbox. If a triangulation is possible a given set of points in the 2D space, it returns a Triangulation structure. This structure contains three main components: triangles, halfedges and hull:

let coords = vec![(0., 0.), (1., 0.), (1., 1.), (0., 1.)];
let (delaunay, _) = delaunator::triangulate_from_tuple(&coords).unwrap();

• triangles: A Vec<usize> that contains the indices for each vertex of a triangle in the original array. All triangles are directed counter-clockwise. To get the coordinates of all triangles, use:

let t = 0;
loop {
    println!("[{:?}, {:?}, {:?}]",
        coords[delaunay.triangles[t]],
        coords[delaunay.triangles[t+1]],
        coords[delaunay.triangles[t+2]],
    );
    t += 3;
}

• halfedges: Vec<usize> array of triangle half-edge indices that allows you to traverse the triangulation. i-th half-edge in the array corresponds to vertex triangles[i] the half-edge is coming from. halfedges[i] is the index of a twin half-edge in an adjacent triangle (or INVALID_INDEX for outer half-edges on the convex hull). The flat array-based data structures might be counterintuitive, but they're one of the key reasons this library is fast.
• hull: A Vec<usize> array of indices that reference points on the convex hull of the input data, counter-clockwise.

The last two components, inedges and outedges, are for voronator internal use only.

Example

extern crate voronator;
 
use voronator::delaunator::{triangulate_from_tuple};
 
fn main() {
    let points = vec![(0., 0.), (1., 0.), (1., 1.), (0., 1.)];
     
    let (t, _) = triangulate_from_tuple(&points)
        .expect("No triangulation exists for this input.");
 
    for i in 0..t.len() {
        let i0 = t.triangles[3*i];
        let i1 = t.triangles[3*i + 1];
        let i2 = t.triangles[3*i + 2];
 
        let p = vec![points[i0], points[i1], points[i2]];
 
        println!("triangle {}: {:?}", i, p);
    }
}

Structs

Point	Represents a point in the 2D space.
Triangulation	Represents a Delaunay triangulation for a given set of points. See example in delaunator for usage details.

Constants

EPSILON	Defines a comparison epsilon used for floating-point comparissons
INVALID_INDEX	Defines an invalid index in the Triangulation vectors

Functions

circumcenter	Calculates the circumcenter of a triangle, given it's three vertices
edges_around_point	Returns a vec containing all edges around a point
edges_of_triangle	Returns a vec containing indices for the 3 edges of a triangle t
next_halfedge	Returs the next halfedge for a given halfedge
points_of_triangle	Returns a vec containing the indices of the corners of the given triangle
prev_halfedge	Returs the previous halfedge for a given halfedge
triangle_of_edge	Returns the triangle associated with the given edge
triangles_adjacent_to_triangle	Returns a vec containing the indices for the adjacent triangles of the given triangle
triangulate	Calculates the Delaunay triangulation, if it exists, for a given set of 2D points
triangulate_from_arr	Calculates the Delaunay triangulation, if it exists, for a given set of 2D points.
triangulate_from_tuple	Calculates the Delaunay triangulation, if it exists, for a given set of 2D points.