use super::{Point, Polygon};
use crate::section::Section;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Axis {
X,
Y,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Transform {
Translate { dx: f64, dy: f64 },
Rotate { angle: f64 },
Scale { factor: f64 },
MirrorX,
MirrorY,
}
impl Transform {
pub fn apply(&self, p: Point) -> Point {
match *self {
Transform::Translate { dx, dy } => Point::new(p.x + dx, p.y + dy),
Transform::Rotate { angle } => {
let (s, c) = angle.sin_cos();
Point::new(p.x * c - p.y * s, p.x * s + p.y * c)
}
Transform::Scale { factor } => Point::new(p.x * factor, p.y * factor),
Transform::MirrorX => Point::new(p.x, -p.y),
Transform::MirrorY => Point::new(-p.x, p.y),
}
}
}
#[derive(Debug, Clone)]
pub struct Geometry {
pub outer: Polygon,
pub holes: Vec<Polygon>,
pub transforms: Vec<Transform>,
}
impl Geometry {
pub fn new(mut outer: Polygon, mut holes: Vec<Polygon>) -> Self {
if outer.signed_area() < 0.0 {
outer.vertices.reverse();
}
for hole in &mut holes {
if hole.signed_area() > 0.0 {
hole.vertices.reverse();
}
}
Self {
outer,
holes,
transforms: Vec::new(),
}
}
pub fn from_points(points: Vec<Point>, holes: Vec<Vec<Point>>) -> Self {
Self::new(
Polygon::new(points),
holes.into_iter().map(Polygon::new).collect(),
)
}
pub fn from_section(section: &crate::section::Section) -> Self {
Self::new(section.outer.clone(), section.holes.clone())
}
pub fn rotate(mut self, angle_degrees: f64) -> Self {
self.transforms.push(Transform::Rotate {
angle: angle_degrees.to_radians(),
});
self
}
pub fn rotate_about(mut self, angle_degrees: f64, point: Point) -> Self {
self.transforms.push(Transform::Translate {
dx: -point.x,
dy: -point.y,
});
self.transforms.push(Transform::Rotate {
angle: angle_degrees.to_radians(),
});
self.transforms.push(Transform::Translate {
dx: point.x,
dy: point.y,
});
self
}
pub fn mirror(mut self, axis: Axis) -> Self {
self.transforms.push(match axis {
Axis::X => Transform::MirrorX,
Axis::Y => Transform::MirrorY,
});
self
}
pub fn shift(mut self, dx: f64, dy: f64) -> Self {
self.transforms.push(Transform::Translate { dx, dy });
self
}
pub fn align_center(&self) -> Self {
let c = self.centroid();
let mut g = self.clone();
g.transforms
.push(Transform::Translate { dx: -c.x, dy: -c.y });
g
}
pub fn align_to(&self, other: &Self) -> Self {
let (l1, r1, b1, t1) = self.bounds();
let (l2, r2, b2, t2) = other.bounds();
let dx = if (l1 - l2).abs() < (r1 - r2).abs() {
l2 - l1
} else {
r2 - r1
};
let dy = if (b1 - b2).abs() < (t1 - t2).abs() {
b2 - b1
} else {
t2 - t1
};
if dx == 0.0 && dy == 0.0 {
return self.clone();
}
let mut g = self.clone();
g.transforms.push(Transform::Translate { dx, dy });
g
}
pub fn offset(&self, amount: f64) -> Option<Self> {
let outer = self.apply_transforms().outer.offset(amount)?;
let mut holes = Vec::with_capacity(self.holes.len());
for h in &self.holes {
holes.push(h.offset(-amount)?);
}
Some(Self {
outer,
holes,
transforms: Vec::new(),
})
}
pub fn split_section(&self, a: Point, b: Point) -> (Option<Geometry>, Option<Geometry>) {
let g = self.apply_transforms();
let (below_outer, above_outer) = g.outer.split_by_line(a, b);
let mut below_holes = Vec::new();
let mut above_holes = Vec::new();
for h in &g.holes {
let (hb, ha) = h.split_by_line(a, b);
if let Some(hb) = hb {
below_holes.push(hb);
}
if let Some(ha) = ha {
above_holes.push(ha);
}
}
let below = below_outer.map(|o| Geometry {
outer: o,
holes: below_holes,
transforms: Vec::new(),
});
let above = above_outer.map(|o| Geometry {
outer: o,
holes: above_holes,
transforms: Vec::new(),
});
(below, above)
}
pub fn union(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
self.boolean_op(other, super::boolean::BoolOp::Union)
}
pub fn intersection(
&self,
other: &Self,
) -> Result<CompoundGeometry, super::boolean::BooleanError> {
self.boolean_op(other, super::boolean::BoolOp::Intersection)
}
pub fn subtract(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
self.boolean_op(other, super::boolean::BoolOp::Difference)
}
fn boolean_op(
&self,
other: &Self,
op: super::boolean::BoolOp,
) -> Result<CompoundGeometry, super::boolean::BooleanError> {
let a_trans = self.apply_transforms();
let b_trans = other.apply_transforms();
let a = Section::new(a_trans.outer, a_trans.holes);
let b = Section::new(b_trans.outer, b_trans.holes);
let results = match op {
super::boolean::BoolOp::Union => super::boolean::section_union(&a, &b)?,
super::boolean::BoolOp::Intersection => super::boolean::section_intersection(&a, &b)?,
super::boolean::BoolOp::Difference => super::boolean::section_difference(&a, &b)?,
};
let geometries = results
.into_iter()
.map(|sec| Geometry::new(sec.outer, sec.holes))
.collect();
Ok(CompoundGeometry::new(geometries))
}
pub fn apply_transforms(&self) -> Self {
if self.transforms.is_empty() {
return self.clone();
}
let map = |poly: &Polygon| -> Polygon {
Polygon::new(
poly.vertices
.iter()
.map(|&v| self.transforms.iter().fold(v, |p, t| t.apply(p)))
.collect(),
)
};
Self {
outer: map(&self.outer),
holes: self.holes.iter().map(map).collect(),
transforms: Vec::new(),
}
}
pub fn area(&self) -> f64 {
let g = if self.transforms.is_empty() {
self
} else {
&self.apply_transforms()
};
let mut a = g.outer.area();
for h in &g.holes {
a -= h.area();
}
a
}
pub fn centroid(&self) -> Point {
let g = if self.transforms.is_empty() {
self
} else {
&self.apply_transforms()
};
let mut sum_x = 0.0;
let mut sum_y = 0.0;
let mut total = 0.0;
let outer_c = g.outer.centroid();
let outer_a = g.outer.area();
sum_x += outer_c.x * outer_a;
sum_y += outer_c.y * outer_a;
total += outer_a;
for h in &g.holes {
let a = h.area();
let c = h.centroid();
sum_x -= c.x * a;
sum_y -= c.y * a;
total -= a;
}
Point::new(sum_x / total, sum_y / total)
}
pub fn bounds(&self) -> (f64, f64, f64, f64) {
let g = if self.transforms.is_empty() {
self
} else {
&self.apply_transforms()
};
let mut min_x = f64::INFINITY;
let mut max_x = f64::NEG_INFINITY;
let mut min_y = f64::INFINITY;
let mut max_y = f64::NEG_INFINITY;
for poly in std::iter::once(&g.outer).chain(g.holes.iter()) {
for v in &poly.vertices {
min_x = min_x.min(v.x);
max_x = max_x.max(v.x);
min_y = min_y.min(v.y);
max_y = max_y.max(v.y);
}
}
(min_x, max_x, min_y, max_y)
}
pub fn perimeter(&self) -> f64 {
let g = if self.transforms.is_empty() {
self
} else {
&self.apply_transforms()
};
g.outer.perimeter() + g.holes.iter().map(|h| h.perimeter()).sum::<f64>()
}
}
#[derive(Debug, Clone)]
pub struct CompoundGeometry {
pub geometries: Vec<Geometry>,
}
#[derive(Debug, Clone, PartialEq)]
pub enum CompoundError {
OverlappingRegions { a: usize, b: usize },
HoleNotInsideOuter { region: usize, hole: usize },
NestedHoles { region: usize, a: usize, b: usize },
}
impl std::fmt::Display for CompoundError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
CompoundError::OverlappingRegions { a, b } => {
write!(f, "regions {a} and {b} have overlapping material")
}
CompoundError::HoleNotInsideOuter { region, hole } => {
write!(
f,
"hole {hole} of region {region} is not fully inside its outer boundary"
)
}
CompoundError::NestedHoles { region, a, b } => {
write!(
f,
"region {region} has hole {b} nested inside hole {a} (holes cannot nest)"
)
}
}
}
}
impl std::error::Error for CompoundError {}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum BBoxRelation {
Disjoint,
Touch,
Overlap,
}
fn outer_bbox_relation(a: &Polygon, b: &Polygon) -> BBoxRelation {
let bbox = |pts: &[Point]| {
pts.iter().fold(
(
f64::INFINITY,
f64::NEG_INFINITY,
f64::INFINITY,
f64::NEG_INFINITY,
),
|(l, r, b, t), p| (l.min(p.x), r.max(p.x), b.min(p.y), t.max(p.y)),
)
};
let (al, ar, ab, at) = bbox(&a.vertices);
let (bl, br, bb, bt) = bbox(&b.vertices);
if ar < bl || br < al || at < bb || bt < ab {
return BBoxRelation::Disjoint;
}
let x_touch = ar == bl || br == al;
let y_touch = at == bb || bt == ab;
if x_touch || y_touch {
return BBoxRelation::Touch;
}
BBoxRelation::Overlap
}
impl CompoundGeometry {
pub fn new(geometries: Vec<Geometry>) -> Self {
Self { geometries }
}
pub fn new_validated(geometries: Vec<Geometry>) -> Result<Self, CompoundError> {
let compound = Self { geometries };
compound.validate()?;
Ok(compound)
}
#[deprecated(
since = "0.1.0",
note = "Use dissolved_outer_only() for explicit naming; holes are dropped"
)]
pub fn dissolved(geometries: Vec<Geometry>) -> Self {
Self::dissolved_outer_only(geometries)
}
pub fn dissolved_outer_only(geometries: Vec<Geometry>) -> Self {
use super::boolean::{BoolOp, polygon_boolean};
let mut acc: Vec<Polygon> = geometries
.iter()
.map(|g| g.apply_transforms().outer)
.collect();
loop {
let mut merged: Option<(usize, usize, Vec<Polygon>)> = None;
'outer: for i in 0..acc.len() {
for j in (i + 1)..acc.len() {
if matches!(
outer_bbox_relation(&acc[i], &acc[j]),
BBoxRelation::Disjoint
) {
continue;
}
let u = polygon_boolean(&acc[i], &acc[j], BoolOp::Union);
let u_area: f64 = u.iter().map(|p| p.area().abs()).sum();
let sum_area = acc[i].area().abs() + acc[j].area().abs();
if u_area < sum_area - 1e-9 {
merged = Some((i, j, u));
break 'outer;
}
}
}
match merged {
Some((i, j, u)) => {
let last = acc.len() - 1;
acc[j] = acc[last].clone();
acc.swap_remove(last);
acc.splice(i..i + 1, u);
}
None => break,
}
}
let geometries = acc
.into_iter()
.map(|p| Geometry {
outer: p,
holes: Vec::new(),
transforms: Vec::new(),
})
.collect();
Self { geometries }
}
pub fn validate(&self) -> Result<(), CompoundError> {
for (ri, g) in self.geometries.iter().enumerate() {
let g = g.apply_transforms();
for (hi, hole) in g.holes.iter().enumerate() {
let vertices_inside = hole.vertices.iter().all(|v| g.outer.contains_point(*v));
if !vertices_inside {
return Err(CompoundError::HoleNotInsideOuter {
region: ri,
hole: hi,
});
}
for i in 0..hole.vertices.len() {
let h1 = hole.vertices[i];
let h2 = hole.vertices[(i + 1) % hole.vertices.len()];
for j in 0..g.outer.vertices.len() {
let o1 = g.outer.vertices[j];
let o2 = g.outer.vertices[(j + 1) % g.outer.vertices.len()];
if segments_interact(h1, h2, o1, o2) {
return Err(CompoundError::HoleNotInsideOuter {
region: ri,
hole: hi,
});
}
}
}
}
for a in 0..g.holes.len() {
for b in (a + 1)..g.holes.len() {
let ha = &g.holes[a];
let hb = &g.holes[b];
let a_contains_b = hb.vertices.iter().all(|v| ha.contains_point(*v));
let b_contains_a = ha.vertices.iter().all(|v| hb.contains_point(*v));
if a_contains_b || b_contains_a {
return Err(CompoundError::NestedHoles { region: ri, a, b });
}
}
}
}
let n = self.geometries.len();
if n < 2 {
return Ok(());
}
let applied: Vec<Geometry> = self
.geometries
.iter()
.map(|g| g.apply_transforms())
.collect();
for i in 0..n {
for j in (i + 1)..n {
let gi = &applied[i];
let gj = &applied[j];
if regions_overlap_deterministic(gi, gj) {
return Err(CompoundError::OverlappingRegions { a: i, b: j });
}
}
}
Ok(())
}
pub fn from_sections(sections: &[crate::section::Section]) -> Self {
Self {
geometries: sections.iter().map(Geometry::from_section).collect(),
}
}
pub fn boolean(
&self,
other: &Self,
op: super::boolean::BoolOp,
) -> Result<Self, super::boolean::BooleanError> {
match op {
super::boolean::BoolOp::Intersection => {
let mut out = Vec::new();
for ga in &self.geometries {
for gb in &other.geometries {
let inter = ga.boolean_op(gb, op)?;
out.extend(inter.geometries);
}
}
Ok(Self { geometries: out })
}
super::boolean::BoolOp::Difference => {
let mut current: Vec<Geometry> = self.geometries.clone();
for gb in &other.geometries {
let mut next = Vec::new();
for ga in ¤t {
let diff = ga.boolean_op(gb, op)?;
next.extend(diff.geometries);
}
current = next;
if current.is_empty() {
break;
}
}
let geometries = current
.into_iter()
.map(|g| Geometry {
outer: g.outer,
holes: g.holes,
transforms: Vec::new(),
})
.collect();
Ok(Self { geometries })
}
super::boolean::BoolOp::Union => {
let mut acc: Vec<Geometry> = self
.geometries
.iter()
.chain(other.geometries.iter())
.cloned()
.collect();
loop {
let mut merged: Option<(usize, usize, Vec<Geometry>)> = None;
'outer: for i in 0..acc.len() {
for j in (i + 1)..acc.len() {
if matches!(
outer_bbox_relation(&acc[i].outer, &acc[j].outer),
BBoxRelation::Disjoint
) {
continue;
}
let union_result =
acc[i].boolean_op(&acc[j], super::boolean::BoolOp::Union)?;
if union_result.geometries.len() == 1 {
merged = Some((i, j, union_result.geometries));
break 'outer;
}
}
}
match merged {
Some((i, j, new_geometries)) => {
let last = acc.len() - 1;
acc[j] = acc[last].clone();
acc.swap_remove(last);
acc.splice(i..i + 1, new_geometries);
}
None => break,
}
}
let geometries = acc;
Ok(Self { geometries })
}
}
}
pub fn union(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
self.boolean(other, super::boolean::BoolOp::Union)
}
pub fn intersection(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
self.boolean(other, super::boolean::BoolOp::Intersection)
}
pub fn subtract(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
self.boolean(other, super::boolean::BoolOp::Difference)
}
pub fn area(&self) -> f64 {
self.geometries.iter().map(|g| g.area()).sum()
}
pub fn centroid(&self) -> Point {
let mut sum_x = 0.0;
let mut sum_y = 0.0;
let mut total = 0.0;
for g in &self.geometries {
let a = g.area();
let c = g.centroid();
sum_x += c.x * a;
sum_y += c.y * a;
total += a;
}
assert!(
total.abs() > f64::EPSILON,
"CompoundGeometry has zero total area"
);
Point::new(sum_x / total, sum_y / total)
}
pub fn bounds(&self) -> (f64, f64, f64, f64) {
let mut min_x = f64::INFINITY;
let mut max_x = f64::NEG_INFINITY;
let mut min_y = f64::INFINITY;
let mut max_y = f64::NEG_INFINITY;
for g in &self.geometries {
let (l, r, b, t) = g.bounds();
min_x = min_x.min(l);
max_x = max_x.max(r);
min_y = min_y.min(b);
max_y = max_y.max(t);
}
(min_x, max_x, min_y, max_y)
}
pub fn perimeter(&self) -> f64 {
self.geometries.iter().map(|g| g.perimeter()).sum()
}
pub fn polygons(&self) -> Vec<Polygon> {
let mut out = Vec::new();
for g in &self.geometries {
let g = g.apply_transforms();
out.push(g.outer);
out.extend(g.holes);
}
out
}
}
impl From<crate::section::Section> for CompoundGeometry {
fn from(section: crate::section::Section) -> Self {
Self::new(vec![Geometry::new(section.outer, section.holes)])
}
}
fn intersection_point(a1: Point, a2: Point, b1: Point, b2: Point) -> Point {
let dx1 = a2.x - a1.x;
let dy1 = a2.y - a1.y;
let dx2 = b2.x - b1.x;
let dy2 = b2.y - b1.y;
let det = dx1 * dy2 - dy1 * dx2;
if det.abs() < 1e-12 {
let len2 = dx1 * dx1 + dy1 * dy1;
if len2 < 1e-24 {
return a1;
}
let t_b1 = ((b1.x - a1.x) * dx1 + (b1.y - a1.y) * dy1) / len2;
let t_b2 = ((b2.x - a1.x) * dx1 + (b2.y - a1.y) * dy1) / len2;
let b_lo = t_b1.min(t_b2);
let b_hi = t_b1.max(t_b2);
let lo = 0.0f64.max(b_lo);
let hi = 1.0f64.min(b_hi);
if lo <= hi {
let t_mid = (lo + hi) * 0.5;
return Point::new(a1.x + t_mid * dx1, a1.y + t_mid * dy1);
}
return Point::new((a1.x + a2.x) * 0.5, (a1.y + a2.y) * 0.5);
}
let t = ((b1.x - a1.x) * dy2 - (b1.y - a1.y) * dx2) / det;
let t = t.clamp(0.0, 1.0);
Point::new(a1.x + t * dx1, a1.y + t * dy1)
}
fn regions_overlap_deterministic(a: &Geometry, b: &Geometry) -> bool {
let a_outer = &a.outer;
let b_outer = &b.outer;
for i in 0..a_outer.vertices.len() {
let a1 = a_outer.vertices[i];
let a2 = a_outer.vertices[(i + 1) % a_outer.vertices.len()];
for j in 0..b_outer.vertices.len() {
let b1 = b_outer.vertices[j];
let b2 = b_outer.vertices[(j + 1) % b_outer.vertices.len()];
if segments_overlap(a1, a2, b1, b2) {
let pt = intersection_point(a1, a2, b1, b2);
let in_a_material =
a_outer.contains_point(pt) && !a.holes.iter().any(|h| h.contains_point(pt));
let in_b_material =
b_outer.contains_point(pt) && !b.holes.iter().any(|h| h.contains_point(pt));
if in_a_material && in_b_material {
return true;
}
}
}
}
for v in &a_outer.vertices {
if b_outer.contains_point(*v) && !b.holes.iter().any(|h| h.contains_point(*v)) {
return true;
}
}
for v in &b_outer.vertices {
if a_outer.contains_point(*v) && !a.holes.iter().any(|h| h.contains_point(*v)) {
return true;
}
}
let a_in_b = a_outer.vertices.iter().all(|v| b_outer.contains_point(*v));
let b_in_a = b_outer.vertices.iter().all(|v| a_outer.contains_point(*v));
if a_in_b || b_in_a {
let inter =
super::boolean::polygon_boolean(a_outer, b_outer, super::boolean::BoolOp::Intersection);
if inter.is_empty() {
return false;
}
let mut remaining = inter;
for hole in a.holes.iter().chain(b.holes.iter()) {
let mut next = Vec::new();
for p in &remaining {
let diff =
super::boolean::polygon_boolean(p, hole, super::boolean::BoolOp::Difference);
next.extend(diff);
}
remaining = next;
if remaining.is_empty() {
break;
}
}
return !remaining.is_empty();
}
false
}
#[derive(Debug, Clone, Copy, PartialEq)]
enum SegmentRelation {
Disjoint,
Touch,
ProperCross,
CollinearOverlap,
}
fn segment_relation(a1: Point, a2: Point, b1: Point, b2: Point) -> SegmentRelation {
const EPS: f64 = 1e-12;
fn orient(p: Point, q: Point, r: Point) -> f64 {
(q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)
}
fn on_segment(p: Point, q: Point, r: Point) -> bool {
q.x >= p.x.min(r.x) - EPS
&& q.x <= p.x.max(r.x) + EPS
&& q.y >= p.y.min(r.y) - EPS
&& q.y <= p.y.max(r.y) + EPS
}
fn points_equal(p: Point, q: Point) -> bool {
(p.x - q.x).abs() <= EPS && (p.y - q.y).abs() <= EPS
}
let o1 = orient(a1, a2, b1);
let o2 = orient(a1, a2, b2);
let o3 = orient(b1, b2, a1);
let o4 = orient(b1, b2, a2);
let o1_pos = o1 > EPS;
let o1_neg = o1 < -EPS;
let o2_pos = o2 > EPS;
let o2_neg = o2 < -EPS;
let o3_pos = o3 > EPS;
let o3_neg = o3 < -EPS;
let o4_pos = o4 > EPS;
let o4_neg = o4 < -EPS;
if (o1_pos != o2_pos || o1_neg != o2_neg) && (o3_pos != o4_pos || o3_neg != o4_neg) {
return SegmentRelation::ProperCross;
}
if o1.abs() <= EPS && o2.abs() <= EPS && o3.abs() <= EPS && o4.abs() <= EPS {
let a_min_x = a1.x.min(a2.x);
let a_max_x = a1.x.max(a2.x);
let b_min_x = b1.x.min(b2.x);
let b_max_x = b1.x.max(b2.x);
let a_min_y = a1.y.min(a2.y);
let a_max_y = a1.y.max(a2.y);
let b_min_y = b1.y.min(b2.y);
let b_max_y = b1.y.max(b2.y);
let overlap_x = a_max_x >= b_min_x - EPS && b_max_x >= a_min_x - EPS;
let overlap_y = a_max_y >= b_min_y - EPS && b_max_y >= a_min_y - EPS;
if overlap_x && overlap_y {
let len_a2 = (a2.x - a1.x).powi(2) + (a2.y - a1.y).powi(2);
let _len_b2 = (b2.x - b1.x).powi(2) + (b2.y - b1.y).powi(2);
let t_b1 = if len_a2 > EPS {
((b1.x - a1.x) * (a2.x - a1.x) + (b1.y - a1.y) * (a2.y - a1.y)) / len_a2
} else {
0.0
};
let t_b2 = if len_a2 > EPS {
((b2.x - a1.x) * (a2.x - a1.x) + (b2.y - a1.y) * (a2.y - a1.y)) / len_a2
} else {
0.0
};
let b_lo = t_b1.min(t_b2);
let b_hi = t_b1.max(t_b2);
let lo = 0.0f64.max(b_lo);
let hi = 1.0f64.min(b_hi);
if lo <= hi {
let overlap_len = (hi - lo) * len_a2.sqrt();
if overlap_len > EPS {
return SegmentRelation::CollinearOverlap;
} else {
return SegmentRelation::Touch;
}
}
}
return SegmentRelation::Disjoint;
}
if o1.abs() <= EPS && on_segment(a1, b1, a2) {
return if points_equal(b1, a1) || points_equal(b1, a2) {
SegmentRelation::Touch
} else {
SegmentRelation::Disjoint
};
}
if o2.abs() <= EPS && on_segment(a1, b2, a2) {
return if points_equal(b2, a1) || points_equal(b2, a2) {
SegmentRelation::Touch
} else {
SegmentRelation::Disjoint
};
}
if o3.abs() <= EPS && on_segment(b1, a1, b2) {
return if points_equal(a1, b1) || points_equal(a1, b2) {
SegmentRelation::Touch
} else {
SegmentRelation::Disjoint
};
}
if o4.abs() <= EPS && on_segment(b1, a2, b2) {
return if points_equal(a2, b1) || points_equal(a2, b2) {
SegmentRelation::Touch
} else {
SegmentRelation::Disjoint
};
}
SegmentRelation::Disjoint
}
pub fn segments_interact(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
!matches!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint)
}
pub fn segments_overlap(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
matches!(
segment_relation(a1, a2, b1, b2),
SegmentRelation::ProperCross | SegmentRelation::CollinearOverlap
)
}
#[cfg(test)]
mod tests {
use super::{Point, SegmentRelation, segment_relation, segments_interact, segments_overlap};
#[test]
fn segment_relation_proper_cross() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(10.0, 10.0);
let b1 = Point::new(0.0, 10.0);
let b2 = Point::new(10.0, 0.0);
assert_eq!(
segment_relation(a1, a2, b1, b2),
SegmentRelation::ProperCross
);
assert!(segments_overlap(a1, a2, b1, b2));
assert!(segments_interact(a1, a2, b1, b2));
}
#[test]
fn segment_relation_touch_endpoint() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(5.0, 0.0);
let b1 = Point::new(5.0, 0.0);
let b2 = Point::new(10.0, 0.0);
assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
assert!(!segments_overlap(a1, a2, b1, b2));
assert!(segments_interact(a1, a2, b1, b2));
}
#[test]
fn segment_relation_collinear_overlap() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(10.0, 0.0);
let b1 = Point::new(5.0, 0.0);
let b2 = Point::new(15.0, 0.0);
assert_eq!(
segment_relation(a1, a2, b1, b2),
SegmentRelation::CollinearOverlap
);
assert!(segments_overlap(a1, a2, b1, b2));
assert!(segments_interact(a1, a2, b1, b2));
}
#[test]
fn segment_relation_collinear_touch() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(5.0, 0.0);
let b1 = Point::new(5.0, 0.0);
let b2 = Point::new(10.0, 0.0);
assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
assert!(!segments_overlap(a1, a2, b1, b2));
assert!(segments_interact(a1, a2, b1, b2));
}
#[test]
fn segment_relation_disjoint() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(5.0, 0.0);
let b1 = Point::new(6.0, 0.0);
let b2 = Point::new(10.0, 0.0);
assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint);
assert!(!segments_overlap(a1, a2, b1, b2));
assert!(!segments_interact(a1, a2, b1, b2));
}
#[test]
fn segment_relation_cross_near_endpoint() {
let a1 = Point::new(0.0, 0.0);
let a2 = Point::new(10.0, 10.0);
let b1 = Point::new(0.0, 10.0);
let b2 = Point::new(10.0, 0.0);
assert_eq!(
segment_relation(a1, a2, b1, b2),
SegmentRelation::ProperCross
);
assert!(segments_overlap(a1, a2, b1, b2));
}
}