1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349
//! # voronoice
//!
//! This crate provides a nice and fast way to construct 2D [Voronoi diagrams](https://en.wikipedia.org/wiki/Voronoi_diagram) from a set of sites.
//! It builds Voronoi diagrams by first obtaining its [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation), through the really fast [delaunator](https://docs.rs/delaunator/*/delaunator) crate,
//! and then extracting its dual Voronoi diagram.
//!
//! Both the Voronoi graph and its dual Delaunay graph are exposed through the [Voronoi] type.
//!
//! # Example
//!
//!```rust
//! use voronoice::*;
//!
//! // voronoi sites
//! let sites = vec![
//! Point { x: 0.0, y: 0.0 }, Point { x: 1.0, y: 0.0 }, Point { x: 0.0, y: 1.0 }
//! ];
//!
//! // builds a voronoi diagram from the set of sites above, bounded by a square of size 4
//! let my_voronoi = VoronoiBuilder::default()
//! .set_sites(sites)
//! .set_bounding_box(BoundingBox::new_centered_square(4.0))
//! .set_lloyd_relaxation_iterations(5)
//! .build()
//! .unwrap();
//!
//! // inspect cells through iterators
//! my_voronoi.iter_cells().for_each(|cell| {
//! println!("Vertices of cell: {:?}", cell.iter_vertices().collect::<Vec<&Point>>())
//! });
//!
//! // or probe cells individually
//! let my_cell = my_voronoi.cell(1);
//! println!("Second cell has site {:?}, voronoi vertices {:?} and delaunay triangles {:?}",
//! my_cell.site_position(),
//! my_cell.iter_vertices().collect::<Vec<&Point>>(),
//! my_cell.triangles().iter().collect::<Vec<&usize>>());
//!
//! // or, for graphical applications, that benefit from index buffers
//! // you can access the raw, indexed data
//! let all_voronoi_cell_vertices = my_voronoi.vertices();
//! let indexed_voronoi_cells = my_voronoi.cells();
//! println!("The first vertex position for the first voronoi cell is at {:?}",
//! all_voronoi_cell_vertices[indexed_voronoi_cells[0][0]]);
//!```
mod bounding_box;
mod cell_builder;
mod voronoi_cell;
mod iterator;
mod utils;
mod voronoi_builder;
use std::{fmt::Display, str::FromStr};
use delaunator::{EMPTY, Triangulation, triangulate};
use self::{
utils::cicumcenter,
cell_builder::*
};
pub use voronoi_builder::VoronoiBuilder;
pub use bounding_box::BoundingBox;
pub use voronoi_cell::VoronoiCell;
pub use iterator::TopologicalNeighborSiteIterator;
pub use iterator::NeighborSiteIterator;
pub use iterator::CellPathIterator;
pub use delaunator::Point;
/// Defines how Voronoi generation will handle clipping of Voronoi cell edges within the bounding box.
///
/// Clipping is necessary to guarantee that all Voronoi vertices are within the bounding box boundary.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum ClipBehavior {
/// No clipping will be performed. Any sites outside the bounding box will still be used for diagram generation.
None,
/// Removes any sites outside the bounding box, but does not perform any further clipping of Voronoi cells that may end up outside of the bounding box.
RemoveSitesOutsideBoundingBoxOnly,
/// Removes sites outside bounding box and clips any Voronoi cell edges that fall outside of the bounding box.
Clip,
}
impl Default for ClipBehavior {
fn default() -> Self {
ClipBehavior::Clip
}
}
impl Display for ClipBehavior {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{:?}", self)
}
}
impl FromStr for ClipBehavior {
type Err = String;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"None" => Ok(Self::None),
"RemoveSitesOutsideBoundingBoxOnly" => Ok(Self::RemoveSitesOutsideBoundingBoxOnly),
"Clip" => Ok(Self::Clip),
_ => Err("Invalid option".to_string())
}
}
}
/// The dual Delaunay-Voronoi graph.
///
/// To obtain an instance of this type, use [VoronoiBuilder].
#[derive(Clone)]
pub struct Voronoi {
/// These are the sites of each voronoi cell.
sites: Vec<Point>,
bounding_box: BoundingBox,
triangulation: Triangulation,
clip_behavior: ClipBehavior,
/// The circumcenter of each triangle (indexed by triangle / triangle's starting half-edge).
///
/// For a given voronoi cell, its vertices are the circumcenters of its associated triangles.
/// Values whose indexes are greater than sites.len() - 1 are not actual triangle circumcenters but
/// voronoi cell vertices added to close sites on the convex hull or otherwise used for clipping edges that fell outside the bounding box region.
circumcenters: Vec<Point>,
/// A map of each site to its left-most incomig half-edge.
site_to_incoming_leftmost_halfedge: Vec<usize>,
/// A map for each voronoi cell and the associated delaunay triangles whose centroids are the cell's vertices.
/// For any site ```i```, the associated voronoi cell associated triangles are represented by ```cell_triangles[i]```.
cells: Vec<Vec<usize>>
}
impl std::fmt::Debug for Voronoi {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
f.debug_struct("Voronoi")
.field("sites", &self.sites)
.field("circumcenters", &self.circumcenters)
.field("cell_triangles", &self.cells)
.finish()
}
}
// When reading this code think about 'edge' as the starting edge for a triangle
// So you can say that the starting edge indexes the triangle
// For instances, diag.triangles.len() is the number of starting edges and triangles in the triangulation, you can think of diag.triangles[e] as 'e' as being both the index of the
// starting edge and the triangle it represents. When dealing with an arbitraty edge, it may not be a starting edge. You can get the starting edge by dividing the edge by 3 and flooring it.
impl Voronoi {
fn new(sites: Vec<Point>, bounding_box: BoundingBox, clip_behavior: ClipBehavior) -> Option<Self> {
// remove any points not within bounding box
let sites = match clip_behavior {
ClipBehavior::RemoveSitesOutsideBoundingBoxOnly | ClipBehavior::Clip => sites.into_iter().filter(|p| bounding_box.is_inside(p)).collect::<Vec<Point>>(),
ClipBehavior::None => sites
};
let triangulation = triangulate(&sites);
// triangulation.triangles is the indexing of each half-edge to source site
// 3 * t, 3 * t + 1 and 3 * t + 2 are the vertices of a triangle in this vector
let num_of_triangles = triangulation.triangles.len() / 3;
if num_of_triangles == 0 {
return None
}
// calculate circuncenter of each triangle, these will be the vertices of the voronoi cells
let circumcenters = (0..num_of_triangles).map(|t| cicumcenter(
&sites[triangulation.triangles[3* t]],
&sites[triangulation.triangles[3* t + 1]],
&sites[triangulation.triangles[3* t + 2]])
).collect();
// create cell builder to build cells and update circumcenters
let cell_builder = CellBuilder::new(&triangulation, &sites, circumcenters, bounding_box.clone(), clip_behavior);
let result = cell_builder.build();
Some(Voronoi {
bounding_box,
site_to_incoming_leftmost_halfedge: result.site_to_incoming_leftmost_halfedge,
triangulation,
sites,
clip_behavior,
circumcenters: result.vertices,
cells: result.cells
})
}
/// Borrows an immutable reference to the sites associated with the Voronoi graph.
/// This is a reference to the unaltered site-point collection provided for the construction of this Voronoi graph.
#[inline]
pub fn sites(&self) -> &Vec<Point> {
&self.sites
}
/// Gets a representation of a Voronoi cell based on its site index.
///
/// # Examples
///```
/// use voronoice::*;
/// let v = VoronoiBuilder::default()
/// .generate_square_sites(10)
/// .build()
/// .unwrap();
/// println!("The following are the positions for the Voronoi cell 0: {:?}",
/// v.cell(0).iter_vertices().collect::<Vec<&Point>>());
///```
#[inline]
pub fn cell(&self, site: usize) -> VoronoiCell {
VoronoiCell::new(site, self)
}
/// Gets an iterator to walk through all Voronoi cells.
/// Cells are iterated in order with the vector returned by [Self::sites()].
pub fn iter_cells<'v>(&'v self) -> impl Iterator<Item = VoronoiCell<'v>> + Clone {
(0..self.sites.len())
.map(move |s| self.cell(s))
}
/// Gets a vector of Voronoi cell vectors that index the cell vertex positions.
///
/// Consider using [Self::iter_cells()] or [Self::cell()] instead for a more ergonomic way of accessing cell information.
/// Use cases for accessing this directly would include graphical applications where you need to build an index buffer for point positions.
///
/// # Examples
///```
/// use voronoice::*;
/// let v = VoronoiBuilder::default()
/// .generate_square_sites(10)
/// .build()
/// .unwrap();
/// let first_cell = v.cells().first().unwrap();
/// let vertices = v.vertices();
/// println!("The following are the positions for the Voronoi cell 0: {:?}",
/// first_cell.iter().copied().map(|v| &vertices[v]).collect::<Vec<&Point>>());
///```
#[inline]
pub fn cells(&self) -> &Vec<Vec<usize>> {
&self.cells
}
/// Gets the a vector of the Voronoi cell vertices. These vertices are indexed by [Self::cells()].
/// Consider using [Self::iter_cells()] or [Self::cell()] instead for a more ergonomic way of accessing cell information.
///
/// For a given Voronoi cell, its vertices are the circumcenters of its associated Delaunay triangles.
/// Values whose indexes are greater than ```sites.len() - 1``` are not actual triangle circumcenters but
/// Voronoi cell vertices added to "close" sites on the convex hull or otherwise used for clipping edges that fell outside the bounding box region.
///
/// Please see [Self::cells()] documentation for examples.
#[inline]
pub fn vertices(&self) -> &Vec<Point> {
&self.circumcenters
}
/// Gets a reference to the underlying delaunay triangulation.
///
/// ```triangulation().triangles``` is a vector of indices to sites where each triple represents a triangle on the dual Delaunay triangulation associated with this Voronoi graph.
/// All triangles are directed counter-clockwise.
#[inline]
pub fn triangulation(&self) -> &Triangulation {
&self.triangulation
}
/// Gets a reference to the bounding box.
pub fn bounding_box(&self) -> &BoundingBox {
&self.bounding_box
}
/// Gets the number of Delaunay triangles.
fn number_of_triangles(&self) -> usize {
self.triangulation.triangles.len() / 3
}
}
#[cfg(test)]
mod tests {
use rand::Rng;
use super::*;
fn create_random_builder(size: usize) -> VoronoiBuilder {
let mut rng = rand::thread_rng();
let builder = VoronoiBuilder::default();
let bbox = BoundingBox::default();
let x_range = rand::distributions::Uniform::new(-bbox.width() / 2.0, bbox.width() / 2.0);
let y_range = rand::distributions::Uniform::new(-bbox.height() / 2.0, bbox.height() / 2.0);
let sites = (0..size)
.map(|_| Point { x: rng.sample(x_range), y: rng.sample(y_range) })
.collect();
builder
.set_bounding_box(bbox)
.set_sites(sites)
}
#[test]
fn random_100_000_site_generation_test() {
let voronoi = create_random_builder(100_000)
.build()
.expect("Some voronoi expected.");
utils::test::validate_voronoi(&voronoi);
}
#[test]
fn random_15_site_generation_test() {
for _ in 0..1000 {
let voronoi = create_random_builder(15)
.build()
.expect("Some voronoi expected.");
utils::test::validate_voronoi(&voronoi);
}
}
#[test]
fn validate_examples() -> std::io::Result<()> {
for path in [
"degenerated1.json",
"degenerated2.json",
"degenerated3.json",
"degenerated4.json",
"degenerated5.json",
"degenerated6.json",
"degenerated7.json",
"degenerated8.json",
"degenerated9.json",
"degenerated10.json",
"clockwise1.json",
] {
let voronoi = utils::test::new_voronoi_builder_from_asset(path)?
.build()
.expect("Some voronoi expected");
utils::test::validate_voronoi(&voronoi);
}
Ok(())
}
#[test]
fn collinear_sites() {
let voronoi = VoronoiBuilder::default()
.set_sites([ Point { x: 0.0, y: 0.0 }, Point { x: 0.0, y: 1.0 }, Point { x: 0.0, y: 2.0 } ].to_vec())
.build();
assert!(voronoi.is_none(), "Collinear points do not generate valid voronoi");
}
}