[go: up one dir, main page]

spade 2.14.0

Delaunay triangulations for the rust ecosystem
Documentation 
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

use std::time::Duration;

use criterion::{measurement::WallTime, BenchmarkGroup, Criterion};
use rand::distr::uniform::SampleUniform;
use spade::{
    DelaunayTriangulation, HierarchyHintGeneratorWithBranchFactor, HintGenerator, Point2, SpadeNum,
    Triangulation,
};

use crate::benchmark_utilities::{uniform_distribution, uniform_f64, SEED2};

pub fn locate_benchmark(c: &mut Criterion) {
    const RANGE: f64 = 1.0e9;
    const NUM_ELEMENTS: usize = 100_000;

    fn single_locate_benchmark<
        H: HintGenerator<S>,
        I: IntoIterator<Item = Point2<S>>,
        S: SpadeNum + SampleUniform,
    >(
        group: &mut BenchmarkGroup<WallTime>,
        name: String,
        range: S,
        elements: I,
    ) where
        S::Sampler: Copy,
    {
        let triangulation = DelaunayTriangulation::<_, (), (), (), H>::bulk_load(
            uniform_distribution(*SEED2, range)
                .take(NUM_ELEMENTS)
                .collect(),
        )
        .unwrap();

        let mut elements = elements.into_iter();

        group.bench_function(name, |b| {
            b.iter_with_setup(
                || elements.next().unwrap(),
                |point| triangulation.locate(point),
            )
        });
    }

    let mut group = c.benchmark_group("locate benchmark (uniform)");
    group
        .warm_up_time(Duration::from_secs(2))
        .measurement_time(Duration::from_secs(4));

    fn single_hierarchy<const BRANCH_FACTOR: u32>(group: &mut BenchmarkGroup<WallTime>) {
        single_locate_benchmark::<HierarchyHintGeneratorWithBranchFactor<f64, BRANCH_FACTOR>, _, _>(
            group,
            format!("locate (hierarchy<{:02}>), f64", BRANCH_FACTOR),
            RANGE,
            uniform_f64(),
        );
    }

    single_hierarchy::<2>(&mut group);
    single_hierarchy::<3>(&mut group);
    single_hierarchy::<4>(&mut group);
    single_hierarchy::<5>(&mut group);
    single_hierarchy::<8>(&mut group);
    single_hierarchy::<10>(&mut group);
    single_hierarchy::<14>(&mut group);
    single_hierarchy::<16>(&mut group);
    single_hierarchy::<18>(&mut group);
    single_hierarchy::<20>(&mut group);
    single_hierarchy::<32>(&mut group);
    single_hierarchy::<40>(&mut group);
    single_hierarchy::<50>(&mut group);
    single_hierarchy::<64>(&mut group);
    single_hierarchy::<70>(&mut group);
    single_hierarchy::<80>(&mut group);
    single_hierarchy::<90>(&mut group);

    group.finish();
}