#![allow(clippy::many_single_char_names)]
use std::iter::{Extend, FromIterator};
use std::ops::{Mul, Range};
use arrayvec::ArrayVec;
use crate::common::{solve_cubic, solve_quadratic};
use crate::MAX_EXTREMA;
use crate::{
Affine, CubicBez, Line, ParamCurve, ParamCurveArclen, ParamCurveArea, ParamCurveExtrema,
ParamCurveNearest, Point, QuadBez, Rect, Shape, TranslateScale,
};
#[derive(Clone, Default, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct BezPath(Vec<PathEl>);
#[derive(Clone, Copy, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum PathEl {
MoveTo(Point),
LineTo(Point),
QuadTo(Point, Point),
CurveTo(Point, Point, Point),
ClosePath,
}
#[derive(Clone, Copy, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum PathSeg {
Line(Line),
Quad(QuadBez),
Cubic(CubicBez),
}
#[derive(Debug, Clone, Copy)]
pub struct LineIntersection {
pub line_t: f64,
pub segment_t: f64,
}
impl BezPath {
pub fn new() -> BezPath {
Default::default()
}
pub fn from_vec(v: Vec<PathEl>) -> BezPath {
BezPath(v)
}
pub fn push(&mut self, el: PathEl) {
self.0.push(el)
}
pub fn move_to<P: Into<Point>>(&mut self, p: P) {
self.push(PathEl::MoveTo(p.into()));
}
pub fn line_to<P: Into<Point>>(&mut self, p: P) {
self.push(PathEl::LineTo(p.into()));
}
pub fn quad_to<P: Into<Point>>(&mut self, p1: P, p2: P) {
self.push(PathEl::QuadTo(p1.into(), p2.into()));
}
pub fn curve_to<P: Into<Point>>(&mut self, p1: P, p2: P, p3: P) {
self.push(PathEl::CurveTo(p1.into(), p2.into(), p3.into()));
}
pub fn close_path(&mut self) {
self.push(PathEl::ClosePath);
}
pub fn elements(&self) -> &[PathEl] {
&self.0
}
pub fn iter(&self) -> impl Iterator<Item = PathEl> + '_ {
self.0.iter().copied()
}
pub fn segments(&self) -> impl Iterator<Item = PathSeg> + '_ {
BezPath::segments_of_slice(&self.0)
}
pub fn flatten(&self, tolerance: f64, callback: impl FnMut(PathEl)) {
flatten(self, tolerance, callback);
}
fn segments_of_slice(slice: &[PathEl]) -> BezPathSegs {
let first = match slice.get(0) {
Some(PathEl::MoveTo(p)) => *p,
Some(PathEl::LineTo(p)) => *p,
Some(PathEl::QuadTo(_, p2)) => *p2,
Some(PathEl::CurveTo(_, _, p3)) => *p3,
Some(PathEl::ClosePath) => panic!("Can't start a segment on a ClosePath"),
None => Default::default(),
};
BezPathSegs {
c: slice.iter(),
start: first,
last: first,
}
}
pub fn get_seg(&self, ix: usize) -> Option<PathSeg> {
if ix == 0 || ix >= self.0.len() {
return None;
}
let last = match self.0[ix - 1] {
PathEl::MoveTo(p) => p,
PathEl::LineTo(p) => p,
PathEl::QuadTo(_, p2) => p2,
PathEl::CurveTo(_, _, p3) => p3,
_ => return None,
};
match self.0[ix] {
PathEl::LineTo(p) => Some(PathSeg::Line(Line::new(last, p))),
PathEl::QuadTo(p1, p2) => Some(PathSeg::Quad(QuadBez::new(last, p1, p2))),
PathEl::CurveTo(p1, p2, p3) => Some(PathSeg::Cubic(CubicBez::new(last, p1, p2, p3))),
PathEl::ClosePath => self.0[..ix].iter().rev().find_map(|el| match *el {
PathEl::MoveTo(start) => Some(PathSeg::Line(Line::new(last, start))),
_ => None,
}),
_ => None,
}
}
pub fn is_empty(&self) -> bool {
!self.0.iter().any(|el| match *el {
PathEl::LineTo(..) | PathEl::QuadTo(..) | PathEl::CurveTo(..) => true,
_ => false,
})
}
pub fn apply_affine(&mut self, affine: Affine) {
for el in self.0.iter_mut() {
*el = affine * (*el);
}
}
pub fn nearest(&self, p: Point, accuracy: f64) -> (usize, f64, f64) {
let mut best = None;
for (ix, seg) in self.segments().enumerate() {
let (t, r) = seg.nearest(p, accuracy);
if best.map(|(_, _, r_best)| r < r_best).unwrap_or(true) {
best = Some((ix, t, r));
}
}
best.unwrap()
}
}
impl FromIterator<PathEl> for BezPath {
fn from_iter<T: IntoIterator<Item = PathEl>>(iter: T) -> Self {
let el_vec: Vec<_> = iter.into_iter().collect();
BezPath::from_vec(el_vec)
}
}
impl<'a> IntoIterator for &'a BezPath {
type Item = PathEl;
type IntoIter = std::iter::Cloned<std::slice::Iter<'a, PathEl>>;
fn into_iter(self) -> Self::IntoIter {
self.elements().iter().cloned()
}
}
impl IntoIterator for BezPath {
type Item = PathEl;
type IntoIter = std::vec::IntoIter<PathEl>;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter()
}
}
impl Extend<PathEl> for BezPath {
fn extend<I: IntoIterator<Item = PathEl>>(&mut self, iter: I) {
self.0.extend(iter);
}
}
const TO_QUAD_TOL: f64 = 0.1;
pub fn flatten(
path: impl IntoIterator<Item = PathEl>,
tolerance: f64,
mut callback: impl FnMut(PathEl),
) {
let sqrt_tol = tolerance.sqrt();
let mut last_pt = None;
let mut quad_buf = Vec::new();
for el in path {
match el {
PathEl::MoveTo(p) => {
last_pt = Some(p);
callback(PathEl::MoveTo(p));
}
PathEl::LineTo(p) => {
last_pt = Some(p);
callback(PathEl::LineTo(p));
}
PathEl::QuadTo(p1, p2) => {
if let Some(p0) = last_pt {
let q = QuadBez::new(p0, p1, p2);
let params = q.estimate_subdiv(sqrt_tol);
let n = ((0.5 * params.val / sqrt_tol).ceil() as usize).max(1);
let step = 1.0 / (n as f64);
for i in 1..(n - 1) {
let u = (i as f64) * step;
let t = q.determine_subdiv_t(¶ms, u);
let p = q.eval(t);
callback(PathEl::LineTo(p));
}
callback(PathEl::LineTo(p2));
}
last_pt = Some(p2);
}
PathEl::CurveTo(p1, p2, p3) => {
if let Some(p0) = last_pt {
let c = CubicBez::new(p0, p1, p2, p3);
let iter = c.to_quads(tolerance * TO_QUAD_TOL);
quad_buf.clear();
quad_buf.reserve(iter.size_hint().0);
let sqrt_remain_tol = sqrt_tol * (1.0 - TO_QUAD_TOL).sqrt();
let mut sum = 0.0;
for (_, _, q) in iter {
let params = q.estimate_subdiv(sqrt_remain_tol);
sum += params.val;
quad_buf.push((q, params));
}
let n = ((0.5 * sum / sqrt_remain_tol).ceil() as usize).max(1);
let step = sum / (n as f64);
let mut i = 1;
let mut val_sum = 0.0;
for (q, params) in &quad_buf {
let mut target = (i as f64) * step;
let recip_val = params.val.recip();
while target < val_sum + params.val {
let u = (target - val_sum) * recip_val;
let t = q.determine_subdiv_t(¶ms, u);
let p = q.eval(t);
callback(PathEl::LineTo(p));
i += 1;
if i == n + 1 {
break;
}
target = (i as f64) * step;
}
val_sum += params.val;
}
callback(PathEl::LineTo(p3));
}
last_pt = Some(p3);
}
PathEl::ClosePath => {
last_pt = None;
callback(PathEl::ClosePath);
}
}
}
}
impl Mul<PathEl> for Affine {
type Output = PathEl;
fn mul(self, other: PathEl) -> PathEl {
match other {
PathEl::MoveTo(p) => PathEl::MoveTo(self * p),
PathEl::LineTo(p) => PathEl::LineTo(self * p),
PathEl::QuadTo(p1, p2) => PathEl::QuadTo(self * p1, self * p2),
PathEl::CurveTo(p1, p2, p3) => PathEl::CurveTo(self * p1, self * p2, self * p3),
PathEl::ClosePath => PathEl::ClosePath,
}
}
}
impl Mul<BezPath> for Affine {
type Output = BezPath;
fn mul(self, other: BezPath) -> BezPath {
BezPath(other.0.iter().map(|&el| self * el).collect())
}
}
impl<'a> Mul<&'a BezPath> for Affine {
type Output = BezPath;
fn mul(self, other: &BezPath) -> BezPath {
BezPath(other.0.iter().map(|&el| self * el).collect())
}
}
impl Mul<PathEl> for TranslateScale {
type Output = PathEl;
fn mul(self, other: PathEl) -> PathEl {
match other {
PathEl::MoveTo(p) => PathEl::MoveTo(self * p),
PathEl::LineTo(p) => PathEl::LineTo(self * p),
PathEl::QuadTo(p1, p2) => PathEl::QuadTo(self * p1, self * p2),
PathEl::CurveTo(p1, p2, p3) => PathEl::CurveTo(self * p1, self * p2, self * p3),
PathEl::ClosePath => PathEl::ClosePath,
}
}
}
impl Mul<BezPath> for TranslateScale {
type Output = BezPath;
fn mul(self, other: BezPath) -> BezPath {
BezPath(other.0.iter().map(|&el| self * el).collect())
}
}
impl<'a> Mul<&'a BezPath> for TranslateScale {
type Output = BezPath;
fn mul(self, other: &BezPath) -> BezPath {
BezPath(other.0.iter().map(|&el| self * el).collect())
}
}
struct BezPathSegs<'a> {
c: std::slice::Iter<'a, PathEl>,
start: Point,
last: Point,
}
impl<'a> Iterator for BezPathSegs<'a> {
type Item = PathSeg;
fn next(&mut self) -> Option<PathSeg> {
for el in &mut self.c {
let (ret, last) = match *el {
PathEl::MoveTo(p) => {
self.start = p;
self.last = p;
continue;
}
PathEl::LineTo(p) => (PathSeg::Line(Line::new(self.last, p)), p),
PathEl::QuadTo(p1, p2) => (PathSeg::Quad(QuadBez::new(self.last, p1, p2)), p2),
PathEl::CurveTo(p1, p2, p3) => {
(PathSeg::Cubic(CubicBez::new(self.last, p1, p2, p3)), p3)
}
PathEl::ClosePath => {
if self.last != self.start {
(PathSeg::Line(Line::new(self.last, self.start)), self.start)
} else {
continue;
}
}
};
self.last = last;
return Some(ret);
}
None
}
}
impl<'a> BezPathSegs<'a> {
fn arclen(self, accuracy: f64) -> f64 {
self.map(|seg| seg.arclen(accuracy)).sum()
}
fn area(self) -> f64 {
self.map(|seg| seg.signed_area()).sum()
}
fn winding(self, p: Point) -> i32 {
self.map(|seg| seg.winding(p)).sum()
}
fn bounding_box(self) -> Rect {
let mut bbox: Option<Rect> = None;
for seg in self {
let seg_bb = seg.bounding_box();
if let Some(bb) = bbox {
bbox = Some(bb.union(seg_bb));
} else {
bbox = Some(seg_bb)
}
}
bbox.unwrap_or_default()
}
}
impl ParamCurve for PathSeg {
fn eval(&self, t: f64) -> Point {
match *self {
PathSeg::Line(line) => line.eval(t),
PathSeg::Quad(quad) => quad.eval(t),
PathSeg::Cubic(cubic) => cubic.eval(t),
}
}
fn subsegment(&self, range: Range<f64>) -> PathSeg {
match *self {
PathSeg::Line(line) => PathSeg::Line(line.subsegment(range)),
PathSeg::Quad(quad) => PathSeg::Quad(quad.subsegment(range)),
PathSeg::Cubic(cubic) => PathSeg::Cubic(cubic.subsegment(range)),
}
}
}
impl ParamCurveArclen for PathSeg {
fn arclen(&self, accuracy: f64) -> f64 {
match *self {
PathSeg::Line(line) => line.arclen(accuracy),
PathSeg::Quad(quad) => quad.arclen(accuracy),
PathSeg::Cubic(cubic) => cubic.arclen(accuracy),
}
}
}
impl ParamCurveArea for PathSeg {
fn signed_area(&self) -> f64 {
match *self {
PathSeg::Line(line) => line.signed_area(),
PathSeg::Quad(quad) => quad.signed_area(),
PathSeg::Cubic(cubic) => cubic.signed_area(),
}
}
}
impl ParamCurveNearest for PathSeg {
fn nearest(&self, p: Point, accuracy: f64) -> (f64, f64) {
match *self {
PathSeg::Line(line) => line.nearest(p, accuracy),
PathSeg::Quad(quad) => quad.nearest(p, accuracy),
PathSeg::Cubic(cubic) => cubic.nearest(p, accuracy),
}
}
}
impl ParamCurveExtrema for PathSeg {
fn extrema(&self) -> ArrayVec<[f64; MAX_EXTREMA]> {
match *self {
PathSeg::Line(line) => line.extrema(),
PathSeg::Quad(quad) => quad.extrema(),
PathSeg::Cubic(cubic) => cubic.extrema(),
}
}
}
impl PathSeg {
pub fn reverse(&self) -> PathSeg {
match self {
PathSeg::Line(Line { p0, p1 }) => PathSeg::Line(Line::new(*p1, *p0)),
PathSeg::Quad(q) => PathSeg::Quad(QuadBez::new(q.p2, q.p1, q.p0)),
PathSeg::Cubic(c) => PathSeg::Cubic(CubicBez::new(c.p3, c.p2, c.p1, c.p0)),
}
}
pub fn to_cubic(&self) -> CubicBez {
match *self {
PathSeg::Line(Line { p0, p1 }) => CubicBez::new(p0, p0, p1, p1),
PathSeg::Cubic(c) => c,
PathSeg::Quad(q) => q.raise(),
}
}
fn winding_inner(&self, p: Point) -> i32 {
let start = self.start();
let end = self.end();
let sign = if end.y > start.y {
if p.y < start.y || p.y >= end.y {
return 0;
}
-1
} else if end.y < start.y {
if p.y < end.y || p.y >= start.y {
return 0;
}
1
} else {
return 0;
};
match *self {
PathSeg::Line(_line) => {
if p.x < start.x.min(end.x) {
return 0;
}
if p.x >= start.x.max(end.x) {
return sign;
}
let a = end.y - start.y;
let b = start.x - end.x;
let c = a * start.x + b * start.y;
if (a * p.x + b * p.y - c) * (sign as f64) >= 0.0 {
sign
} else {
0
}
}
PathSeg::Quad(quad) => {
let p1 = quad.p1;
if p.x < start.x.min(end.x).min(p1.x) {
return 0;
}
if p.x >= start.x.max(end.x).max(p1.x) {
return sign;
}
let a = end.y - 2.0 * p1.y + start.y;
let b = 2.0 * (p1.y - start.y);
let c = start.y - p.y;
for t in solve_quadratic(c, b, a) {
if t >= 0.0 && t <= 1.0 {
let x = quad.eval(t).x;
if p.x >= x {
return sign;
} else {
return 0;
}
}
}
0
}
PathSeg::Cubic(cubic) => {
let p1 = cubic.p1;
let p2 = cubic.p2;
if p.x < start.x.min(end.x).min(p1.x).min(p2.x) {
return 0;
}
if p.x >= start.x.max(end.x).max(p1.x).max(p2.x) {
return sign;
}
let a = end.y - 3.0 * p2.y + 3.0 * p1.y - start.y;
let b = 3.0 * (p2.y - 2.0 * p1.y + start.y);
let c = 3.0 * (p1.y - start.y);
let d = start.y - p.y;
for t in solve_cubic(d, c, b, a) {
if t >= 0.0 && t <= 1.0 {
let x = cubic.eval(t).x;
if p.x >= x {
return sign;
} else {
return 0;
}
}
}
0
}
}
}
fn winding(&self, p: Point) -> i32 {
self.extrema_ranges()
.into_iter()
.map(|range| self.subsegment(range).winding_inner(p))
.sum()
}
pub fn intersect_line(&self, line: Line) -> ArrayVec<[LineIntersection; 3]> {
const EPSILON: f64 = 1e-9;
let p0 = line.p0;
let p1 = line.p1;
let dx = p1.x - p0.x;
let dy = p1.y - p0.y;
let mut result = ArrayVec::new();
match self {
PathSeg::Line(l) => {
let det = dx * (l.p1.y - l.p0.y) - dy * (l.p1.x - l.p0.x);
if det.abs() < EPSILON {
return result;
}
let t = dx * (p0.y - l.p0.y) - dy * (p0.x - l.p0.x);
let t = t / det;
if t >= -EPSILON && t <= 1.0 + EPSILON {
let u =
(l.p0.x - p0.x) * (l.p1.y - l.p0.y) - (l.p0.y - p0.y) * (l.p1.x - l.p0.x);
let u = u / det;
if u >= 0.0 && u <= 1.0 {
result.push(LineIntersection::new(u, t));
}
}
}
PathSeg::Quad(q) => {
let (px0, px1, px2) = quadratic_bez_coefs(q.p0.x, q.p1.x, q.p2.x);
let (py0, py1, py2) = quadratic_bez_coefs(q.p0.y, q.p1.y, q.p2.y);
let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
let c1 = dy * px1 - dx * py1;
let c2 = dy * px2 - dx * py2;
let invlen2 = (dx * dx + dy * dy).recip();
for t in crate::common::solve_quadratic(c0, c1, c2) {
if t >= -EPSILON && t <= 1.0 + EPSILON {
let x = px0 + t * px1 + t * t * px2;
let y = py0 + t * py1 + t * t * py2;
let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
if u >= 0.0 && u <= 1.0 {
result.push(LineIntersection::new(u, t));
}
}
}
}
PathSeg::Cubic(c) => {
let (px0, px1, px2, px3) = cubic_bez_coefs(c.p0.x, c.p1.x, c.p2.x, c.p3.x);
let (py0, py1, py2, py3) = cubic_bez_coefs(c.p0.y, c.p1.y, c.p2.y, c.p3.y);
let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
let c1 = dy * px1 - dx * py1;
let c2 = dy * px2 - dx * py2;
let c3 = dy * px3 - dx * py3;
let invlen2 = (dx * dx + dy * dy).recip();
for t in crate::common::solve_cubic(c0, c1, c2, c3) {
if t >= -EPSILON && t <= 1.0 + EPSILON {
let x = px0 + t * px1 + t * t * px2 + t * t * t * px3;
let y = py0 + t * py1 + t * t * py2 + t * t * t * py3;
let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
if u >= 0.0 && u <= 1.0 {
result.push(LineIntersection::new(u, t));
}
}
}
}
}
result
}
}
impl LineIntersection {
fn new(line_t: f64, segment_t: f64) -> Self {
LineIntersection { line_t, segment_t }
}
}
fn quadratic_bez_coefs(x0: f64, x1: f64, x2: f64) -> (f64, f64, f64) {
let p0 = x0;
let p1 = 2.0 * x1 - 2.0 * x0;
let p2 = x2 - 2.0 * x1 + x0;
(p0, p1, p2)
}
fn cubic_bez_coefs(x0: f64, x1: f64, x2: f64, x3: f64) -> (f64, f64, f64, f64) {
let p0 = x0;
let p1 = 3.0 * x1 - 3.0 * x0;
let p2 = 3.0 * x2 - 6.0 * x1 + 3.0 * x0;
let p3 = x3 - 3.0 * x2 + 3.0 * x1 - x0;
(p0, p1, p2, p3)
}
impl From<CubicBez> for PathSeg {
fn from(cubic_bez: CubicBez) -> PathSeg {
PathSeg::Cubic(cubic_bez)
}
}
impl From<Line> for PathSeg {
fn from(line: Line) -> PathSeg {
PathSeg::Line(line)
}
}
impl From<QuadBez> for PathSeg {
fn from(quad_bez: QuadBez) -> PathSeg {
PathSeg::Quad(quad_bez)
}
}
impl Shape for BezPath {
type BezPathIter = std::vec::IntoIter<PathEl>;
fn to_bez_path(&self, _tolerance: f64) -> Self::BezPathIter {
self.clone().0.into_iter()
}
fn area(&self) -> f64 {
self.elements().area()
}
fn perimeter(&self, accuracy: f64) -> f64 {
self.elements().perimeter(accuracy)
}
fn winding(&self, pt: Point) -> i32 {
self.elements().winding(pt)
}
fn bounding_box(&self) -> Rect {
self.elements().bounding_box()
}
fn as_path_slice(&self) -> Option<&[PathEl]> {
Some(&self.0)
}
}
impl<'a> Shape for &'a [PathEl] {
type BezPathIter = std::iter::Cloned<std::slice::Iter<'a, PathEl>>;
#[inline]
fn to_bez_path(&self, _tolerance: f64) -> Self::BezPathIter {
self.iter().cloned()
}
fn area(&self) -> f64 {
BezPath::segments_of_slice(self).area()
}
fn perimeter(&self, accuracy: f64) -> f64 {
BezPath::segments_of_slice(self).arclen(accuracy)
}
fn winding(&self, pt: Point) -> i32 {
BezPath::segments_of_slice(self).winding(pt)
}
fn bounding_box(&self) -> Rect {
BezPath::segments_of_slice(self).bounding_box()
}
#[inline]
fn as_path_slice(&self) -> Option<&[PathEl]> {
Some(self)
}
}
#[cfg(test)]
mod tests {
use super::{CubicBez, Line, PathSeg, QuadBez};
fn assert_approx_eq(x: f64, y: f64) {
assert!((x - y).abs() < 1e-8, "{} != {}", x, y);
}
#[test]
fn test_intersect_line() {
let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
let intersection = PathSeg::Line(h_line).intersect_line(v_line)[0];
assert_approx_eq(intersection.segment_t, 0.1);
assert_approx_eq(intersection.line_t, 0.5);
let v_line = Line::new((-10.0, -10.0), (-10.0, 10.0));
assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
let v_line = Line::new((10.0, 10.0), (10.0, 20.0));
assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
}
#[test]
fn test_intersect_qad() {
let q = QuadBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -10.0));
let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
assert_eq!(PathSeg::Quad(q).intersect_line(v_line).len(), 1);
let intersection = PathSeg::Quad(q).intersect_line(v_line)[0];
assert_approx_eq(intersection.segment_t, 0.5);
assert_approx_eq(intersection.line_t, 0.75);
let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
assert_eq!(PathSeg::Quad(q).intersect_line(h_line).len(), 2);
}
#[test]
fn test_intersect_cubic() {
let c = CubicBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -20.0), (30.0, 10.0));
let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
assert_eq!(PathSeg::Cubic(c).intersect_line(v_line).len(), 1);
let intersection = PathSeg::Cubic(c).intersect_line(v_line)[0];
assert_approx_eq(intersection.segment_t, 0.333333333);
assert_approx_eq(intersection.line_t, 0.592592592);
let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
assert_eq!(PathSeg::Cubic(c).intersect_line(h_line).len(), 3);
}
}