#computational-geometry #fortune #voronoi-diagram #diagram #voronoi #fortune-algorithm

voronoi

A library to compute Voronoi diagrams, using Fortune's sweepline algorithm

5 releases

Uses old Rust 2015

0.1.4 Nov 26, 2017
0.1.3 Sep 27, 2017
0.1.2 Sep 27, 2017
0.1.1 Sep 26, 2017
0.1.0 Sep 26, 2017

#1923 in Algorithms

Download history 53/week @ 2023-11-06 66/week @ 2023-11-13 65/week @ 2023-11-20 43/week @ 2023-11-27 30/week @ 2023-12-04 41/week @ 2023-12-11 47/week @ 2023-12-18 45/week @ 2023-12-25 25/week @ 2024-01-01 36/week @ 2024-01-08 55/week @ 2024-01-15 32/week @ 2024-01-22 29/week @ 2024-01-29 29/week @ 2024-02-05 54/week @ 2024-02-12 128/week @ 2024-02-19

241 downloads per month

MIT license

48KB
1K SLoC

voronoi

This is a Rust implementation of Fortune's Linesweep algorithm for computing Voronoi diagrams.

Online Documentation

Usage

To use, add the following line to Cargo.toml under [dependencies]:

voronoi = "0.1.4"

or alternatively,

voronoi = { git = "https://github.com/petosegan/rust_voronoi.git" }

Example

extern crate voronoi;
use voronoi::{voronoi, Point, make_polygons};
const BOX_SIZE: f64 = 800.;
// ...
let vor_pts = vec![Point::new(0.0, 1.0), Point::new(2.0, 3.0), Point::new(10.0, 12.0)];
let vor_diagram = voronoi(vor_pts, BOX_SIZE);
let vor_polys = make_polygons(&vor_diagram);

TODO

  • Handle degeneracies in geometry.rs
  • Match DCEL faces to input points
  • Reimplement the data structures with memory management
  • Balance the trees
  • Benchmark against other implementations

lib.rs:

A Rust implementation of Fortune's Linesweep algorithm for computing Voronoi diagrams.

Dependencies

~1MB
~16K SLoC