generators.rs
1 //! Utilities for generating examples, benchmarks, and test cases. 2 3 use std::f64::consts::PI; 4 5 use kurbo::{Affine, BezPath}; 6 7 use crate::Point; 8 9 type Contours = Vec<Vec<Point>>; 10 11 /// Generate a bunch of squares, arranged in a grid. 12 /// 13 /// The top-left of the first square is at (x0, y0). Each square has size `size 14 /// x size`, and the distance between squares (both horizontally and vertically) 15 /// is `offset`. 16 /// 17 /// If `slant` is non-zero, generates parallelograms instead of squares: the 18 /// right-hand side of each square gets translated down by `slant`. 19 fn squares((x0, y0): (f64, f64), size: f64, offset: f64, slant: f64, count: usize) -> Contours { 20 let mut ret = Vec::new(); 21 for i in 0..count { 22 let x = x0 + i as f64 * offset; 23 for j in 0..count { 24 let y = y0 + j as f64 * offset; 25 ret.push(vec![ 26 Point::new(x, y), 27 Point::new(x, y + size), 28 Point::new(x + size, y + size + slant), 29 Point::new(x + size, y + slant), 30 ]); 31 } 32 } 33 34 ret 35 } 36 37 /// Generate an `n` by `n` checkerboard-like pattern with overlapping squares. 38 /// For `n = 3`, it looks like: 39 /// 40 /// ```text 41 /// ┌────┐ ┌────┐ ┌────┐ 42 /// │ │ │ │ │ │ 43 /// │ ┌─┼─┼─┐┌─┼─┼─┐ │ 44 /// └──┼─┘ └─┼┼─┘ └─┼──┘ 45 /// ┌──┼─┐ ┌─┼┼─┐ ┌─┼──┐ 46 /// │ └─┼─┼─┘└─┼─┼─┘ │ 47 /// │ ┌─┼─┼─┐┌─┼─┼─┐ │ 48 /// └──┼─┘ └─┼┼─┘ └─┼──┘ 49 /// ┌──┼─┐ ┌─┼┼─┐ ┌─┼──┐ 50 /// │ └─┼─┼─┘└─┼─┼─┘ │ 51 /// │ │ │ │ │ │ 52 /// └────┘ └────┘ └────┘ 53 /// ``` 54 /// 55 /// We return the pattern in two parts: the outer collection of `n x n` 56 /// non-overlapping squares, and the inner collection of `(n - 1) x (n - 1)` 57 /// non-overlapping squares. 58 pub fn checkerboard(n: usize) -> (Contours, Contours) { 59 ( 60 squares((0.0, 0.0), 30.0, 40.0, 0.0, n), 61 squares((20.0, 20.0), 30.0, 40.0, 0.0, n - 1), 62 ) 63 } 64 65 /// Like `checkerboard`, but with no exactly-horizontal lines. 66 /// 67 /// Horizontal lines have special handling in the sweep-line algorithm, so 68 /// their presence or absence can affect performance. 69 pub fn slanted_checkerboard(n: usize) -> (Contours, Contours) { 70 ( 71 squares((0.0, 0.0), 30.0, 40.0, 1.0, n), 72 squares((20.0, 20.0), 30.0, 40.0, 1.0, n - 1), 73 ) 74 } 75 76 /// The "evens" are a bunch of long, skinny parallelograms going from top-left 77 /// to bottom-right. The "odds" go from top-right to bottom-left. 78 pub fn slanties(n: usize) -> (Contours, Contours) { 79 let h = 20.0 * n as f64; 80 81 let mut even = Vec::new(); 82 let mut odd = Vec::new(); 83 for i in 0..n { 84 let x_off = 20.0 * i as f64; 85 even.push(vec![ 86 Point::new(x_off, 0.0), 87 Point::new(x_off + h, h), 88 Point::new(x_off + h + 10.0, h), 89 Point::new(x_off + 10.0, 0.0), 90 ]); 91 92 odd.push(vec![ 93 Point::new(x_off + h, 0.0), 94 Point::new(x_off, h), 95 Point::new(x_off + 10.0, h), 96 Point::new(x_off + h + 10.0, 0.0), 97 ]); 98 } 99 100 (even, odd) 101 } 102 103 /// A bunch of things that all intersect at the origin, some tangentially. 104 pub fn star(n: usize) -> (BezPath, BezPath) { 105 fn mul(p: kurbo::Point, f: f64) -> kurbo::Point { 106 (p.x * f, p.y * f).into() 107 } 108 109 let angle_increment = PI / (n as f64 * 2.0); 110 let mut angle = 0.0; 111 112 let mut straight = BezPath::new(); 113 let mut bent = BezPath::new(); 114 let p = kurbo::Point::new(1.0, 0.0); 115 for i in 0..n { 116 let p0 = Affine::rotate(angle) * p; 117 let p1 = Affine::rotate(angle + angle_increment) * p; 118 let p2 = Affine::rotate(angle + angle_increment + PI) * p; 119 let p3 = Affine::rotate(angle + PI) * p; 120 121 if i.is_multiple_of(2) { 122 straight.move_to(p0); 123 straight.line_to(p1); 124 straight.line_to(p2); 125 straight.line_to(p3); 126 straight.close_path(); 127 } else { 128 let zero_ish = mul(p0, 1e-12); 129 let neg_zero_ish = mul(p0, -1e-12); 130 bent.move_to(p0); 131 bent.line_to(p1); 132 bent.curve_to(mul(p1, 2. / 3.), mul(p0.midpoint(p1), 1. / 3.), zero_ish); 133 bent.curve_to(mul(p2.midpoint(p3), 1. / 3.), mul(p2, 2. / 3.), p2); 134 bent.line_to(p3); 135 bent.curve_to( 136 mul(p3, 2. / 3.), 137 mul(p2.midpoint(p3), 1. / 3.), 138 neg_zero_ish, 139 ); 140 bent.curve_to(mul(p0.midpoint(p1), 1. / 3.), mul(p0, 2. / 3.), p0); 141 } 142 143 angle += 2.0 * angle_increment; 144 } 145 146 (straight, bent) 147 }