a770fa5a5e5f
region.rs
//! Regions (REGION): a closed planar area bounded by loops of lines and arcs. Outer loops add
//! area, island loops (holes) take it away; loops don't cross.
use cadcraft_geom::{Bounds2, PolyVertex, Polyline, Segment, Vec2, point_in_polygon};
use serde::{Deserialize, Serialize};
use super::HatchLoop;
/// Most loops one region has (hostile files and edits).
pub const MAX_REGION_LOOPS: usize = 10_000;
/// Most polygon edges [`Region::renest`] tests, over all its point-in-loop tests.
pub const MAX_RENEST_EDGE_VISITS: usize = 50_000_000;
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct Region {
/// Closed loops with bulges; `outer` false for islands.
pub loops: Vec<HatchLoop>,
}
/// Area properties of a region (MASSPROP), in drawing units.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct RegionProps {
pub area: f64,
pub perimeter: f64,
pub bounds: Bounds2,
pub centroid: Vec2,
/// ∫y² dA and ∫x² dA about the origin.
pub ixx: f64,
pub iyy: f64,
/// ∫xy dA about the origin.
pub ixy: f64,
/// The same three about the centroid.
pub centroid_moments: [f64; 3],
}
impl Region {
/// A region bounded by one closed loop.
pub fn from_loop(vertices: Vec<PolyVertex>) -> Region {
Region { loops: vec![HatchLoop { vertices, outer: true, sources: Vec::new() }] }
}
pub fn polylines(&self) -> Vec<Polyline> {
self.loops.iter().map(|l| Polyline { vertices: l.vertices.clone(), closed: true }).collect()
}
/// The boundary: every loop's lines and arcs.
pub fn segments(&self) -> Vec<Segment> {
self.polylines().iter().flat_map(Polyline::segments).collect()
}
/// Each loop as points, arcs within `tol`.
pub fn tessellate(&self, tol: f64) -> Vec<Vec<Vec2>> {
self.polylines().iter().map(|p| p.tessellate(tol)).collect()
}
pub fn bounds(&self) -> Bounds2 {
self.polylines().iter().fold(Bounds2::EMPTY, |b, p| b.union(&p.bounds()))
}
/// Outer loops' area less the islands'.
pub fn area(&self) -> f64 {
self.loops.iter().map(|l| Polyline { vertices: l.vertices.clone(), closed: true }.area().abs() * if l.outer { 1.0 } else { -1.0 }).sum()
}
pub fn perimeter(&self) -> f64 {
self.polylines().iter().map(Polyline::len).sum()
}
/// A chord tolerance fine enough for measuring: 1e-5 of the region's size.
fn fine_tol(&self) -> f64 {
let b = self.bounds();
if b.is_empty() { 1e-6 } else { ((b.width() + b.height()) * 1e-5).max(1e-12) }
}
/// Whether `p` lies inside the region (odd parity over its loops).
pub fn contains(&self, p: Vec2) -> bool {
self.tessellate(self.fine_tol()).iter().filter(|l| point_in_polygon(l, p)).count() % 2 == 1
}
/// Set each loop's `outer` flag from how deeply other loops enclose it: an even depth is
/// an outer loop, odd an island. `false`, with the flags left as they were, when that takes
/// more than [`MAX_RENEST_EDGE_VISITS`] polygon edge tests.
#[must_use]
pub fn renest(&mut self) -> bool {
let polys = self.tessellate(self.fine_tol());
// A loop's probe can only be inside loops whose box holds it: test only those. A box with
// a non-finite corner says nothing (an edge through a non-finite point never counts, so
// such a polygon need not be closed), so its loop is always tested.
let boxes: Vec<Option<Bounds2>> = polys
.iter()
.map(|l| {
let b = Bounds2::from_points(l.iter().copied());
(l.iter().all(|p| p.is_finite()) && b.min.is_finite() && b.max.is_finite()).then_some(b)
})
.collect();
let mut visits = 0usize;
let mut depth = Vec::with_capacity(polys.len());
for (i, l) in polys.iter().enumerate() {
let Some(p) = probe(l) else {
depth.push(0);
continue;
};
let mut d = 0;
for (j, (o, b)) in polys.iter().zip(&boxes).enumerate() {
if j == i || b.is_some_and(|b| !b.contains(p)) {
continue;
}
// Each loop against every other is loops x vertices: bounded so a region of many
// large nested loops cannot hold the thread (CWE-407).
visits = visits.saturating_add(o.len());
if visits > MAX_RENEST_EDGE_VISITS {
return false;
}
if point_in_polygon(o, p) {
d += 1;
}
}
depth.push(d);
}
for (l, d) in self.loops.iter_mut().zip(depth) {
l.outer = d % 2 == 0;
}
true
}
/// Area, perimeter, bounding box, centroid and second moments (outer loops counted
/// counter-clockwise, islands clockwise).
pub fn props(&self) -> RegionProps {
let tol = self.fine_tol();
let (mut a, mut cx, mut cy, mut ixx, mut iyy, mut ixy) = (0.0, 0.0, 0.0, 0.0, 0.0, 0.0);
for (l, pts) in self.loops.iter().zip(self.tessellate(tol)) {
let signed = cadcraft_geom::shoelace(&pts);
// Outer loops add, islands subtract, whatever way they run.
let flip = if (signed >= 0.0) == l.outer { 1.0 } else { -1.0 };
let n = pts.len();
for i in 0..n {
let (Some(p), Some(q)) = (pts.get(i), pts.get((i + 1) % n)) else { continue };
let c = (p.x * q.y - q.x * p.y) * flip;
a += c / 2.0;
cx += (p.x + q.x) * c / 6.0;
cy += (p.y + q.y) * c / 6.0;
ixx += (p.y * p.y + p.y * q.y + q.y * q.y) * c / 12.0;
iyy += (p.x * p.x + p.x * q.x + q.x * q.x) * c / 12.0;
ixy += (p.x * q.y + 2.0 * p.x * p.y + 2.0 * q.x * q.y + q.x * p.y) * c / 24.0;
}
}
let c = if a.abs() > 1e-300 { Vec2::new(cx / a, cy / a) } else { Vec2::ZERO };
// Shifted with the area of the same outline the moments were taken from.
let centroid_moments = [ixx - a * c.y * c.y, iyy - a * c.x * c.x, ixy - a * c.x * c.y];
RegionProps { area: self.area(), perimeter: self.perimeter(), bounds: self.bounds(), centroid: c, ixx, iyy, ixy, centroid_moments }
}
}
/// A point of a loop to test its nesting with: the middle of its first non-degenerate edge.
fn probe(l: &[Vec2]) -> Option<Vec2> {
let n = l.len();
(0..n).find_map(|i| {
let (a, b) = (*l.get(i)?, *l.get((i + 1) % n)?);
(a.dist(b) > 1e-12).then(|| (a + b) * 0.5).filter(|m| m.is_finite())
})
}
#[cfg(test)]
mod tests {
use super::*;
fn square(c: f64, half: f64, n: usize, outer: bool) -> HatchLoop {
// `n` vertices along the bottom edge, then the other three corners.
let mut vertices: Vec<PolyVertex> =
(0..n).map(|k| PolyVertex::new(Vec2::new(c - half + 2.0 * half * k as f64 / n as f64, c - half))).collect();
vertices.extend([Vec2::new(c + half, c - half), Vec2::new(c + half, c + half), Vec2::new(c - half, c + half)].map(PolyVertex::new));
HatchLoop { vertices, outer, sources: Vec::new() }
}
#[test]
fn renest_sets_depth_parity_and_skips_loops_far_away() {
// Three nested squares, and one beside them.
let mut r =
Region { loops: vec![square(0.0, 3.0, 1, false), square(0.0, 2.0, 1, false), square(0.0, 1.0, 1, false), square(10.0, 1.0, 1, false)] };
assert!(r.renest());
assert_eq!(r.loops.iter().map(|l| l.outer).collect::<Vec<_>>(), [true, false, true, true]);
}
#[test]
fn renest_of_many_large_nested_loops_stops_at_its_budget() {
// Concentric loops of many vertices each: each probe is inside the box of every larger
// loop (about loops² / 2 pairs), so each of those tests is a full polygon scan.
let loops = 300;
let n = 3 * MAX_RENEST_EDGE_VISITS / (loops * loops);
let mut r = Region { loops: (0..loops).map(|i| square(0.0, 1.0 + i as f64, n, false)).collect() };
let before = r.clone();
assert!(!r.renest());
assert_eq!(r, before, "flags left as they were");
}
}
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.