mod archive;
mod builder;
mod collection;
mod contains;
pub mod convert;
mod extents;
mod intersect;
pub mod outline;
mod polygons;
mod shapes;
mod svg;
use std::fmt;
pub use builder::PathBuilder;
pub use collection::{CollectionError, CollectionGeometry};
pub use extents::{DataLimits, count_overlapping};
pub use polygons::PolygonOptions;
pub use svg::SvgPathError;
use crate::bezier::{Bezier, BezierSegment};
use crate::{Affine2D, Bbox, Point};
pub const MAX_INTERPOLATED_VERTICES: usize = 1 << 22;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[repr(u8)]
pub enum PathCode {
MoveTo = 1,
LineTo = 2,
Curve3 = 3,
Curve4 = 4,
ClosePoly = 79,
}
impl PathCode {
pub const fn vertex_count(self) -> usize {
match self {
Self::MoveTo | Self::LineTo | Self::ClosePoly => 1,
Self::Curve3 => 2,
Self::Curve4 => 3,
}
}
}
impl TryFrom<u8> for PathCode {
type Error = PathError;
fn try_from(value: u8) -> Result<Self, PathError> {
Ok(match value {
1 => Self::MoveTo,
2 => Self::LineTo,
3 => Self::Curve3,
4 => Self::Curve4,
79 => Self::ClosePoly,
other => return Err(PathError::UnknownCode(other)),
})
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Segment {
MoveTo(Point),
LineTo(Point),
QuadTo(Point, Point),
CubicTo(Point, Point, Point),
Close,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum PathError {
LengthMismatch {
vertices: usize,
codes: usize,
},
MissingInitialMove,
UnknownCode(u8),
}
impl fmt::Display for PathError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::LengthMismatch { vertices, codes } => write!(
f,
"path has {vertices} vertices but {codes} codes; they must match"
),
Self::MissingInitialMove => f.write_str("the first path code must be MOVETO"),
Self::UnknownCode(code) => write!(f, "unknown path code {code}"),
}
}
}
impl std::error::Error for PathError {}
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Path {
vertices: Vec<Point>,
codes: Option<Vec<PathCode>>,
interpolation_steps: usize,
}
impl Path {
pub fn new(vertices: Vec<Point>, codes: Vec<PathCode>) -> Result<Self, PathError> {
if vertices.len() != codes.len() {
return Err(PathError::LengthMismatch {
vertices: vertices.len(),
codes: codes.len(),
});
}
if codes.first().is_some_and(|c| *c != PathCode::MoveTo) {
return Err(PathError::MissingInitialMove);
}
Ok(Self {
vertices,
codes: Some(codes),
interpolation_steps: 1,
})
}
pub fn polyline(vertices: Vec<Point>) -> Self {
Self {
vertices,
codes: None,
interpolation_steps: 1,
}
}
pub fn closed(vertices: Vec<Point>) -> Self {
let codes = (!vertices.is_empty()).then(|| closed_codes(vertices.len()));
Self {
vertices,
codes,
interpolation_steps: 1,
}
}
pub fn polygon<I: IntoIterator<Item = Point>>(points: I) -> Self {
let points = points.into_iter();
let mut vertices = Vec::with_capacity(points.size_hint().0 + 1);
vertices.extend(points);
if let Some(&first) = vertices.first() {
vertices.push(first);
}
Self::closed(vertices)
}
pub fn builder() -> PathBuilder {
PathBuilder::default()
}
pub fn compound<'a, I: IntoIterator<Item = &'a Self>>(paths: I) -> Self {
let paths: Vec<&Self> = paths.into_iter().collect();
if paths.is_empty() {
return Self::polyline(Vec::new());
}
let len = paths.iter().map(|path| path.vertices.len()).sum();
let mut vertices = Vec::with_capacity(len);
let mut codes = Vec::with_capacity(len);
for path in paths {
vertices.extend_from_slice(&path.vertices);
match &path.codes {
Some(c) => codes.extend_from_slice(c),
None => codes.extend(polyline_codes(path.vertices.len())),
}
}
Self {
vertices,
codes: Some(codes),
interpolation_steps: 1,
}
}
pub fn compound_from_polygons<P: AsRef<[Point]>>(polygons: &[P]) -> Self {
let len = polygons.iter().map(|p| p.as_ref().len() + 1).sum();
let mut vertices = Vec::with_capacity(len);
let mut codes = Vec::with_capacity(len);
for polygon in polygons {
let polygon = polygon.as_ref();
vertices.extend_from_slice(polygon);
vertices.push(Point::ORIGIN);
codes.extend(closed_codes(polygon.len() + 1));
}
Self {
vertices,
codes: Some(codes),
interpolation_steps: 1,
}
}
pub fn vertices(&self) -> &[Point] {
&self.vertices
}
pub fn vertices_mut(&mut self) -> &mut [Point] {
&mut self.vertices
}
pub fn codes(&self) -> Option<&[PathCode]> {
self.codes.as_deref()
}
pub fn code_at(&self, index: usize) -> PathCode {
match &self.codes {
Some(codes) => codes[index],
None if index == 0 => PathCode::MoveTo,
None => PathCode::LineTo,
}
}
pub fn resolved_codes(&self) -> Vec<PathCode> {
self.codes
.clone()
.unwrap_or_else(|| polyline_codes(self.vertices.len()).collect())
}
pub fn len(&self) -> usize {
self.vertices.len()
}
pub fn is_empty(&self) -> bool {
self.vertices.is_empty()
}
pub fn has_curves(&self) -> bool {
self.codes.as_ref().is_some_and(|c| {
c.iter()
.any(|c| matches!(c, PathCode::Curve3 | PathCode::Curve4))
})
}
pub const fn interpolation_steps(&self) -> usize {
self.interpolation_steps
}
#[must_use]
pub fn with_interpolation_steps(mut self, steps: usize) -> Self {
self.interpolation_steps = steps.max(1);
self
}
pub fn segments(&self) -> Segments<'_> {
Segments {
path: self,
index: 0,
}
}
pub fn beziers(&self) -> impl Iterator<Item = Bezier> + '_ {
let mut current = Point::ORIGIN;
let mut start = Point::ORIGIN;
self.segments().filter_map(move |segment| {
let from = current;
match segment {
Segment::MoveTo(p) => {
current = p;
start = p;
None
}
Segment::LineTo(p) => {
current = p;
Some(Bezier::Line(from, p))
}
Segment::QuadTo(c, p) => {
current = p;
Some(Bezier::Quad(from, c, p))
}
Segment::CubicTo(c1, c2, p) => {
current = p;
Some(Bezier::Cubic(from, c1, c2, p))
}
Segment::Close => {
current = start;
Some(Bezier::Line(from, start))
}
}
})
}
pub fn transform(&mut self, t: &Affine2D) {
t.transform_in_place(&mut self.vertices);
}
#[must_use]
pub fn transformed(&self, t: &Affine2D) -> Self {
let mut path = self.clone();
path.transform(t);
path
}
pub fn extents(&self) -> Bbox {
let mut bbox = Bbox::NULL;
let mut include = |p: Point| bbox = bbox.including(p);
if !self.has_curves() {
for (p, code) in self.vertices.iter().zip(self.resolved_codes()) {
if code != PathCode::ClosePoly {
include(*p);
}
}
return bbox;
}
for segment in self.segments() {
if let Segment::MoveTo(p) = segment {
include(p);
}
}
for curve in self.beziers() {
include(curve.start());
include(curve.end());
for t in curve.axis_aligned_extrema() {
include(curve.eval(t));
}
}
bbox
}
pub fn bezier_bounding_points(&self) -> impl Iterator<Item = Point> + '_ {
let moves = self.segments().filter_map(|segment| match segment {
Segment::MoveTo(point) => Some(point),
_ => None,
});
moves.chain(self.pieces_bounding_points())
}
fn pieces_bounding_points(&self) -> impl Iterator<Item = Point> + '_ {
self.beziers().flat_map(|curve| match curve {
Bezier::Line(start, end) => vec![start, end],
curve => {
let segment = BezierSegment::from_points(&curve.control_points())
.expect("a curve has control points of two coordinates");
let (_, roots) = segment.axis_aligned_extrema();
std::iter::once(0.0)
.chain(roots)
.chain(std::iter::once(1.0))
.map(|t| segment.point_at(t))
.collect()
}
})
}
pub fn bezier_extents(&self) -> Bbox {
if !self.has_curves() {
return self.extents();
}
self.bezier_bounding_points()
.fold(Bbox::NULL, |bbox, point| bbox.including(point))
}
pub fn subpaths(&self) -> Vec<Self> {
let codes = self.resolved_codes();
let mut starts: Vec<usize> = codes
.iter()
.enumerate()
.filter(|(i, c)| *i == 0 || **c == PathCode::MoveTo)
.map(|(i, _)| i)
.collect();
starts.push(codes.len());
starts
.windows(2)
.filter(|w| w[0] < w[1])
.map(|w| Self {
vertices: self.vertices[w[0]..w[1]].to_vec(),
codes: Some(codes[w[0]..w[1]].to_vec()),
interpolation_steps: self.interpolation_steps,
})
.collect()
}
#[must_use]
pub fn interpolated(&self, steps: usize) -> Self {
let steps = steps.min(MAX_INTERPOLATED_VERTICES / self.len().max(1));
self.subdivided(steps)
}
fn subdivided(&self, steps: usize) -> Self {
if steps <= 1 || self.is_empty() {
return self.clone();
}
let codes = self.resolved_codes();
if codes.iter().skip(1).any(|c| *c == PathCode::MoveTo) {
let parts: Vec<Self> = self
.subpaths()
.iter()
.map(|p| p.subdivided(steps))
.collect();
return Self::compound(&parts);
}
let first = self.vertices[0];
let vertices: Vec<Point> = self
.vertices
.iter()
.zip(&codes)
.map(|(p, c)| if *c == PathCode::ClosePoly { first } else { *p })
.collect();
let mut out = Vec::with_capacity((vertices.len() - 1) * steps + 1);
for pair in vertices.windows(2) {
out.extend((0..steps).map(|k| {
Point::new(
interp(pair[0].x, pair[1].x, k, steps),
interp(pair[0].y, pair[1].y, k, steps),
)
}));
}
out.push(vertices[vertices.len() - 1]);
let new_codes = self.codes.as_ref().map(|codes| {
let mut expanded = vec![PathCode::LineTo; (codes.len() - 1) * steps + 1];
for (i, code) in codes.iter().enumerate() {
expanded[i * steps] = *code;
}
expanded
});
Self {
vertices: out,
codes: new_codes,
interpolation_steps: self.interpolation_steps,
}
}
}
#[expect(clippy::float_cmp, reason = "numpy compares the samples exactly")]
fn interp(a: f64, b: f64, k: usize, steps: usize) -> f64 {
if k == 0 {
return a;
}
let slope = (b - a) / steps as f64;
let value = slope * k as f64 + a;
if !value.is_nan() {
return value;
}
let value = slope * (k as f64 - steps as f64) + b;
if value.is_nan() && a == b { a } else { value }
}
fn polyline_codes(len: usize) -> impl Iterator<Item = PathCode> {
(0..len).map(|i| {
if i == 0 {
PathCode::MoveTo
} else {
PathCode::LineTo
}
})
}
fn closed_codes(len: usize) -> Vec<PathCode> {
let mut codes: Vec<PathCode> = polyline_codes(len).collect();
if let Some(last) = codes.last_mut() {
*last = PathCode::ClosePoly;
}
codes
}
#[derive(Clone, Debug)]
pub struct Segments<'a> {
path: &'a Path,
index: usize,
}
impl Iterator for Segments<'_> {
type Item = Segment;
fn next(&mut self) -> Option<Segment> {
let vertices = &self.path.vertices;
let i = self.index;
if i >= vertices.len() {
return None;
}
let code = self.path.code_at(i);
let needed = code.vertex_count();
if i + needed > vertices.len() {
self.index = vertices.len();
return None;
}
self.index += needed;
Some(match code {
PathCode::MoveTo => Segment::MoveTo(vertices[i]),
PathCode::LineTo => Segment::LineTo(vertices[i]),
PathCode::Curve3 => Segment::QuadTo(vertices[i], vertices[i + 1]),
PathCode::Curve4 => Segment::CubicTo(vertices[i], vertices[i + 1], vertices[i + 2]),
PathCode::ClosePoly => Segment::Close,
})
}
}
#[cfg(test)]
mod tests;