Crate voronator

Constructs a Voronoi diagram given a set of points.

This module was adapted from d3-delaunay and from Red Blog Games Voronoi maps tutorial. It implements the Delaunay triangulation dual extraction, which is the Voronoi diagram. It also implements a centroidal tesselation based on the Voronoi diagram, but using centroids instead of circumcenters for the vertices of the cell polygons.

Apart from the triangle center they are using, the Voronoi and Centroidal diagrams differ in how they handle the hull cells. The Voronoi diagram implements a clipping algorithm that clips the diagram into a bounding box, thus extracting neat polygons around the hull. The Centroid diagram, in the other hand, doesn't. The outer cells can be missing or be distorted, as triangles calculated by the Delaunay triangulation can be too thin in the hull, causing centroid calculation to be "bad".

If you have a robust solution for this particular problem, please let me know either by creating an issue or through a pull-request, and I will make sure to add your solution with the proper credits.

Example

Voronoi Diagram

extern crate voronator;
extern crate rand;
 
use voronator::VoronoiDiagram;
use rand::prelude::*;
use rand::distributions::Uniform;
 
fn main() {
    let mut rng = rand::thread_rng();
    let range1 = Uniform::new(0., 100.);
    let range2 = Uniform::new(0., 100.);
    let mut points: Vec<(f64, f64)> = (0..10)
        .map(|_| (rng.sample(&range1), rng.sample(&range2)))
        .collect();
 
    let diagram = VoronoiDiagram::from_tuple(&(0., 0.), &(100., 100.), &points).unwrap();
     
    for cell in diagram.cells {
        let p: Vec<(f32, f32)> = cell.into_iter()
            .map(|x| (x.x as f32, x.y as f32))
            .collect();
         
        println!("{:?}", p);
    }
}

Centroidal Tesselation Diagram

extern crate voronator;
extern crate rand;
 
use voronator::CentroidDiagram;
use rand::prelude::*;
use rand::distributions::Uniform;
 
fn main() {
    let mut rng = rand::thread_rng();
    let range1 = Uniform::new(0., 100.);
    let range2 = Uniform::new(0., 100.);
    let mut points: Vec<(f64, f64)> = (0..10)
        .map(|_| (rng.sample(&range1), rng.sample(&range2)))
        .collect();
 
    let diagram = CentroidDiagram::from_tuple(&points).unwrap();
     
    for cell in diagram.cells {
        let p: Vec<(f32, f32)> = cell.into_iter()
            .map(|x| (x.x as f32, x.y as f32))
            .collect();
         
        println!("{:?}", p);
    }
}

Modules

delaunator

Implements the Delaunay triangulation algorithm.

Structs

CentroidDiagram	Represents a centroidal tesselation diagram.
VoronoiDiagram	Represents a Voronoi diagram.