a770fa5a5e5f
curve.rs
use serde::{Deserialize, Serialize};
use crate::{Bounds2, EPS, Mat3, PI, TAU, Vec2, angle_in_sweep, arc_segments, ccw_sweep, norm_angle};
/// A straight segment.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Line {
pub a: Vec2,
pub b: Vec2,
}
impl Line {
pub fn new(a: Vec2, b: Vec2) -> Self {
Line { a, b }
}
pub fn len(&self) -> f64 {
self.a.dist(self.b)
}
pub fn dir(&self) -> Vec2 {
(self.b - self.a).normalized()
}
pub fn mid(&self) -> Vec2 {
self.a.mid(self.b)
}
/// Parameter (0..1 on the segment) of the projection of `p`.
pub fn param_of(&self, p: Vec2) -> f64 {
let d = self.b - self.a;
let l2 = d.len2();
if l2 <= EPS * EPS { 0.0 } else { (p - self.a).dot(d) / l2 }
}
pub fn at(&self, t: f64) -> Vec2 {
self.a.lerp(self.b, t)
}
/// Closest point on the segment.
pub fn closest(&self, p: Vec2) -> Vec2 {
self.at(self.param_of(p).clamp(0.0, 1.0))
}
/// Foot of the perpendicular on the infinite line.
pub fn project(&self, p: Vec2) -> Vec2 {
self.at(self.param_of(p))
}
pub fn dist(&self, p: Vec2) -> f64 {
self.closest(p).dist(p)
}
/// Signed side: > 0 left of a→b.
pub fn side(&self, p: Vec2) -> f64 {
(self.b - self.a).cross(p - self.a)
}
pub fn offset(&self, d: f64) -> Line {
let n = (self.b - self.a).normalized().perp() * d;
Line::new(self.a + n, self.b + n)
}
}
/// A circular arc, CCW from `start` to `end` angle.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Arc {
pub center: Vec2,
pub radius: f64,
pub start: f64,
pub end: f64,
}
impl Arc {
pub fn new(center: Vec2, radius: f64, start: f64, end: f64) -> Self {
Arc { center, radius: radius.abs(), start: norm_angle(start), end: norm_angle(end) }
}
pub fn sweep(&self) -> f64 {
ccw_sweep(self.start, self.end)
}
pub fn start_point(&self) -> Vec2 {
Vec2::polar(self.center, self.radius, self.start)
}
pub fn end_point(&self) -> Vec2 {
Vec2::polar(self.center, self.radius, self.end)
}
pub fn mid_point(&self) -> Vec2 {
Vec2::polar(self.center, self.radius, self.start + self.sweep() / 2.0)
}
pub fn len(&self) -> f64 {
self.radius * self.sweep()
}
pub fn contains_angle(&self, a: f64) -> bool {
angle_in_sweep(a, self.start, self.end)
}
/// Point at parameter `t` in 0..1 along the sweep.
pub fn at(&self, t: f64) -> Vec2 {
Vec2::polar(self.center, self.radius, self.start + self.sweep() * t)
}
/// Arc through three points, or `None` when collinear.
pub fn from_3_points(p1: Vec2, p2: Vec2, p3: Vec2) -> Option<Arc> {
let c = Circle::from_3_points(p1, p2, p3)?;
let a1 = c.center.angle_to(p1);
let a2 = c.center.angle_to(p2);
let a3 = c.center.angle_to(p3);
// CCW from p1 to p3 must pass p2; otherwise go the other way.
if angle_in_sweep(a2, a1, a3) { Some(Arc::new(c.center, c.radius, a1, a3)) } else { Some(Arc::new(c.center, c.radius, a3, a1)) }
}
/// Arc from start point, center and end point (CCW).
pub fn from_start_center_end(s: Vec2, c: Vec2, e: Vec2) -> Arc {
Arc::new(c, s.dist(c), c.angle_to(s), c.angle_to(e))
}
pub fn closest(&self, p: Vec2) -> Vec2 {
let a = self.center.angle_to(p);
if self.contains_angle(a) && p.dist(self.center) > EPS {
Vec2::polar(self.center, self.radius, a)
} else {
let s = self.start_point();
let e = self.end_point();
if s.dist(p) <= e.dist(p) { s } else { e }
}
}
pub fn bounds(&self) -> Bounds2 {
let mut b = Bounds2::from_points([self.start_point(), self.end_point()]);
for k in 0..4 {
let a = f64::from(k) * PI / 2.0;
if self.contains_angle(a) {
b.add(Vec2::polar(self.center, self.radius, a));
}
}
b
}
#[expect(clippy::cast_precision_loss, reason = "arc_segments caps the sample count at 4096, so every sample index is exact as f64.")]
pub fn tessellate(&self, tol: f64, out: &mut Vec<Vec2>) {
let sweep = self.sweep();
let n = arc_segments(self.radius, sweep, tol);
for i in 0..=n {
out.push(Vec2::polar(self.center, self.radius, self.start + sweep * i as f64 / n as f64));
}
}
}
/// A full circle.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Circle {
pub center: Vec2,
pub radius: f64,
}
impl Circle {
pub fn new(center: Vec2, radius: f64) -> Self {
Circle { center, radius: radius.abs() }
}
pub fn from_3_points(p1: Vec2, p2: Vec2, p3: Vec2) -> Option<Circle> {
// Work in point-relative coordinates. Absolute coordinate squares lose the small
// differences between points in drawings far from the origin.
if !p1.is_finite() || !p2.is_finite() || !p3.is_finite() {
return None;
}
let u = p2 - p1;
let v = p3 - p1;
let det = 2.0 * u.cross(v);
// The collinearity threshold must scale with the triangle, not drawing units.
if !det.is_finite() || det.abs() <= 1e-12 * (u.len() * v.len()).max(1e-300) {
return None;
}
let u2 = u.len2();
let v2 = v.len2();
let c = p1 + Vec2::new((u2 * v.y - v2 * u.y) / det, (v2 * u.x - u2 * v.x) / det);
if !c.is_finite() {
return None;
}
let radius = c.dist(p1);
if !radius.is_finite() {
return None;
}
Some(Circle::new(c, radius))
}
pub fn from_2_points(p1: Vec2, p2: Vec2) -> Circle {
Circle::new(p1.mid(p2), p1.dist(p2) / 2.0)
}
pub fn closest(&self, p: Vec2) -> Vec2 {
let d = p - self.center;
if d.len() < EPS { self.center + Vec2::X * self.radius } else { self.center + d.normalized() * self.radius }
}
pub fn bounds(&self) -> Bounds2 {
Bounds2::new(self.center - Vec2::new(self.radius, self.radius), self.center + Vec2::new(self.radius, self.radius))
}
pub fn tessellate(&self, tol: f64, out: &mut Vec<Vec2>) {
Arc { center: self.center, radius: self.radius, start: 0.0, end: TAU }.tessellate(tol, out);
}
/// Tangent points from external point `p`.
pub fn tangent_points(&self, p: Vec2) -> Vec<Vec2> {
let d = p.dist(self.center);
if d <= self.radius + EPS {
return Vec::new();
}
let base = self.center.angle_to(p);
let off = (self.radius / d).clamp(-1.0, 1.0).acos();
vec![Vec2::polar(self.center, self.radius, base + off), Vec2::polar(self.center, self.radius, base - off)]
}
/// Lines tangent to both `self` and `other`, as (point on `self`, point on `other`) pairs:
/// up to two outer (belt) tangents and two inner (crossed) tangents. Empty for concentric
/// circles or when one circle lies inside the other; tangents that touch both circles at the
/// same point (circles touching each other) are left out.
#[expect(clippy::many_single_char_names, reason = "Circle-tangent equations use conventional r/v/d/u/c/h/n/p/q notation.")]
pub fn common_tangents(&self, other: &Circle) -> Vec<(Vec2, Vec2)> {
let (r1, r2) = (self.radius, other.radius);
let v = other.center - self.center;
let d = v.len();
if !(d.is_finite() && r1.is_finite() && r2.is_finite()) || d <= EPS {
return Vec::new();
}
let u = v / d;
let mut out = Vec::new();
// `s` = +1: outer tangents (both circles on the same side); -1: inner tangents.
for s in [1.0, -1.0] {
let c = (r1 - s * r2) / d;
if c.abs() > 1.0 - EPS {
continue;
}
let h = (1.0 - c * c).max(0.0).sqrt();
for k in [1.0, -1.0] {
// Unit normal of the tangent line, pointing from each center towards its tangent point.
let n = u * c + u.perp() * (h * k);
let (p, q) = (self.center + n * r1, other.center + n * (s * r2));
if p.is_finite() && q.is_finite() && p.dist(q) > EPS {
out.push((p, q));
}
}
}
out
}
}
/// An ellipse (or elliptical arc), DXF-style: center, major-axis endpoint vector, ratio, params.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Ellipse {
pub center: Vec2,
pub major: Vec2,
pub ratio: f64,
pub start: f64,
pub end: f64,
}
impl Ellipse {
pub fn full(center: Vec2, major: Vec2, ratio: f64) -> Self {
Ellipse { center, major, ratio, start: 0.0, end: TAU }
}
pub fn is_full(&self) -> bool {
(ccw_sweep(self.start, self.end) - TAU).abs() < 1e-9
}
pub fn minor(&self) -> Vec2 {
self.major.perp() * self.ratio
}
pub fn at_param(&self, t: f64) -> Vec2 {
self.center + self.major * t.cos() + self.minor() * t.sin()
}
pub fn sweep(&self) -> f64 {
ccw_sweep(self.start, self.end)
}
/// The image under the affine transform `m`, exactly: the conjugate semi-diameters
/// `A·major`, `A·minor` give the new principal axes; parameters shift with them (and
/// reverse under a mirroring transform).
pub fn transformed(&self, m: &Mat3) -> Ellipse {
let center = m.apply(self.center);
let (am, an) = (m.apply_vec(self.major), m.apply_vec(self.minor()));
// |am·cos t + an·sin t| is largest at t0: the new major axis.
let t0 = 0.5 * (2.0 * am.dot(an)).atan2(am.dot(am) - an.dot(an));
let (s0, c0) = t0.sin_cos();
let (u, v) = (am * c0 + an * s0, an * c0 - am * s0);
let ratio = if u.len() > 0.0 { (v.len() / u.len()).min(1.0) } else { 1.0 };
if self.is_full() {
return Ellipse::full(center, u, ratio);
}
let (start, end) = if u.cross(v) >= 0.0 { (self.start - t0, self.end - t0) } else { (t0 - self.end, t0 - self.start) };
Ellipse { center, major: u, ratio, start: norm_angle(start), end: norm_angle(end) }
}
#[expect(clippy::cast_precision_loss, reason = "arc_segments caps the sample count at 4096, so every sample index is exact as f64.")]
pub fn tessellate(&self, tol: f64, out: &mut Vec<Vec2>) {
let r = self.major.len();
let sweep = self.sweep();
let n = arc_segments(r, sweep, tol).max(8);
for i in 0..=n {
out.push(self.at_param(self.start + sweep * i as f64 / n as f64));
}
}
pub fn bounds(&self) -> Bounds2 {
// Sampled bounds can cut off the true extrema, especially on a small arc or
// a large drawing. The derivative of each coordinate gives two exact
// candidate parameters (opposite sides of the ellipse).
let minor = self.minor();
let mut bounds = Bounds2::from_points([self.at_param(self.start), self.at_param(self.end)]);
for angle in [minor.x.atan2(self.major.x), minor.x.atan2(self.major.x) + PI, minor.y.atan2(self.major.y), minor.y.atan2(self.major.y) + PI] {
if angle_in_sweep(angle, self.start, self.end) {
bounds.add(self.at_param(angle));
}
}
bounds
}
/// Parameter of the point on the ellipse nearest the direction of `p` (approximate).
pub fn param_of(&self, p: Vec2) -> f64 {
let ma = self.major.len();
if ma < EPS {
return 0.0;
}
let ux = self.major / ma;
let local = p - self.center;
let x = local.dot(ux);
let y = local.dot(ux.perp());
let mb = ma * self.ratio;
norm_angle((y / mb.max(EPS)).atan2(x / ma))
}
pub fn closest(&self, p: Vec2) -> Vec2 {
let mut pts = Vec::new();
self.tessellate(self.major.len() * 1e-3, &mut pts);
nearest_on_polyline(&pts, p).unwrap_or(self.center)
}
}
/// The nearest point to `p` on a polyline (through tessellated points).
pub(crate) fn nearest_on_polyline(pts: &[Vec2], p: Vec2) -> Option<Vec2> {
let mut best: Option<(f64, Vec2)> = None;
for w in pts.windows(2) {
if let [a, b] = w {
let c = Line::new(*a, *b).closest(p);
let d = c.dist(p);
if best.is_none_or(|(bd, _)| d < bd) {
best = Some((d, c));
}
}
}
best.map(|(_, c)| c).or_else(|| pts.first().copied())
}
/// A primitive segment: a line or an arc (polyline pieces, boundary loops, offsets).
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub enum Segment {
Line(Line),
/// An arc with direction: `ccw == false` runs from end to start in arc terms.
Arc {
arc: Arc,
ccw: bool,
},
}
impl Segment {
pub fn start(&self) -> Vec2 {
match self {
Segment::Line(l) => l.a,
Segment::Arc { arc, ccw: true } => arc.start_point(),
Segment::Arc { arc, ccw: false } => arc.end_point(),
}
}
pub fn end(&self) -> Vec2 {
match self {
Segment::Line(l) => l.b,
Segment::Arc { arc, ccw: true } => arc.end_point(),
Segment::Arc { arc, ccw: false } => arc.start_point(),
}
}
pub fn len(&self) -> f64 {
match self {
Segment::Line(l) => l.len(),
Segment::Arc { arc, .. } => arc.len(),
}
}
pub fn mid(&self) -> Vec2 {
match self {
Segment::Line(l) => l.mid(),
Segment::Arc { arc, .. } => arc.mid_point(),
}
}
pub fn closest(&self, p: Vec2) -> Vec2 {
match self {
Segment::Line(l) => l.closest(p),
Segment::Arc { arc, .. } => arc.closest(p),
}
}
pub fn bounds(&self) -> Bounds2 {
match self {
Segment::Line(l) => Bounds2::new(l.a, l.b),
Segment::Arc { arc, .. } => arc.bounds(),
}
}
/// Points along the segment in its direction, including both ends.
pub fn tessellate(&self, tol: f64, out: &mut Vec<Vec2>) {
match self {
Segment::Line(l) => {
out.push(l.a);
out.push(l.b);
}
Segment::Arc { arc, ccw } => {
let start = out.len();
arc.tessellate(tol, out);
if !ccw && let Some(s) = out.get_mut(start..) {
s.reverse();
}
}
}
}
/// Point at parameter `t` (0..1) in segment direction.
pub fn at(&self, t: f64) -> Vec2 {
match self {
Segment::Line(l) => l.at(t),
Segment::Arc { arc, ccw: true } => arc.at(t),
Segment::Arc { arc, ccw: false } => arc.at(1.0 - t),
}
}
pub fn reversed(&self) -> Segment {
match *self {
Segment::Line(l) => Segment::Line(Line::new(l.b, l.a)),
Segment::Arc { arc, ccw } => Segment::Arc { arc, ccw: !ccw },
}
}
/// Tangent direction (unit) at parameter t.
pub fn tangent(&self, t: f64) -> Vec2 {
match self {
Segment::Line(l) => l.dir(),
Segment::Arc { arc, ccw } => {
let p = self.at(t);
let r = (p - arc.center).perp().normalized();
if *ccw { r } else { -r }
}
}
}
/// Offset by `d` to the left of travel direction. `None` if an arc collapses.
pub fn offset(&self, d: f64) -> Option<Segment> {
match *self {
Segment::Line(l) => Some(Segment::Line(l.offset(d))),
Segment::Arc { arc, ccw } => {
// Left of a CCW arc is toward the center.
let r = if ccw { arc.radius - d } else { arc.radius + d };
if r <= EPS {
return None;
}
Some(Segment::Arc { arc: Arc { radius: r, ..arc }, ccw })
}
}
}
}
/// A polyline vertex: position, bulge to the next vertex (tan(θ/4)), and optional widths.
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct PolyVertex {
pub p: Vec2,
#[serde(default)]
pub bulge: f64,
#[serde(default)]
pub start_width: f64,
#[serde(default)]
pub end_width: f64,
}
impl PolyVertex {
pub fn new(p: Vec2) -> Self {
PolyVertex { p, ..Default::default() }
}
pub fn with_bulge(p: Vec2, bulge: f64) -> Self {
PolyVertex { p, bulge, ..Default::default() }
}
}
/// Convert a bulge segment to an arc. `None` for a straight (zero-bulge or degenerate) segment.
pub fn bulge_to_arc(a: Vec2, b: Vec2, bulge: f64) -> Option<(Arc, bool)> {
if bulge.abs() < 1e-12 || !bulge.is_finite() || a.near(b, EPS) {
return None;
}
let theta = 4.0 * bulge.atan(); // signed included angle
// A sweep at or below EPS would be read back as a full circle by `ccw_sweep`; it is a straight segment.
if theta.abs() <= EPS {
return None;
}
let chord = a.dist(b);
let r = chord / (2.0 * (theta / 2.0).sin().abs());
let mid = a.mid(b);
let sagitta_dir = (b - a).normalized().perp();
// distance from chord midpoint to center
let h = r * (theta / 2.0).cos().abs();
// For bulge > 0 (CCW), center is to the left of a→b when |θ| < π.
let sign = if bulge > 0.0 { 1.0 } else { -1.0 };
let center = if theta.abs() < PI { mid + sagitta_dir * (h * sign) } else { mid - sagitta_dir * (h * sign) };
let sa = center.angle_to(a);
let ea = center.angle_to(b);
if bulge > 0.0 { Some((Arc::new(center, r, sa, ea), true)) } else { Some((Arc::new(center, r, ea, sa), false)) }
}
/// Bulge for an arc traversed from `a` to `b` with the given sweep (signed: + = CCW).
pub fn arc_to_bulge(signed_sweep: f64) -> f64 {
(signed_sweep / 4.0).tan()
}
/// A 2D polyline with bulges (LWPOLYLINE).
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct Polyline {
pub vertices: Vec<PolyVertex>,
pub closed: bool,
}
/// Sampled points one [`Polyline::tessellate`] call produces before arcs become chords.
pub const MAX_TESSELLATED_POINTS: usize = 4_000_000;
impl Polyline {
pub fn from_points(pts: &[Vec2], closed: bool) -> Self {
Polyline { vertices: pts.iter().map(|p| PolyVertex::new(*p)).collect(), closed }
}
/// The segments, including the closing segment when closed.
pub fn segments(&self) -> Vec<Segment> {
let n = self.vertices.len();
let mut out = Vec::with_capacity(n);
let count = if self.closed { n } else { n.saturating_sub(1) };
for i in 0..count {
let (Some(v), Some(w)) = (self.vertices.get(i), self.vertices.get((i + 1) % n.max(1))) else { continue };
if v.p.near(w.p, EPS) && v.bulge.abs() < 1e-12 {
continue;
}
match bulge_to_arc(v.p, w.p, v.bulge) {
Some((arc, ccw)) => out.push(Segment::Arc { arc, ccw }),
None => out.push(Segment::Line(Line::new(v.p, w.p))),
}
}
out
}
pub fn len(&self) -> f64 {
self.segments().iter().map(Segment::len).sum()
}
pub fn bounds(&self) -> Bounds2 {
let mut b = Bounds2::from_points(self.vertices.iter().map(|v| v.p));
for s in self.segments() {
b = b.union(&s.bounds());
}
b
}
pub fn tessellate(&self, tol: f64) -> Vec<Vec2> {
let mut budget = MAX_TESSELLATED_POINTS;
self.tessellate_within(tol, &mut budget)
}
/// [`Polyline::tessellate`] spending about `budget` sampled points (shared by the caller
/// across many polylines). The budget is checked before each segment, so the last segment
/// started may overshoot it by that one segment's samples. Once it is spent, the remaining arcs are drawn as chords, so the
/// output stays proportional to the input vertices. Each arc can sample thousands of points,
/// so a compact polyline could otherwise expand into gigabytes (CWE-400).
pub fn tessellate_within(&self, tol: f64, budget: &mut usize) -> Vec<Vec2> {
let mut out: Vec<Vec2> = Vec::new();
for s in self.segments() {
let mut pts = Vec::new();
if *budget > 0 {
s.tessellate(tol, &mut pts);
*budget = budget.saturating_sub(pts.len());
} else {
pts.extend([s.start(), s.end()]);
}
let skip = usize::from(out.last().is_some_and(|l| pts.first().is_some_and(|f| l.near(*f, 1e-9))));
out.extend(pts.into_iter().skip(skip));
}
if out.is_empty() {
out.extend(self.vertices.first().map(|v| v.p));
}
out
}
/// Signed area (CCW positive) of a closed polyline including bulge areas.
pub fn area(&self) -> f64 {
// Integrate the chords exactly and add the signed circular-segment area
// for every bulge. A tessellated shoelace loses precision on large arcs.
// Working relative to the first vertex avoids cancellation when a small
// shape is located far from the drawing origin.
let Some(first) = self.vertices.first() else {
return 0.0;
};
let origin = first.p;
let n = self.vertices.len();
let mut twice_area = 0.0;
for i in 0..n {
let (Some(a), Some(b)) = (self.vertices.get(i), self.vertices.get((i + 1) % n)) else {
continue;
};
twice_area += (a.p - origin).cross(b.p - origin);
// Open polylines keep their historical implicit straight closing edge.
// The final vertex's bulge is only used for an explicit closing segment.
if (i + 1 < n || self.closed)
&& let Some((arc, ccw)) = bulge_to_arc(a.p, b.p, a.bulge)
{
let sweep = if ccw { arc.sweep() } else { -arc.sweep() };
twice_area += arc.radius * arc.radius * (sweep - sweep.sin());
}
}
twice_area / 2.0
}
pub fn closest(&self, p: Vec2) -> Option<Vec2> {
let mut best: Option<(f64, Vec2)> = None;
for s in self.segments() {
let c = s.closest(p);
let d = c.dist(p);
if best.is_none_or(|(bd, _)| d < bd) {
best = Some((d, c));
}
}
best.map(|(_, c)| c).or_else(|| self.vertices.first().map(|v| v.p))
}
/// True if `p` is inside a closed polyline (even-odd on the tessellation).
pub fn contains(&self, p: Vec2) -> bool {
point_in_polygon(&self.tessellate(1e-3), p)
}
/// Area centroid of the closed polyline, exact with bulges: the chord triangles fanned from the
/// first vertex plus each bulge's circular segment, weighted by signed area. `None` at zero area.
#[expect(clippy::many_single_char_names, reason = "Centroid integration uses conventional a/b/c/d/t area and point notation.")]
pub fn centroid(&self) -> Option<Vec2> {
let origin = self.vertices.first()?.p;
let n = self.vertices.len();
let (mut area, mut mx, mut my) = (0.0, 0.0, 0.0);
let mut add = |a: f64, c: Vec2| {
area += a;
mx += a * c.x;
my += a * c.y;
};
for i in 0..n {
let (Some(a), Some(b)) = (self.vertices.get(i), self.vertices.get((i + 1) % n)) else { continue };
let (pa, pb) = (a.p - origin, b.p - origin);
add(pa.cross(pb) / 2.0, (pa + pb) * (1.0 / 3.0));
if (i + 1 < n || self.closed)
&& let Some((arc, ccw)) = bulge_to_arc(a.p, b.p, a.bulge)
{
let t = arc.sweep();
let seg = arc.radius * arc.radius * (t - t.sin()) / 2.0;
if seg > 0.0 {
// A circular segment's centroid lies on the bisector, 4r·sin³(θ/2) / 3(θ − sin θ) from the centre.
let d = 4.0 * arc.radius * (t / 2.0).sin().powi(3) / (3.0 * (t - t.sin()));
let dir = (arc.mid_point() - arc.center).normalized();
add(if ccw { seg } else { -seg }, arc.center - origin + dir * d);
}
}
}
let scale = self.vertices.iter().map(|v| (v.p - origin).len()).fold(0.0, f64::max);
(area.is_finite() && area.abs() > 1e-12 * scale * scale).then(|| origin + Vec2::new(mx / area, my / area))
}
}
/// Area centroid of a closed polygon. `None` at zero area.
pub fn polygon_centroid(pts: &[Vec2]) -> Option<Vec2> {
Polyline::from_points(pts, true).centroid()
}
/// Signed polygon area (CCW positive).
pub fn shoelace(pts: &[Vec2]) -> f64 {
let n = pts.len();
if n < 3 {
return 0.0;
}
let Some(origin) = pts.first().copied() else {
return 0.0;
};
// Measure about a local origin so a small polygon at a large world
// coordinate does not lose its area to cancellation of huge products.
let mut s = 0.0;
for i in 0..n {
if let (Some(a), Some(b)) = (pts.get(i), pts.get((i + 1) % n)) {
s += (*a - origin).cross(*b - origin);
}
}
s / 2.0
}
/// Even-odd point-in-polygon test.
pub fn point_in_polygon(poly: &[Vec2], p: Vec2) -> bool {
let n = poly.len();
if n < 3 {
return false;
}
let mut inside = false;
let mut j = n - 1;
for i in 0..n {
if let (Some(a), Some(b)) = (poly.get(i), poly.get(j))
&& (a.y > p.y) != (b.y > p.y)
{
let x = (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
if p.x < x {
inside = !inside;
}
}
j = i;
}
inside
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.