Struct boostvoronoi::Builder

pub struct Builder<I, F>
where
    I: InputType,
    F: OutputType,
{ /* private fields */ }

The sweepline algorithm implementation to compute Voronoi diagram of points and non-intersecting segments (excluding endpoints). Complexity - O(N*logN), memory usage - O(N), where N is the total number of input geometries.

CONTRACT:

1. Input geometries should be of signed integer type (e.g. i32, i64).
2. Input geometries should never intersect except at their endpoints.

IMPLEMENTATION DETAILS: Each input point creates one input site. Each input segment creates three input sites: two for its endpoints and one for the segment itself (this is made to simplify output construction). All the site objects are constructed and sorted at the algorithm initialization step. Priority queue is used to dynamically hold circle events. At each step of the algorithm execution the leftmost event is retrieved by comparing the current site event and the topmost element from the circle event queue. STL map (red-black tree) container was chosen to hold state of the beach line. The keys of the map correspond to the neighboring sites that form a bisector and values map to the corresponding Voronoi edges in the output data structure.

use boostvoronoi_core::BvError;

type I = i32; // this is the integer input type
type F = f64; // this is the float output type (circle event coordinates)

// Points should be unique. Points should not intersect lines
let p = vec!(Point{x:9_i32, y:10});
// Lines may only intersect at the endpoints.
let s = vec!(Line::new(Point{x:10_i32, y:11}, Point{x:12, y:13}));
let result = Builder::<I, F>::default()
    // You will have to keep track of the input geometry. it will be referenced as
    // input geometry indices in the output.
    // `with_vertices()` and `with_segments()` accepts iterators of anything that implements
    // `Into()` for `Point` and `Line`
    .with_vertices(p.iter())?
    .with_segments(s.iter())?
    // this will generate a the list of cells, edges and circle events (aka vertices)
    .build()?;

Implementations

impl<I, F> Builder<I, F>

where I: InputType, F: OutputType,

pub fn with_vertices<T, IT>(self, vertices: T) -> Result<Builder<I, F>, BvError>

where T: IntoIterator<Item = IT>, IT: Copy + Into<Point<I>>,

Inserts vertices. This should be done before inserting segments. This method accepts iterators of anything that implements Into<boostvoronoi::geometry::Point>

pub fn with_segments<T, IT>(self, segments: T) -> Result<Builder<I, F>, BvError>

where T: IntoIterator<Item = IT>, IT: Copy + Into<Line<I>>,

Inserts segments. This should be done after inserting vertices. This method accepts iterators of anything that implements Into<boostvoronoi::geometry::Line>

pub fn build(self) -> Result<Diagram<F>, BvError>

Run sweep-line algorithm and fill output data structure.

Trait Implementations

impl<I, F> Default for Builder<I, F>

where I: InputType, F: OutputType,

fn default() -> Builder<I, F>

Returns the “default value” for a type.