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::{Point, triangulate_from_tuple};

fn main() {
    let points = vec![(0., 0.), (1., 0.), (1., 1.), (0., 1.)];

    let (t, _) = triangulate_from_tuple::<Point>(&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 comparisons

INVALID_INDEX

Defines an invalid index in the Triangulation vectors

Traits

Coord

Trait for a coordinate (point) used to generate a Voronoi diagram. The default included struct Point is included below as an example.

Vector

Trait implementing basic vector functions for a Coord.

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.