Crate voronator[−][src]
Expand description
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 voronator::delaunator::Point;
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::<Point>::from_tuple(&(0., 0.), &(100., 100.), &points).unwrap();
for cell in diagram.cells() {
let p: Vec<(f32, f32)> = cell.points().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 voronator::delaunator::Point;
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::<Point>::from_tuple(&points).unwrap();
for cell in diagram.cells {
let p: Vec<(f32, f32)> = cell.points().into_iter()
.map(|x| (x.x as f32, x.y as f32))
.collect();
println!("{:?}", p);
}
}
Modules
Implements the Delaunay triangulation algorithm.
Provides functions for handling polygons.
Structs
Represents a centroidal tesselation diagram.
Represents a Voronoi diagram.