-
-
Notifications
You must be signed in to change notification settings - Fork 110
/
curves.rs
106 lines (89 loc) · 2.99 KB
/
curves.rs
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
use std::cmp::max;
use fj_math::{Circle, Point, Scalar};
use crate::{
local::Local,
objects::{CurveKind, GlobalCurve},
};
use super::Tolerance;
/// Compute an approximation of the curve
///
/// `tolerance` defines how far the approximation is allowed to deviate from the
/// actual edge.
///
/// # Implementation Note
///
/// This only works as it is, because edges are severely limited and don't
/// define which section of the curve they inhabit. Once they do that, we need
/// an `approximate_between(a, b)` method instead, where `a` and `b` are the
/// vertices that bound the edge on the curve.
///
/// The `approximate_between` methods of the curves then need to make sure to
/// only return points in between those vertices, not the vertices themselves.
pub fn approx_curve(
curve: &GlobalCurve,
tolerance: Tolerance,
out: &mut Vec<Local<Point<1>>>,
) {
match curve.kind() {
CurveKind::Circle(curve) => approx_circle(curve, tolerance, out),
CurveKind::Line(_) => {}
}
}
/// Approximate the circle
///
/// `tolerance` specifies how much the approximation is allowed to deviate
/// from the circle.
pub fn approx_circle(
circle: &Circle<3>,
tolerance: Tolerance,
out: &mut Vec<Local<Point<1>>>,
) {
let radius = circle.a.magnitude();
// To approximate the circle, we use a regular polygon for which
// the circle is the circumscribed circle. The `tolerance`
// parameter is the maximum allowed distance between the polygon
// and the circle. This is the same as the difference between
// the circumscribed circle and the incircle.
let n = number_of_vertices_for_circle(tolerance, radius);
for i in 0..n {
let angle = Scalar::PI * 2. / n as f64 * i as f64;
let point = circle.point_from_circle_coords([angle]);
out.push(Local::new([angle], point));
}
}
fn number_of_vertices_for_circle(tolerance: Tolerance, radius: Scalar) -> u64 {
let n = (Scalar::PI / (Scalar::ONE - (tolerance.inner() / radius)).acos())
.ceil()
.into_u64();
max(n, 3)
}
#[cfg(test)]
mod tests {
use fj_math::Scalar;
use crate::algorithms::Tolerance;
#[test]
fn number_of_vertices_for_circle() {
verify_result(50., 100., 3);
verify_result(10., 100., 7);
verify_result(1., 100., 23);
fn verify_result(
tolerance: impl Into<Tolerance>,
radius: impl Into<Scalar>,
n: u64,
) {
let tolerance = tolerance.into();
let radius = radius.into();
assert_eq!(
n,
super::number_of_vertices_for_circle(tolerance, radius)
);
assert!(calculate_error(radius, n) <= tolerance.inner());
if n > 3 {
assert!(calculate_error(radius, n - 1) >= tolerance.inner());
}
}
fn calculate_error(radius: Scalar, n: u64) -> Scalar {
radius - radius * (Scalar::PI / Scalar::from_u64(n)).cos()
}
}
}