856f865cf98d
area.rs
//! Area type: text that wraps inside a closed path, like Photoshop's area type.
//!
//! The path is flattened once into edges. For a line's band (ascent to descent),
//! [`AreaShape::spans`] gives the intervals that are inside the shape for the whole band, left
//! to right. A shape with dents or holes gives several spans on a row, and the layout fills
//! them in order at the same baseline, as Photoshop does.
use std::ops::Range;
use photocraft_doc::vector::{FillRule, Path, PathOp};
use photocraft_geom::Point;
/// Pieces each curved segment is cut into (about 0.1 px off a 300 px bubble's curve).
const CURVE_PIECES: usize = 16;
/// Most anchors an area path can have: the most `type.fillPath` accepts and a Type tool click
/// targets (`path_target` in ui-egui).
pub const MAX_AREA_KNOTS: usize = 4096;
/// Largest number of edges an area keeps, so a hostile path can't make every line scan millions.
/// A closed subpath of `n` anchors gives at most `CURVE_PIECES * n + 1` edges, so every path
/// within [`MAX_AREA_KNOTS`] fits, even with every segment curved.
pub const MAX_AREA_EDGES: usize = MAX_AREA_KNOTS * (CURVE_PIECES + 1);
/// Most shape components an area keeps: every row folds each one in, so a path of thousands of
/// tiny shapes can't make each line cost thousands of interval merges.
pub const MAX_AREA_COMPONENTS: usize = 4096;
/// Largest coordinate magnitude an area accepts, so f32 math on it can't overflow.
const MAX_COORD: f64 = 1e7;
/// Most baselines `next_row` tries before giving up.
const MAX_ROW_STEPS: usize = 1024;
#[derive(Clone, Copy, Debug)]
struct Edge {
x0: f32,
y0: f32,
x1: f32,
y1: f32,
/// Lower and upper y of the edge.
lo: f32,
hi: f32,
}
#[derive(Clone, Debug)]
struct Component {
op: PathOp,
/// Range into `AreaShape::edges`, sorted by `lo`.
edges: Range<usize>,
/// Tallest edge in the range, so a query only looks at edges whose `lo` is within it.
max_h: f32,
}
/// A closed path ready for line fitting, in area space (text space, or `(y, -x)` for vertical
/// type so its rows are columns).
#[derive(Clone, Debug)]
pub struct AreaShape {
edges: Vec<Edge>,
comps: Vec<Component>,
rule: FillRule,
/// Extent of the edges: `[x0, y0, x1, y1]`.
pub bounds: [f32; 4],
}
fn cubic(s: &[Point; 4], t: f64) -> (f64, f64) {
let u = 1.0 - t;
let (a, b, c, d) = (u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t);
(a * s[0].x + b * s[1].x + c * s[2].x + d * s[3].x, a * s[0].y + b * s[1].y + c * s[2].y + d * s[3].y)
}
fn same(a: Point, b: Point) -> bool {
(a.x - b.x).abs() < 1e-9 && (a.y - b.y).abs() < 1e-9
}
/// f64 → f32, rejecting values that are not finite or are beyond [`MAX_COORD`].
fn small(v: f64) -> Option<f32> {
let f = v as f32;
(v.abs() <= MAX_COORD && f.is_finite()).then_some(f)
}
impl AreaShape {
/// `None` when the path encloses nothing: no closed subpath, no height or width, an
/// inverted (unbounded) path, coordinates that aren't finite, or more than
/// [`MAX_AREA_EDGES`] edges or [`MAX_AREA_COMPONENTS`] components. A component with no
/// closed subpath encloses nothing and is left out, so an open path drawn with Intersect
/// doesn't empty the shape.
pub fn new(path: &Path, vertical: bool) -> Option<AreaShape> {
if path.inverted {
return None;
}
let map = |x: f64, y: f64| -> Option<(f32, f32)> { if vertical { Some((small(y)?, small(-x)?)) } else { Some((small(x)?, small(y)?)) } };
let mut edges: Vec<Edge> = Vec::new();
let mut comps: Vec<Component> = Vec::new();
for range in path.components() {
let op = path.effective_op(range.start);
let start = edges.len();
for sub in path.subpaths.get(range).unwrap_or(&[]) {
if !sub.closed {
continue;
}
let mut pts: Vec<(f32, f32)> = Vec::new();
for seg in sub.segments() {
if pts.is_empty() {
pts.push(map(seg[0].x, seg[0].y)?);
}
if same(seg[1], seg[0]) && same(seg[2], seg[3]) {
pts.push(map(seg[3].x, seg[3].y)?);
} else {
for j in 1..=CURVE_PIECES {
let (x, y) = cubic(&seg, j as f64 / CURVE_PIECES as f64);
pts.push(map(x, y)?);
}
}
if edges.len().saturating_add(pts.len()) > MAX_AREA_EDGES {
return None;
}
}
// Closing edge back to the first point.
if let Some(&first) = pts.first() {
pts.push(first);
}
for w in pts.windows(2) {
if let [(x0, y0), (x1, y1)] = *w {
edges.push(Edge { x0, y0, x1, y1, lo: y0.min(y1), hi: y0.max(y1) });
}
}
if edges.len() > MAX_AREA_EDGES {
return None;
}
}
if edges.len() == start {
continue;
}
if comps.len() >= MAX_AREA_COMPONENTS {
return None;
}
if let Some(mine) = edges.get_mut(start..) {
mine.sort_by(|a, b| a.lo.total_cmp(&b.lo));
}
let max_h = edges.get(start..).unwrap_or(&[]).iter().map(|e| e.hi - e.lo).fold(0.0f32, f32::max);
comps.push(Component { op, edges: start..edges.len(), max_h });
}
let mut b = [f32::INFINITY, f32::INFINITY, f32::NEG_INFINITY, f32::NEG_INFINITY];
for e in &edges {
b = [b[0].min(e.x0).min(e.x1), b[1].min(e.y0).min(e.y1), b[2].max(e.x0).max(e.x1), b[3].max(e.y0).max(e.y1)];
}
if edges.is_empty() || !(b[2] - b[0] >= 1.0 && b[3] - b[1] >= 1.0) {
return None;
}
Some(AreaShape { edges, comps, rule: path.fill_rule, bounds: b })
}
fn filled(&self, winding: i32) -> bool {
match self.rule {
FillRule::NonZero => winding != 0,
FillRule::EvenOdd => winding & 1 != 0,
}
}
/// Edges of `c` that may overlap `[ya, yb]` (a superset), found by binary search.
fn candidates(&self, c: &Component, ya: f32, yb: f32) -> &[Edge] {
let all = self.edges.get(c.edges.clone()).unwrap_or(&[]);
// Slack covers f32 rounding of `max_h` and of the subtraction; extras are filtered exactly later.
let slack = (ya.abs() + c.max_h) * 1e-6 + 1e-3;
let from = all.partition_point(|e| e.lo < ya - c.max_h - slack);
let to = all.partition_point(|e| e.lo <= yb);
all.get(from..to.max(from)).unwrap_or(&[])
}
/// Inside intervals of one component on row `y` (half-open in y, so a vertex is counted once).
fn component_intervals(&self, c: &Component, y: f32) -> Vec<(f32, f32)> {
let mut xs: Vec<(f32, i32)> = Vec::new();
for e in self.candidates(c, y, y) {
if e.lo <= y && y < e.hi {
let dir = if e.y0 < e.y1 { 1 } else { -1 };
let t = (y - e.y0) / (e.y1 - e.y0);
xs.push((e.x0 + t * (e.x1 - e.x0), dir));
}
}
xs.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut out = Vec::new();
let (mut winding, mut start) = (0i32, 0.0f32);
for (x, dir) in xs {
let was = self.filled(winding);
winding = winding.saturating_add(dir);
let now = self.filled(winding);
if !was && now {
start = x;
} else if was && !now && x > start {
out.push((start, x));
}
}
out
}
/// Inside intervals of the whole path on row `y`, components folded in with their ops.
fn intervals_at(&self, y: f32) -> Vec<(f32, f32)> {
let mut acc: Vec<(f32, f32)> = Vec::new();
for c in &self.comps {
let v = self.component_intervals(c, y);
acc = match c.op {
PathOp::Combine | PathOp::Join => boolean(&acc, &v, |a, b| a || b),
PathOp::Subtract => boolean(&acc, &v, |a, b| a && !b),
PathOp::Intersect => boolean(&acc, &v, |a, b| a && b),
PathOp::Exclude => boolean(&acc, &v, |a, b| a != b),
};
}
acc
}
/// The x-ranges swept by the edges of `c` while inside `[y0, y1]`, sorted and merged.
fn swept(&self, c: &Component, y0: f32, y1: f32) -> Vec<(f32, f32)> {
let mut v: Vec<(f32, f32)> = Vec::new();
for e in self.candidates(c, y0, y1) {
if e.hi < y0 || e.lo > y1 {
continue;
}
if e.lo == e.hi {
// A horizontal edge only matters strictly inside the band.
if e.lo > y0 && e.lo < y1 {
v.push((e.x0.min(e.x1), e.x0.max(e.x1)));
}
continue;
}
let at = |y: f32| e.x0 + (y - e.y0) / (e.y1 - e.y0) * (e.x1 - e.x0);
let (xa, xb) = (at(e.lo.max(y0)), at(e.hi.min(y1)));
v.push((xa.min(xb), xa.max(xb)));
}
v.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut out: Vec<(f32, f32)> = Vec::new();
for (l, r) in v {
match out.last_mut() {
Some(last) if l <= last.1 => last.1 = last.1.max(r),
_ => out.push((l, r)),
}
}
out
}
/// Intervals inside the shape on every row of `[y0, y1]`, left to right, each at least
/// `min_width` wide.
///
/// Within one component a point is inside for the whole band exactly when it is inside on
/// the middle row and none of that component's edges crosses its vertical segment
/// (`whole`); it is inside on some row when either holds (`ever`). The components then fold
/// together with their ops, so an edge hidden inside another component's fill (the inner
/// edges of a speech bubble's tail) never cuts the row, and text never sits over a cutout:
/// Subtract takes away everything the cut ever covers.
pub fn spans(&self, y0: f32, y1: f32, min_width: f32) -> Vec<(f32, f32)> {
if !(y0.is_finite() && y1.is_finite()) || y1 < y0 {
return Vec::new();
}
let mid = y0 + (y1 - y0) * 0.5;
let mut whole: Vec<(f32, f32)> = Vec::new();
let mut ever: Vec<(f32, f32)> = Vec::new();
// A run of Combine / Join components is one union: gather its intervals and merge them
// once when the run ends. Folding each component into the growing result rewrote the
// whole list per component, quadratic for a shape of many disjoint components.
let (mut more_whole, mut more_ever) = (Vec::new(), Vec::new());
for c in &self.comps {
let inside = self.component_intervals(c, mid);
let edges = self.swept(c, y0, y1);
let w = boolean(&inside, &edges, |a, b| a && !b);
let e = boolean(&inside, &edges, |a, b| a || b);
if matches!(c.op, PathOp::Combine | PathOp::Join) {
more_whole.extend(w);
more_ever.extend(e);
continue;
}
(whole, ever) = (union_all(whole, &mut more_whole), union_all(ever, &mut more_ever));
(whole, ever) = match c.op {
PathOp::Combine | PathOp::Join => (whole, ever),
PathOp::Subtract => (boolean(&whole, &e, |a, b| a && !b), boolean(&ever, &w, |a, b| a && !b)),
PathOp::Intersect => (boolean(&whole, &w, |a, b| a && b), boolean(&ever, &e, |a, b| a && b)),
PathOp::Exclude => {
let both = boolean(&whole, &w, |a, b| a && b);
let x = boolean(&boolean(&whole, &e, |a, b| a && !b), &boolean(&w, &ever, |a, b| a && !b), |a, b| a || b);
(x, boolean(&boolean(&ever, &e, |a, b| a || b), &both, |a, b| a && !b))
}
};
}
union_all(whole, &mut more_whole).into_iter().filter(|(l, r)| r - l >= min_width).collect()
}
/// The first baseline at or below `from` whose band `[b - ascent, b + descent]` has spans
/// at least `min_width` wide, with those spans. `None` once the band leaves the shape.
pub fn next_row(&self, from: f32, ascent: f32, descent: f32, min_width: f32) -> Option<(f32, Vec<(f32, f32)>)> {
if !(from.is_finite() && ascent.is_finite() && descent.is_finite()) {
return None;
}
let from = from.max(self.bounds[1] + ascent);
let step = ((self.bounds[3] - self.bounds[1]) / 512.0).max(0.5);
let mut b = from;
for _ in 0..MAX_ROW_STEPS {
if b + descent > self.bounds[3] {
return None;
}
let s = self.spans(b - ascent, b + descent, min_width);
if !s.is_empty() {
return Some((b, s));
}
b += step;
}
None
}
/// Is `(x, y)` (area space) inside the shape?
pub fn contains(&self, x: f32, y: f32) -> bool {
self.intervals_at(y).iter().any(|&(l, r)| l <= x && x < r)
}
}
/// Bounds `(x0, y0, x1, y1)` of an area type path's anchors and control points, when every point
/// is finite and within the area coordinate limit (`1e7`), the same paths [`AreaShape::new`]
/// accepts. `None` for an empty path or one with a NaN, infinite or huge coordinate, so callers
/// that turn the bounds into a text box or a PSD rectangle never write NaN.
pub fn path_bounds(path: &Path) -> Option<(f64, f64, f64, f64)> {
let ok = |p: Point| p.x.is_finite() && p.y.is_finite() && p.x.abs() <= MAX_COORD && p.y.abs() <= MAX_COORD;
if !path.subpaths.iter().flat_map(|s| &s.knots).all(|k| ok(k.anchor) && ok(k.in_ctrl) && ok(k.out_ctrl)) {
return None;
}
path.control_bounds()
}
/// The union of the sorted, disjoint intervals `base` and the intervals in `more` (any order,
/// drained), as [`boolean`] with `a || b` gives it: touching intervals join, empty ones vanish.
fn union_all(base: Vec<(f32, f32)>, more: &mut Vec<(f32, f32)>) -> Vec<(f32, f32)> {
if more.is_empty() {
return base;
}
let mut all: Vec<(f32, f32)> = base.into_iter().chain(more.drain(..)).filter(|(l, r)| l < r).collect();
all.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut out: Vec<(f32, f32)> = Vec::with_capacity(all.len());
for (l, r) in all {
match out.last_mut() {
Some(last) if l <= last.1 => last.1 = last.1.max(r),
_ => out.push((l, r)),
}
}
out
}
/// Boolean combination of two sorted, disjoint interval lists, in one linear merge.
fn boolean(a: &[(f32, f32)], b: &[(f32, f32)], f: impl Fn(bool, bool) -> bool) -> Vec<(f32, f32)> {
let ends = |v: &[(f32, f32)]| -> Vec<f32> { v.iter().flat_map(|&(l, r)| [l, r]).collect() };
let (ea, eb) = (ends(a), ends(b));
let mut xs: Vec<f32> = Vec::with_capacity(ea.len() + eb.len());
let (mut i, mut j) = (0, 0);
while i < ea.len() || j < eb.len() {
let next = match (ea.get(i), eb.get(j)) {
(Some(&p), Some(&q)) if q < p => {
j += 1;
q
}
(Some(&p), _) => {
i += 1;
p
}
(None, Some(&q)) => {
j += 1;
q
}
(None, None) => break,
};
if xs.last() != Some(&next) {
xs.push(next);
}
}
let (mut ia, mut ib) = (0usize, 0usize);
let mut out: Vec<(f32, f32)> = Vec::new();
for w in xs.windows(2) {
let &[l, r] = w else { continue };
let mid = (l + r) * 0.5;
while a.get(ia).is_some_and(|s| s.1 <= mid) {
ia += 1;
}
while b.get(ib).is_some_and(|s| s.1 <= mid) {
ib += 1;
}
let in_a = a.get(ia).is_some_and(|s| s.0 <= mid);
let in_b = b.get(ib).is_some_and(|s| s.0 <= mid);
if f(in_a, in_b) {
match out.last_mut() {
Some(last) if last.1 == l => last.1 = r,
_ => out.push((l, r)),
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use photocraft_doc::vector::{FillRule, Knot, Path, PathOp, Subpath};
fn poly(pts: &[(f64, f64)]) -> Path {
Path::new(vec![Subpath::polygon(pts)])
}
fn close(a: (f32, f32), b: (f32, f32)) -> bool {
(a.0 - b.0).abs() < 0.01 && (a.1 - b.1).abs() < 0.01
}
#[test]
fn many_disjoint_components_union_like_the_pairwise_fold() {
// Within MAX_AREA_COMPONENTS: narrow columns, every other one overlapping its neighbour.
let cols: Vec<Subpath> = (0..2000)
.map(|i| {
let x = f64::from(i) * 3.0 + if i % 2 == 1 { -2.5 } else { 0.0 };
Subpath::polygon(&[(x, 0.0), (x + 1.0, 0.0), (x + 1.0, 100.0), (x, 100.0)]).with_op(PathOp::Combine)
})
.collect();
let a = AreaShape::new(&Path::new(cols), false).unwrap();
let got = a.spans(10.0, 20.0, 0.0);
// Each overlapping pair is one span: [3k, 3k + 1.5] for k = 0, 2, 4, ...
assert_eq!(got.len(), 1000);
for (k, &(l, r)) in got.iter().enumerate() {
let x = k as f32 * 6.0;
assert!((l - x).abs() < 1e-3 && (r - x - 1.5).abs() < 1e-3, "span {k}: {l}..{r}");
}
// An empty interval adds nothing, a touching one joins.
assert_eq!(union_all(vec![(0.0, 1.0)], &mut vec![(5.0, 5.0), (1.0, 2.0)]), [(0.0, 2.0)]);
}
#[test]
fn rectangle_band_is_its_width() {
let a = AreaShape::new(&poly(&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)]), false).unwrap();
assert_eq!(a.bounds, [0.0, 0.0, 100.0, 50.0]);
let s = a.spans(10.0, 20.0, 1.0);
assert_eq!(s.len(), 1);
assert!(close(s[0], (0.0, 100.0)), "{s:?}");
// A band leaving the shape has no span.
assert!(a.spans(40.0, 60.0, 1.0).is_empty());
}
#[test]
fn triangle_band_is_its_narrowest_row() {
// Apex at the top: the width at y is y.
let a = AreaShape::new(&poly(&[(50.0, 0.0), (100.0, 100.0), (0.0, 100.0)]), false).unwrap();
let s = a.spans(40.0, 60.0, 1.0);
assert_eq!(s.len(), 1);
assert!(close(s[0], (30.0, 70.0)), "{s:?}");
// Narrower than min_width: dropped.
assert!(a.spans(5.0, 10.0, 20.0).is_empty());
}
#[test]
fn hole_splits_the_row() {
let outer = Subpath::polygon(&[(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)]);
let hole = Subpath::polygon(&[(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)]).with_op(PathOp::Subtract);
let a = AreaShape::new(&Path::new(vec![outer.clone(), hole]), false).unwrap();
let s = a.spans(45.0, 55.0, 1.0);
assert_eq!(s.len(), 2, "{s:?}");
assert!(close(s[0], (0.0, 40.0)) && close(s[1], (60.0, 100.0)), "{s:?}");
// The same hole as a joined subpath under even-odd (a custom shape's counter).
let joined = Subpath::polygon(&[(40.0, 40.0), (60.0, 40.0), (60.0, 60.0), (40.0, 60.0)]).with_op(PathOp::Join);
let mut p = Path::new(vec![outer, joined]);
p.fill_rule = FillRule::EvenOdd;
assert_eq!(AreaShape::new(&p, false).unwrap().spans(45.0, 55.0, 1.0).len(), 2);
}
#[test]
fn intersect_and_exclude_follow_photoshop_ops() {
let a = Subpath::polygon(&[(0.0, 0.0), (60.0, 0.0), (60.0, 10.0), (0.0, 10.0)]);
let b = |op| Subpath::polygon(&[(40.0, 0.0), (100.0, 0.0), (100.0, 10.0), (40.0, 10.0)]).with_op(op);
let i = AreaShape::new(&Path::new(vec![a.clone(), b(PathOp::Intersect)]), false).unwrap().spans(2.0, 8.0, 1.0);
assert!(i.len() == 1 && close(i[0], (40.0, 60.0)), "{i:?}");
let x = AreaShape::new(&Path::new(vec![a, b(PathOp::Exclude)]), false).unwrap().spans(2.0, 8.0, 1.0);
assert!(x.len() == 2 && close(x[0], (0.0, 40.0)) && close(x[1], (60.0, 100.0)), "{x:?}");
}
#[test]
fn curves_are_flattened() {
// A circle of radius 50 centred on (50, 50) from four kappa curves.
let k = 0.552_284_75 * 50.0;
let c = |x: f64, y: f64, ix: f64, iy: f64, ox: f64, oy: f64| {
Knot::smooth(photocraft_geom::Point::new(x, y), photocraft_geom::Point::new(ix, iy), photocraft_geom::Point::new(ox, oy))
};
let circle = Subpath {
closed: true,
knots: vec![
c(50.0, 0.0, 50.0 - k, 0.0, 50.0 + k, 0.0),
c(100.0, 50.0, 100.0, 50.0 - k, 100.0, 50.0 + k),
c(50.0, 100.0, 50.0 + k, 100.0, 50.0 - k, 100.0),
c(0.0, 50.0, 0.0, 50.0 + k, 0.0, 50.0 - k),
],
op: PathOp::Combine,
};
let a = AreaShape::new(&Path::new(vec![circle]), false).unwrap();
let s = a.spans(49.0, 51.0, 1.0);
assert!(s.len() == 1 && s[0].0 < 1.0 && s[0].1 > 99.0, "{s:?}");
assert!(a.contains(50.0, 50.0) && !a.contains(3.0, 3.0));
}
/// A 260×160 ellipse at the origin from four kappa curves.
fn ellipse() -> Subpath {
let (cx, cy, rx, ry) = (130.0, 80.0, 130.0, 80.0);
let (kx, ky) = (0.552_284_75 * rx, 0.552_284_75 * ry);
let p = photocraft_geom::Point::new;
let c = |x: f64, y: f64, ix: f64, iy: f64, ox: f64, oy: f64| Knot::smooth(p(x, y), p(ix, iy), p(ox, oy));
Subpath {
closed: true,
knots: vec![
c(cx, cy - ry, cx - kx, cy - ry, cx + kx, cy - ry),
c(cx + rx, cy, cx + rx, cy - ky, cx + rx, cy + ky),
c(cx, cy + ry, cx + kx, cy + ry, cx - kx, cy + ry),
c(cx - rx, cy, cx - rx, cy + ky, cx - rx, cy - ky),
],
op: PathOp::Combine,
}
}
/// The speech bubble: the ellipse combined with a tail whose wide end sits inside it.
fn bubble() -> AreaShape {
let tail = Subpath::polygon(&[(120.0, 64.0), (180.0, 64.0), (230.0, 210.0)]).with_op(PathOp::Combine);
AreaShape::new(&Path::new(vec![ellipse(), tail]), false).unwrap()
}
#[test]
fn combined_overlap_hides_inner_edges() {
let a = bubble();
// Rows through the overlap: the tail's edges inside the ellipse must not cut the row.
for y0 in [56.0f32, 70.0, 90.0, 110.0, 120.0] {
let s = a.spans(y0, y0 + 18.0, 1.0);
assert_eq!(s.len(), 1, "band {y0}: {s:?}");
// The ellipse's own edge bounds the row on both sides.
let dy = (y0 - 80.0).abs().max((y0 + 18.0 - 80.0).abs());
let half = 130.0 * (1.0 - (dy / 80.0).powi(2)).sqrt();
assert!((s[0].0 - (130.0 - half)).abs() < 0.5 && (s[0].1 - (130.0 + half)).abs() < 0.5, "band {y0}: {s:?}");
}
// Lower down the tail pokes out on the right: still one span, out to the tail's edge.
let s = a.spans(130.0, 148.0, 1.0);
assert!(s.len() == 1 && s[0].1 > 202.0, "{s:?}");
// Below the ellipse only the tail is left.
let s = a.spans(165.0, 183.0, 1.0);
assert!(s.len() == 1 && s[0].0 > 190.0 && s[0].1 < 220.0, "{s:?}");
}
#[test]
fn component_without_edges_is_left_out() {
let rect = Subpath::polygon(&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)]);
let open = Subpath::polyline(&[(10.0, 10.0), (90.0, 40.0)]).with_op(PathOp::Intersect);
let a = AreaShape::new(&Path::new(vec![rect, open]), false).unwrap();
let s = a.spans(10.0, 20.0, 1.0);
assert!(s.len() == 1 && close(s[0], (0.0, 100.0)), "{s:?}");
}
#[test]
fn too_many_components_give_no_area() {
let square = |i: usize| {
let x = (i % 100) as f64 * 3.0;
let y = (i / 100) as f64 * 3.0;
Subpath::polygon(&[(x, y), (x + 2.0, y), (x + 2.0, y + 2.0), (x, y + 2.0)])
};
let at_cap: Vec<Subpath> = (0..MAX_AREA_COMPONENTS).map(square).collect();
assert!(AreaShape::new(&Path::new(at_cap), false).is_some());
let over: Vec<Subpath> = (0..=MAX_AREA_COMPONENTS).map(square).collect();
assert!(AreaShape::new(&Path::new(over), false).is_none());
}
#[test]
fn path_bounds_need_finite_small_points() {
assert_eq!(path_bounds(&poly(&[(1.0, 2.0), (30.0, 2.0), (30.0, 40.0)])), Some((1.0, 2.0, 30.0, 40.0)));
assert_eq!(path_bounds(&Path::default()), None);
for bad in [f64::NAN, f64::INFINITY, -f64::INFINITY, 2e7] {
// Anywhere in the path, not just the first point (`f64::min` skips a NaN).
assert_eq!(path_bounds(&poly(&[(0.0, 0.0), (10.0, bad), (10.0, 10.0)])), None, "{bad}");
assert_eq!(path_bounds(&poly(&[(bad, 0.0), (10.0, 0.0), (10.0, 10.0)])), None, "{bad}");
}
}
#[test]
fn next_row_skips_the_narrow_top() {
let a = AreaShape::new(&poly(&[(50.0, 0.0), (100.0, 100.0), (0.0, 100.0)]), false).unwrap();
// Ascent 8: the band's top (b - 8) needs width ≥ 30, so b ≥ 38.
let (b, s) = a.next_row(8.0, 8.0, 2.0, 30.0).unwrap();
assert!((b - 38.0).abs() <= 0.51, "{b}");
assert!(s[0].1 - s[0].0 >= 30.0);
// Past the bottom: no row.
assert!(a.next_row(99.0, 8.0, 2.0, 1.0).is_none());
}
#[test]
fn next_row_from_far_above_still_finds_rows() {
let a = AreaShape::new(&poly(&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)]), false).unwrap();
let (b, s) = a.next_row(-1000.0, 8.0, 2.0, 10.0).unwrap();
assert!((b - 8.0).abs() < 0.6 && close(s[0], (0.0, 100.0)), "{b} {s:?}");
}
#[test]
fn tall_edge_survives_rounding_at_its_end() {
// The tallest edge's height and `y - height` both round; the lookup must still find it.
let a = AreaShape::new(&poly(&[(0.0, -1898.2166), (10.0, 212.32651), (0.0, 212.32651)]), false).unwrap();
let y = 212.32649_f32;
assert!(a.contains(5.0, y));
let s = a.spans(y, y, 1.0);
assert!(s.len() == 1 && s[0].0 < 0.01 && s[0].1 > 9.9, "{s:?}");
}
#[test]
fn slanted_hole_is_never_spanned() {
let outer = Subpath::polygon(&[(0.0, 0.0), (100.0, 0.0), (100.0, 100.0), (0.0, 100.0)]);
let strip = || Subpath::polygon(&[(5.0, 0.0), (8.0, 0.0), (98.0, 100.0), (95.0, 100.0)]);
let sub = Path::new(vec![outer.clone(), strip().with_op(PathOp::Subtract)]);
let mut eo = Path::new(vec![outer, strip().with_op(PathOp::Join)]);
eo.fill_rule = FillRule::EvenOdd;
for p in [sub, eo] {
let s = AreaShape::new(&p, false).unwrap().spans(40.0, 60.0, 1.0);
assert!(!s.is_empty());
assert!(s.iter().all(|&(l, r)| r <= 50.0 || l >= 53.0), "{s:?}");
}
}
#[test]
fn vertical_maps_columns_right_to_left() {
// Text space 100 wide, 50 tall; area space is (y, -x): x in 0..50, y in -100..0.
let a = AreaShape::new(&poly(&[(0.0, 0.0), (100.0, 0.0), (100.0, 50.0), (0.0, 50.0)]), true).unwrap();
assert_eq!(a.bounds, [0.0, -100.0, 50.0, 0.0]);
let s = a.spans(-60.0, -40.0, 1.0);
assert!(s.len() == 1 && close(s[0], (0.0, 50.0)), "{s:?}");
}
#[test]
fn degenerate_and_hostile_paths_give_no_area() {
assert!(AreaShape::new(&Path::default(), false).is_none());
assert!(AreaShape::new(&Path::new(vec![Subpath::polyline(&[(0.0, 0.0), (10.0, 10.0), (0.0, 10.0)])]), false).is_none(), "open only");
assert!(AreaShape::new(&poly(&[(0.0, 0.0), (10.0, 0.0), (20.0, 0.0)]), false).is_none(), "no height");
assert!(AreaShape::new(&poly(&[(0.0, 0.0), (f64::NAN, 0.0), (5.0, 5.0)]), false).is_none());
assert!(AreaShape::new(&poly(&[(0.0, 0.0), (1e300, 0.0), (5.0, 5.0)]), false).is_none(), "beyond f32");
let mut inv = poly(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0)]);
inv.inverted = true;
assert!(AreaShape::new(&inv, false).is_none(), "an inverted path is unbounded");
let many: Vec<(f64, f64)> = (0..MAX_AREA_EDGES + 10).map(|i| ((i as f64).cos() * 50.0, (i as f64).sin() * 50.0)).collect();
assert!(AreaShape::new(&poly(&many), false).is_none());
assert!(AreaShape::new(&poly(&[(0.0, 0.0), (1e8, 0.0), (5.0, 5.0)]), false).is_none(), "beyond 1e7");
// Bad bands never panic.
let a = AreaShape::new(&poly(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0)]), false).unwrap();
assert!(a.spans(f32::NAN, 5.0, 1.0).is_empty());
assert!(a.spans(5.0, 1.0, 1.0).is_empty());
assert!(a.next_row(f32::INFINITY, 1.0, 1.0, 1.0).is_none());
}
}
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.