linesweeper 0.3.0

Robust sweep-line algorithm and two-dimensional boolean ops
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

//! Utilities for fuzz and/or property testing using `arbitrary`.

use arbitrary::Unstructured;
use kurbo::{CubicBez, Point};

use crate::{curve::Quadratic, geom};

/// Generate an arbitrary float in some range.
pub fn float_in_range(
    start: f64,
    end: f64,
    u: &mut Unstructured<'_>,
) -> Result<f64, arbitrary::Error> {
    let num: u32 = u.arbitrary()?;
    let t = num as f64 / u32::MAX as f64;
    Ok((start + t * (end - start)).clamp(start, end))
}

fn float(u: &mut Unstructured<'_>) -> Result<f64, arbitrary::Error> {
    float_in_range(-1e6, 1e6, u)
}

fn float_at_least(min: f64, u: &mut Unstructured<'_>) -> Result<f64, arbitrary::Error> {
    float_in_range(min, 1e6, u)
}

fn float_at_most(max: f64, u: &mut Unstructured<'_>) -> Result<f64, arbitrary::Error> {
    float_in_range(-1e6, max, u)
}

/// Generate a float in some range, but give it a chance to be close to another float.
fn another_float_in_range(
    orig: f64,
    start: f64,
    end: f64,
    u: &mut Unstructured<'_>,
) -> Result<f64, arbitrary::Error> {
    let close: bool = u.arbitrary()?;
    if close {
        let ulps: i32 = u.int_in_range(-32..=32)?;
        let scale = 1.0f64 + ulps as f64 * f64::EPSILON;
        Ok((orig * scale).clamp(start, end))
    } else {
        float_in_range(start, end, u)
    }
}

fn point(u: &mut Unstructured<'_>) -> Result<Point, arbitrary::Error> {
    Ok(Point::new(float(u)?, float(u)?))
}

fn point_at_least(min: f64, u: &mut Unstructured<'_>) -> Result<Point, arbitrary::Error> {
    Ok(Point::new(float(u)?, float_at_least(min, u)?))
}

fn point_at_most(max: f64, u: &mut Unstructured<'_>) -> Result<Point, arbitrary::Error> {
    Ok(Point::new(float(u)?, float_at_most(max, u)?))
}

/// Generate an arbitrary cubic Bezier, guaranteed to be monotonically increasing in y.
pub fn monotonic_bezier(u: &mut Unstructured<'_>) -> Result<CubicBez, arbitrary::Error> {
    let p0 = point(u)?;
    let p3 = point(u)?;
    let (p0, mut p3) = if p0.y < p3.y { (p0, p3) } else { (p3, p0) };
    if p3.y == p0.y {
        p3.y += 1.0;
    }

    let p1 = point_at_least(p0.y, u)?;
    let p2 = point_at_most(p3.y, u)?;

    let ret = CubicBez::new(p0, p1, p2, p3);
    Ok(geom::monotonic_pieces(ret)
        .into_iter()
        .find(|c| c.piece.p0.y < c.piece.p3.y)
        // unwrap: we started with p0 having smaller y, so there must be
        // a monotonic component that's increasing in y.
        .unwrap()
        .piece)
}

/// Generate an arbitrary cubic Bezier, guaranteed to be monotonically increasing in y.
///
/// This generated Bezier has a chance to be "close" to `first`, for example by starting
/// at the same point or with the same tangent.
pub fn another_monotonic_bezier(
    u: &mut Unstructured<'_>,
    first: &CubicBez,
) -> Result<CubicBez, arbitrary::Error> {
    let same_start: bool = u.arbitrary()?;
    let same_start_tangent: bool = same_start && u.arbitrary()?;

    let p0 = if same_start { first.p0 } else { point(u)? };

    let p1 = if same_start_tangent {
        first.p1
    } else {
        point_at_least(p0.y, u)?
    };

    let p3 = point_at_least(p0.y.max(first.p0.y), u)?;
    let p2 = point_at_most(p3.y, u)?;

    let ret = CubicBez::new(p0, p1, p2, p3);
    Ok(geom::monotonic_pieces(ret)
        .into_iter()
        .next()
        .map(|c| c.piece)
        .unwrap_or(ret))
}

/// Generate an arbitrary quadratic function, with coefficients of roughly the scale `size`.
pub fn quadratic(size: f64, u: &mut Unstructured<'_>) -> Result<Quadratic, arbitrary::Error> {
    let use_coeffs: bool = u.arbitrary()?;
    if use_coeffs {
        let c2 = float_in_range(-size, size, u)?;
        let c1 = another_float_in_range(c2, -size, size, u)?;
        let c0 = another_float_in_range(c1, -size, size, u)?;

        Ok(Quadratic { c2, c1, c0 })
    } else {
        // Generate the roots, with a bias towards an almost-repeated root.
        let size = size.sqrt();

        let r1 = float_in_range(-size, size, u)?;
        let r2 = another_float_in_range(r1, -size, size, u)?;
        let scale = float_in_range(-size, size, u)?;

        Ok(Quadratic {
            c2: scale,
            c1: -scale * (r1 + r2),
            c0: scale * r1 * r2,
        })
    }
}