cdt 0.1.0

Fast, robust constrained Delaunay triangulation
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
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

use std::iter::repeat_with;
use rand::{Rng, SeedableRng};

use clap::{Arg, App};
use itertools::Itertools;

const N: usize = 64;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let matches = App::new("fuzz")
        .author("Matt Keeter <matt.j.keeter@gmail.com>")
        .about("Fuzzes the triangulator")
        .arg(Arg::with_name("num")
            .short("n")
            .long("num")
            .help("number of points")
            .takes_value(true))
        .arg(Arg::with_name("output")
            .short("o")
            .long("out")
            .help("svg file to target")
            .takes_value(true))
        .arg(Arg::with_name("check")
            .short("c")
            .long("check")
            .help("check invariants after each step (slow)"))
        .arg(Arg::with_name("lock")
            .short("l")
            .long("lock")
            .help("lock three edges to test constrained triangulation"))
        .get_matches();

    let num = matches.value_of("num")
        .map(|s| s.parse())
        .unwrap_or(Ok(N))?;

    let check = matches.is_present("check");

    let mut i = 0;
    loop {
        if i % 1000 == 0 {
            eprintln!("{}", i);
        }
        i += 1;

        let seed = rand::thread_rng().gen();
        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(seed);

        // We generate random points as f32, to make it more likely that
        // some will line up exactly on one axis or another, which can trigger
        // interesting edge cases.  Experimentally, we have X or Y collisions
        // at a rate of about one per 4K fuzzed samples.
        let points: Vec<_> = repeat_with(|| rng.gen_range(0.0..1.0))
            .tuple_windows()
            .map(|(a, b): (f32, f32)| (a as f64, b as f64))
            .take(num)
            .collect();

        // Generator to build the triangulation
        let gen = || if matches.is_present("lock") {
            cdt::Triangulation::new_with_edges(&points,
                &[(0, 1), (1, 2), (2, 0)])
        } else {
            cdt::Triangulation::new(&points)
        };

        let mut t = gen()?;
        t.check();
        let result = std::panic::catch_unwind(move || {
            while !t.done() {
                t.step().expect("Could not triangulate");
                if check {
                    t.check();
                }
            }
        });

        // Count how many steps we can do before failure
        if result.is_err() {
            let mut safe_steps = 0;
            for i in 0..points.len() {
                let mut t = gen()?;
                let result = std::panic::catch_unwind(move || {
                    for _ in 0..i {
                        t.step().expect("oh no");
                        if check {
                            t.check();
                        }
                    }
                });
                if result.is_ok() {
                    safe_steps = i;
                } else {
                    break;
                }
            }

            let mut t = gen()?;
            for _ in 0..safe_steps {
                t.step().expect("Failed too early");
            }

            if let Some(out) = matches.value_of("output") {
                eprintln!("    Saving {}", out);
                t.save_debug_svg(out).expect("Could not save SVG");
            } else {
                println!("{}", t.to_svg(true));
            }
            eprintln!("Crashed with seed: {}", seed);
            break Ok(())
        }
    }
}