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

## 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. |