1// Copyright 2019 the Kurbo Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Implementation of circle shape.
5
6use core::{
7 f64::consts::{FRAC_PI_2, PI},
8 iter,
9 ops::{Add, Mul, Sub},
10};
11
12use crate::{Affine, Arc, ArcAppendIter, Ellipse, PathEl, Point, Rect, Shape, Vec2};
13
14#[cfg(not(feature = "std"))]
15use crate::common::FloatFuncs;
16
17/// A circle.
18#[derive(Clone, Copy, Default, Debug, PartialEq)]
19#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
20#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
21pub struct Circle {
22 /// The center.
23 pub center: Point,
24 /// The radius.
25 pub radius: f64,
26}
27
28impl Circle {
29 /// A new circle from center and radius.
30 #[inline]
31 pub fn new(center: impl Into<Point>, radius: f64) -> Circle {
32 Circle {
33 center: center.into(),
34 radius,
35 }
36 }
37
38 /// Create a [`CircleSegment`] by cutting out parts of this circle.
39 pub fn segment(self, inner_radius: f64, start_angle: f64, sweep_angle: f64) -> CircleSegment {
40 CircleSegment {
41 center: self.center,
42 outer_radius: self.radius,
43 inner_radius,
44 start_angle,
45 sweep_angle,
46 }
47 }
48
49 /// Is this circle finite?
50 #[inline]
51 pub fn is_finite(&self) -> bool {
52 self.center.is_finite() && self.radius.is_finite()
53 }
54
55 /// Is this circle NaN?
56 #[inline]
57 pub fn is_nan(&self) -> bool {
58 self.center.is_nan() || self.radius.is_nan()
59 }
60}
61
62impl Add<Vec2> for Circle {
63 type Output = Circle;
64
65 #[inline]
66 fn add(self, v: Vec2) -> Circle {
67 Circle {
68 center: self.center + v,
69 radius: self.radius,
70 }
71 }
72}
73
74impl Sub<Vec2> for Circle {
75 type Output = Circle;
76
77 #[inline]
78 fn sub(self, v: Vec2) -> Circle {
79 Circle {
80 center: self.center - v,
81 radius: self.radius,
82 }
83 }
84}
85
86impl Mul<Circle> for Affine {
87 type Output = Ellipse;
88 fn mul(self, other: Circle) -> Self::Output {
89 self * Ellipse::from(other)
90 }
91}
92
93#[doc(hidden)]
94pub struct CirclePathIter {
95 circle: Circle,
96 delta_th: f64,
97 arm_len: f64,
98 ix: usize,
99 n: usize,
100}
101
102impl Shape for Circle {
103 type PathElementsIter<'iter> = CirclePathIter;
104
105 fn path_elements(&self, tolerance: f64) -> CirclePathIter {
106 let scaled_err = self.radius.abs() / tolerance;
107 let (n, arm_len) = if scaled_err < 1.0 / 1.9608e-4 {
108 // Solution from http://spencermortensen.com/articles/bezier-circle/
109 (4, 0.551915024494)
110 } else {
111 // This is empirically determined to fall within error tolerance.
112 let n = (1.1163 * scaled_err).powf(1.0 / 6.0).ceil() as usize;
113 // Note: this isn't minimum error, but it is simple and we can easily
114 // estimate the error.
115 let arm_len = (4.0 / 3.0) * (FRAC_PI_2 / (n as f64)).tan();
116 (n, arm_len)
117 };
118 CirclePathIter {
119 circle: *self,
120 delta_th: 2.0 * PI / (n as f64),
121 arm_len,
122 ix: 0,
123 n,
124 }
125 }
126
127 #[inline]
128 fn area(&self) -> f64 {
129 PI * self.radius.powi(2)
130 }
131
132 #[inline]
133 fn perimeter(&self, _accuracy: f64) -> f64 {
134 (2.0 * PI * self.radius).abs()
135 }
136
137 fn winding(&self, pt: Point) -> i32 {
138 if (pt - self.center).hypot2() < self.radius.powi(2) {
139 1
140 } else {
141 0
142 }
143 }
144
145 #[inline]
146 fn bounding_box(&self) -> Rect {
147 let r = self.radius.abs();
148 let (x, y) = self.center.into();
149 Rect::new(x - r, y - r, x + r, y + r)
150 }
151
152 fn as_circle(&self) -> Option<Circle> {
153 Some(*self)
154 }
155}
156
157impl Iterator for CirclePathIter {
158 type Item = PathEl;
159
160 fn next(&mut self) -> Option<PathEl> {
161 let a = self.arm_len;
162 let r = self.circle.radius;
163 let (x, y) = self.circle.center.into();
164 let ix = self.ix;
165 self.ix += 1;
166 if ix == 0 {
167 Some(PathEl::MoveTo(Point::new(x + r, y)))
168 } else if ix <= self.n {
169 let th1 = self.delta_th * (ix as f64);
170 let th0 = th1 - self.delta_th;
171 let (s0, c0) = th0.sin_cos();
172 let (s1, c1) = if ix == self.n {
173 (0.0, 1.0)
174 } else {
175 th1.sin_cos()
176 };
177 Some(PathEl::CurveTo(
178 Point::new(x + r * (c0 - a * s0), y + r * (s0 + a * c0)),
179 Point::new(x + r * (c1 + a * s1), y + r * (s1 - a * c1)),
180 Point::new(x + r * c1, y + r * s1),
181 ))
182 } else if ix == self.n + 1 {
183 Some(PathEl::ClosePath)
184 } else {
185 None
186 }
187 }
188}
189
190/// A segment of a circle.
191///
192/// If `inner_radius > 0`, then the shape will be a doughnut segment.
193pub struct CircleSegment {
194 /// The center.
195 pub center: Point,
196 /// The outer radius.
197 pub outer_radius: f64,
198 /// The inner radius.
199 pub inner_radius: f64,
200 /// The angle to start drawing the segment (in radians).
201 pub start_angle: f64,
202 /// The arc length of the segment (in radians).
203 pub sweep_angle: f64,
204}
205
206impl CircleSegment {
207 /// Create a `CircleSegment` out of its constituent parts.
208 pub fn new(
209 center: impl Into<Point>,
210 outer_radius: f64,
211 inner_radius: f64,
212 start_angle: f64,
213 sweep_angle: f64,
214 ) -> Self {
215 CircleSegment {
216 center: center.into(),
217 outer_radius,
218 inner_radius,
219 start_angle,
220 sweep_angle,
221 }
222 }
223
224 /// Is this circle segment finite?
225 #[inline]
226 pub fn is_finite(&self) -> bool {
227 self.center.is_finite()
228 && self.outer_radius.is_finite()
229 && self.inner_radius.is_finite()
230 && self.start_angle.is_finite()
231 && self.sweep_angle.is_finite()
232 }
233
234 /// Is this circle segment NaN?
235 #[inline]
236 pub fn is_nan(&self) -> bool {
237 self.center.is_nan()
238 || self.outer_radius.is_nan()
239 || self.inner_radius.is_nan()
240 || self.start_angle.is_nan()
241 || self.sweep_angle.is_nan()
242 }
243}
244
245impl Add<Vec2> for CircleSegment {
246 type Output = CircleSegment;
247
248 #[inline]
249 fn add(self, v: Vec2) -> Self {
250 Self {
251 center: self.center + v,
252 ..self
253 }
254 }
255}
256
257impl Sub<Vec2> for CircleSegment {
258 type Output = CircleSegment;
259
260 #[inline]
261 fn sub(self, v: Vec2) -> Self {
262 Self {
263 center: self.center - v,
264 ..self
265 }
266 }
267}
268
269type CircleSegmentPathIter = iter::Chain<
270 iter::Chain<
271 iter::Chain<iter::Chain<iter::Once<PathEl>, iter::Once<PathEl>>, ArcAppendIter>,
272 iter::Once<PathEl>,
273 >,
274 ArcAppendIter,
275>;
276
277impl Shape for CircleSegment {
278 type PathElementsIter<'iter> = CircleSegmentPathIter;
279
280 fn path_elements(&self, tolerance: f64) -> CircleSegmentPathIter {
281 iter::once(PathEl::MoveTo(point_on_circle(
282 self.center,
283 self.inner_radius,
284 self.start_angle,
285 )))
286 // First radius
287 .chain(iter::once(PathEl::LineTo(point_on_circle(
288 self.center,
289 self.outer_radius,
290 self.start_angle,
291 ))))
292 // outer arc
293 .chain(
294 Arc {
295 center: self.center,
296 radii: Vec2::new(self.outer_radius, self.outer_radius),
297 start_angle: self.start_angle,
298 sweep_angle: self.sweep_angle,
299 x_rotation: 0.0,
300 }
301 .append_iter(tolerance),
302 )
303 // second radius
304 .chain(iter::once(PathEl::LineTo(point_on_circle(
305 self.center,
306 self.inner_radius,
307 self.start_angle + self.sweep_angle,
308 ))))
309 // inner arc
310 .chain(
311 Arc {
312 center: self.center,
313 radii: Vec2::new(self.inner_radius, self.inner_radius),
314 start_angle: self.start_angle + self.sweep_angle,
315 sweep_angle: -self.sweep_angle,
316 x_rotation: 0.0,
317 }
318 .append_iter(tolerance),
319 )
320 }
321
322 #[inline]
323 fn area(&self) -> f64 {
324 0.5 * (self.outer_radius.powi(2) - self.inner_radius.powi(2)).abs() * self.sweep_angle
325 }
326
327 #[inline]
328 fn perimeter(&self, _accuracy: f64) -> f64 {
329 2.0 * (self.outer_radius - self.inner_radius).abs()
330 + self.sweep_angle * (self.inner_radius + self.outer_radius)
331 }
332
333 fn winding(&self, pt: Point) -> i32 {
334 let angle = (pt - self.center).atan2();
335 if angle < self.start_angle || angle > self.start_angle + self.sweep_angle {
336 return 0;
337 }
338 let dist2 = (pt - self.center).hypot2();
339 if (dist2 < self.outer_radius.powi(2) && dist2 > self.inner_radius.powi(2)) ||
340 // case where outer_radius < inner_radius
341 (dist2 < self.inner_radius.powi(2) && dist2 > self.outer_radius.powi(2))
342 {
343 1
344 } else {
345 0
346 }
347 }
348
349 #[inline]
350 fn bounding_box(&self) -> Rect {
351 // todo this is currently not tight
352 let r = self.inner_radius.max(self.outer_radius);
353 let (x, y) = self.center.into();
354 Rect::new(x - r, y - r, x + r, y + r)
355 }
356}
357
358#[cfg(test)]
359mod tests {
360 use crate::{Circle, Point, Shape};
361 use std::f64::consts::PI;
362
363 fn assert_approx_eq(x: f64, y: f64) {
364 // Note: we might want to be more rigorous in testing the accuracy
365 // of the conversion into Béziers. But this seems good enough.
366 assert!((x - y).abs() < 1e-7, "{x} != {y}");
367 }
368
369 #[test]
370 fn area_sign() {
371 let center = Point::new(5.0, 5.0);
372 let c = Circle::new(center, 5.0);
373 assert_approx_eq(c.area(), 25.0 * PI);
374
375 assert_eq!(c.winding(center), 1);
376
377 let p = c.to_path(1e-9);
378 assert_approx_eq(c.area(), p.area());
379 assert_eq!(c.winding(center), p.winding(center));
380
381 let c_neg_radius = Circle::new(center, -5.0);
382 assert_approx_eq(c_neg_radius.area(), 25.0 * PI);
383
384 assert_eq!(c_neg_radius.winding(center), 1);
385
386 let p_neg_radius = c_neg_radius.to_path(1e-9);
387 assert_approx_eq(c_neg_radius.area(), p_neg_radius.area());
388 assert_eq!(c_neg_radius.winding(center), p_neg_radius.winding(center));
389 }
390}
391
392#[inline]
393fn point_on_circle(center: Point, radius: f64, angle: f64) -> Point {
394 let (angle_sin: f64, angle_cos: f64) = angle.sin_cos();
395 center
396 + Vec2 {
397 x: angle_cos * radius,
398 y: angle_sin * radius,
399 }
400}
401