1#![doc(html_logo_url = "https://nical.github.io/lyon-doc/lyon-logo.svg")]
2#![deny(bare_trait_objects)]
3#![deny(unconditional_recursion)]
4#![allow(clippy::excessive_precision)]
5#![allow(clippy::let_and_return)]
6#![allow(clippy::many_single_char_names)]
7#![no_std]
8
9//! Simple 2D geometric primitives on top of euclid.
10//!
11//! This crate is reexported in [lyon](https://docs.rs/lyon/).
12//!
13//! # Overview.
14//!
15//! This crate implements some of the maths to work with:
16//!
17//! - lines and line segments,
18//! - quadratic and cubic bézier curves,
19//! - elliptic arcs,
20//! - triangles.
21//!
22//! # Flattening
23//!
24//! Flattening is the action of approximating a curve with a succession of line segments.
25//!
26//! <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 120 30" height="30mm" width="120mm">
27//! <path d="M26.7 24.94l.82-11.15M44.46 5.1L33.8 7.34" fill="none" stroke="#55d400" stroke-width=".5"/>
28//! <path d="M26.7 24.94c.97-11.13 7.17-17.6 17.76-19.84M75.27 24.94l1.13-5.5 2.67-5.48 4-4.42L88 6.7l5.02-1.6" fill="none" stroke="#000"/>
29//! <path d="M77.57 19.37a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
30//! <path d="M77.57 19.37a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="#fff"/>
31//! <path d="M80.22 13.93a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.08 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
32//! <path d="M80.22 13.93a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.08 1.08" color="#000" fill="#fff"/>
33//! <path d="M84.08 9.55a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
34//! <path d="M84.08 9.55a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
35//! <path d="M89.1 6.66a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.08-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
36//! <path d="M89.1 6.66a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.08-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="#fff"/>
37//! <path d="M94.4 5a1.1 1.1 0 0 1-1.1 1.1A1.1 1.1 0 0 1 92.23 5a1.1 1.1 0 0 1 1.08-1.08A1.1 1.1 0 0 1 94.4 5" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
38//! <path d="M94.4 5a1.1 1.1 0 0 1-1.1 1.1A1.1 1.1 0 0 1 92.23 5a1.1 1.1 0 0 1 1.08-1.08A1.1 1.1 0 0 1 94.4 5" color="#000" fill="#fff"/>
39//! <path d="M76.44 25.13a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
40//! <path d="M76.44 25.13a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
41//! <path d="M27.78 24.9a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
42//! <path d="M27.78 24.9a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
43//! <path d="M45.4 5.14a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
44//! <path d="M45.4 5.14a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="#fff"/>
45//! <path d="M28.67 13.8a1.1 1.1 0 0 1-1.1 1.08 1.1 1.1 0 0 1-1.08-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
46//! <path d="M28.67 13.8a1.1 1.1 0 0 1-1.1 1.08 1.1 1.1 0 0 1-1.08-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="#fff"/>
47//! <path d="M35 7.32a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1A1.1 1.1 0 0 1 35 7.33" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
48//! <path d="M35 7.32a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1A1.1 1.1 0 0 1 35 7.33" color="#000" fill="#fff"/>
49//! <text style="line-height:6.61458302px" x="35.74" y="284.49" font-size="5.29" font-family="Sans" letter-spacing="0" word-spacing="0" fill="#b3b3b3" stroke-width=".26" transform="translate(19.595 -267)">
50//! <tspan x="35.74" y="284.49" font-size="10.58">→</tspan>
51//! </text>
52//! </svg>
53//!
54//! The tolerance threshold taken as input by the flattening algorithms corresponds
55//! to the maximum distance between the curve and its linear approximation.
56//! The smaller the tolerance is, the more precise the approximation and the more segments
57//! are generated. This value is typically chosen in function of the zoom level.
58//!
59//! <svg viewBox="0 0 47.5 13.2" height="100" width="350" xmlns="http://www.w3.org/2000/svg">
60//! <path d="M-2.44 9.53c16.27-8.5 39.68-7.93 52.13 1.9" fill="none" stroke="#dde9af" stroke-width="4.6"/>
61//! <path d="M-1.97 9.3C14.28 1.03 37.36 1.7 49.7 11.4" fill="none" stroke="#00d400" stroke-width=".57" stroke-linecap="round" stroke-dasharray="4.6, 2.291434"/>
62//! <path d="M-1.94 10.46L6.2 6.08l28.32-1.4 15.17 6.74" fill="none" stroke="#000" stroke-width=".6"/>
63//! <path d="M6.83 6.57a.9.9 0 0 1-1.25.15.9.9 0 0 1-.15-1.25.9.9 0 0 1 1.25-.15.9.9 0 0 1 .15 1.25" color="#000" stroke="#000" stroke-width=".57" stroke-linecap="round" stroke-opacity=".5"/>
64//! <path d="M35.35 5.3a.9.9 0 0 1-1.25.15.9.9 0 0 1-.15-1.25.9.9 0 0 1 1.25-.15.9.9 0 0 1 .15 1.24" color="#000" stroke="#000" stroke-width=".6" stroke-opacity=".5"/>
65//! <g fill="none" stroke="#ff7f2a" stroke-width=".26">
66//! <path d="M20.4 3.8l.1 1.83M19.9 4.28l.48-.56.57.52M21.02 5.18l-.5.56-.6-.53" stroke-width=".2978872"/>
67//! </g>
68//! </svg>
69//!
70//! The figure above shows a close up on a curve (the dotted line) and its linear
71//! approximation (the black segments). The tolerance threshold is represented by
72//! the light green area and the orange arrow.
73//!
74
75//#![allow(needless_return)] // clippy
76
77#[cfg(any(test, feature = "std"))]
78extern crate std;
79
80// Reexport dependencies.
81pub use arrayvec;
82pub use euclid;
83
84#[cfg(feature = "serialization")]
85#[macro_use]
86pub extern crate serde;
87
88#[macro_use]
89mod segment;
90pub mod arc;
91pub mod cubic_bezier;
92mod cubic_bezier_intersections;
93mod line;
94pub mod quadratic_bezier;
95mod triangle;
96pub mod utils;
97
98#[doc(inline)]
99pub use crate::arc::{Arc, ArcFlags, SvgArc};
100#[doc(inline)]
101pub use crate::cubic_bezier::CubicBezierSegment;
102#[doc(inline)]
103pub use crate::line::{Line, LineEquation, LineSegment};
104#[doc(inline)]
105pub use crate::quadratic_bezier::QuadraticBezierSegment;
106#[doc(inline)]
107pub use crate::segment::Segment;
108#[doc(inline)]
109pub use crate::triangle::Triangle;
110
111pub use crate::scalar::Scalar;
112
113mod scalar {
114 pub(crate) use euclid::Trig;
115 pub(crate) use num_traits::cast::cast;
116 pub(crate) use num_traits::{Float, FloatConst, NumCast};
117
118 use core::fmt::{Debug, Display};
119 use core::ops::{AddAssign, DivAssign, MulAssign, SubAssign};
120
121 pub trait Scalar:
122 Float
123 + NumCast
124 + FloatConst
125 + Sized
126 + Display
127 + Debug
128 + Trig
129 + AddAssign
130 + SubAssign
131 + MulAssign
132 + DivAssign
133 {
134 const HALF: Self;
135 const ZERO: Self;
136 const ONE: Self;
137 const TWO: Self;
138 const THREE: Self;
139 const FOUR: Self;
140 const FIVE: Self;
141 const SIX: Self;
142 const SEVEN: Self;
143 const EIGHT: Self;
144 const NINE: Self;
145 const TEN: Self;
146
147 const MIN: Self;
148 const MAX: Self;
149
150 const EPSILON: Self;
151 const DIV_EPSILON: Self = Self::EPSILON;
152
153 /// Epsilon constants are usually not a good way to deal with float precision.
154 /// Float precision depends on the magnitude of the values and so should appropriate
155 /// epsilons.
156 fn epsilon_for(_reference: Self) -> Self {
157 Self::EPSILON
158 }
159
160 fn value(v: f32) -> Self;
161 }
162
163 impl Scalar for f32 {
164 const HALF: Self = 0.5;
165 const ZERO: Self = 0.0;
166 const ONE: Self = 1.0;
167 const TWO: Self = 2.0;
168 const THREE: Self = 3.0;
169 const FOUR: Self = 4.0;
170 const FIVE: Self = 5.0;
171 const SIX: Self = 6.0;
172 const SEVEN: Self = 7.0;
173 const EIGHT: Self = 8.0;
174 const NINE: Self = 9.0;
175 const TEN: Self = 10.0;
176
177 const MIN: Self = f32::MIN;
178 const MAX: Self = f32::MAX;
179
180 const EPSILON: Self = 1e-4;
181
182 fn epsilon_for(reference: Self) -> Self {
183 // The thresholds are chosen by looking at the table at
184 // https://blog.demofox.org/2017/11/21/floating-point-precision/ plus a bit
185 // of trial and error. They might change in the future.
186 // TODO: instead of casting to an integer, could look at the exponent directly.
187 let magnitude = reference.abs() as i32;
188 match magnitude {
189 0..=7 => 1e-5,
190 8..=1023 => 1e-3,
191 1024..=4095 => 1e-2,
192 5096..=65535 => 1e-1,
193 65536..=8_388_607 => 0.5,
194 _ => 1.0,
195 }
196 }
197
198 #[inline]
199 fn value(v: f32) -> Self {
200 v
201 }
202 }
203
204 // Epsilon constants are usually not a good way to deal with float precision.
205 // Float precision depends on the magnitude of the values and so should appropriate
206 // epsilons. This function addresses this somewhat empirically.
207 impl Scalar for f64 {
208 const HALF: Self = 0.5;
209 const ZERO: Self = 0.0;
210 const ONE: Self = 1.0;
211 const TWO: Self = 2.0;
212 const THREE: Self = 3.0;
213 const FOUR: Self = 4.0;
214 const FIVE: Self = 5.0;
215 const SIX: Self = 6.0;
216 const SEVEN: Self = 7.0;
217 const EIGHT: Self = 8.0;
218 const NINE: Self = 9.0;
219 const TEN: Self = 10.0;
220
221 const MIN: Self = f64::MIN;
222 const MAX: Self = f64::MAX;
223
224 const EPSILON: Self = 1e-8;
225
226 fn epsilon_for(reference: Self) -> Self {
227 let magnitude = reference.abs() as i64;
228 match magnitude {
229 0..=65_535 => 1e-8,
230 65_536..=8_388_607 => 1e-5,
231 8_388_608..=4_294_967_295 => 1e-3,
232 _ => 1e-1,
233 }
234 }
235
236 #[inline]
237 fn value(v: f32) -> Self {
238 v as f64
239 }
240 }
241}
242
243/// Alias for `euclid::default::Point2D`.
244pub use euclid::default::Point2D as Point;
245
246/// Alias for `euclid::default::Vector2D`.
247pub use euclid::default::Vector2D as Vector;
248
249/// Alias for `euclid::default::Size2D`.
250pub use euclid::default::Size2D as Size;
251
252/// Alias for `euclid::default::Box2D`
253pub use euclid::default::Box2D;
254
255/// Alias for `euclid::default::Transform2D`
256pub type Transform<S> = euclid::default::Transform2D<S>;
257
258/// Alias for `euclid::default::Rotation2D`
259pub type Rotation<S> = euclid::default::Rotation2D<S>;
260
261/// Alias for `euclid::default::Translation2D`
262pub type Translation<S> = euclid::Translation2D<S, euclid::UnknownUnit, euclid::UnknownUnit>;
263
264/// Alias for `euclid::default::Scale`
265pub use euclid::default::Scale;
266
267/// An angle in radians.
268pub use euclid::Angle;
269
270/// Shorthand for `Vector::new(x, y)`.
271#[inline]
272pub fn vector<S>(x: S, y: S) -> Vector<S> {
273 Vector::new(x, y)
274}
275
276/// Shorthand for `Point::new(x, y)`.
277#[inline]
278pub fn point<S>(x: S, y: S) -> Point<S> {
279 Point::new(x, y)
280}
281
282/// Shorthand for `Size::new(x, y)`.
283#[inline]
284pub fn size<S>(w: S, h: S) -> Size<S> {
285 Size::new(width:w, height:h)
286}
287
288pub mod traits {
289 pub use crate::segment::Segment;
290
291 use crate::{Point, Rotation, Scalar, Scale, Transform, Translation, Vector};
292
293 pub trait Transformation<S> {
294 fn transform_point(&self, p: Point<S>) -> Point<S>;
295 fn transform_vector(&self, v: Vector<S>) -> Vector<S>;
296 }
297
298 impl<S: Scalar> Transformation<S> for Transform<S> {
299 fn transform_point(&self, p: Point<S>) -> Point<S> {
300 self.transform_point(p)
301 }
302
303 fn transform_vector(&self, v: Vector<S>) -> Vector<S> {
304 self.transform_vector(v)
305 }
306 }
307
308 impl<S: Scalar> Transformation<S> for Rotation<S> {
309 fn transform_point(&self, p: Point<S>) -> Point<S> {
310 self.transform_point(p)
311 }
312
313 fn transform_vector(&self, v: Vector<S>) -> Vector<S> {
314 self.transform_vector(v)
315 }
316 }
317
318 impl<S: Scalar> Transformation<S> for Translation<S> {
319 fn transform_point(&self, p: Point<S>) -> Point<S> {
320 self.transform_point(p)
321 }
322
323 fn transform_vector(&self, v: Vector<S>) -> Vector<S> {
324 v
325 }
326 }
327
328 impl<S: Scalar> Transformation<S> for Scale<S> {
329 fn transform_point(&self, p: Point<S>) -> Point<S> {
330 (*self).transform_point(p)
331 }
332
333 fn transform_vector(&self, v: Vector<S>) -> Vector<S> {
334 (*self).transform_vector(v)
335 }
336 }
337
338 // Automatically implement Transformation for all &Transformation.
339 impl<'l, S: Scalar, T: Transformation<S>> Transformation<S> for &'l T {
340 #[inline]
341 fn transform_point(&self, p: Point<S>) -> Point<S> {
342 (*self).transform_point(p)
343 }
344
345 #[inline]
346 fn transform_vector(&self, v: Vector<S>) -> Vector<S> {
347 (*self).transform_vector(v)
348 }
349 }
350}
351