# [−][src]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.