use crate::complexity::BooleanComplexity;
use crate::{
ComplexityLimits, Error, Path64, PathD, PathKind, Paths64, PathsD, validate_path_d,
validate_path64,
};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
#[repr(u8)]
pub enum ClipType {
Intersection = 1,
Union = 2,
Difference = 3,
Xor = 4,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
#[repr(u8)]
pub enum FillRule {
EvenOdd = 0,
NonZero = 1,
Positive = 2,
Negative = 3,
}
#[derive(Debug)]
pub struct BooleanRequest<'a, P> {
pub closed_subjects: &'a [P],
pub open_subjects: &'a [P],
pub clips: &'a [P],
pub clip_type: ClipType,
pub fill_rule: FillRule,
pub limits: ComplexityLimits,
}
impl<P> Copy for BooleanRequest<'_, P> {}
impl<P> Clone for BooleanRequest<'_, P> {
fn clone(&self) -> Self {
*self
}
}
impl<'a, P> BooleanRequest<'a, P> {
#[must_use]
pub const fn new(
closed_subjects: &'a [P],
clips: &'a [P],
clip_type: ClipType,
fill_rule: FillRule,
) -> Self {
Self {
closed_subjects,
open_subjects: &[],
clips,
clip_type,
fill_rule,
limits: ComplexityLimits::DEFAULT,
}
}
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct BooleanOutput<P> {
pub closed: Vec<P>,
pub open: Vec<P>,
}
fn closed_request<'a, P>(
subjects: &'a [P],
clips: &'a [P],
clip_type: ClipType,
fill_rule: FillRule,
) -> BooleanRequest<'a, P> {
BooleanRequest::new(subjects, clips, clip_type, fill_rule)
}
pub fn boolean_op(request: BooleanRequest<'_, Path64>) -> Result<BooleanOutput<Path64>, Error> {
validate_bounded64(&request)?;
crate::boolean::boolean_op64(&request)
}
pub fn boolean_op_d(request: BooleanRequest<'_, PathD>) -> Result<BooleanOutput<PathD>, Error> {
validate_bounded_d(&request)?;
crate::boolean::boolean_op_d(&request)
}
fn validate_bounded64(request: &BooleanRequest<'_, Path64>) -> Result<(), Error> {
let mut validation_error = None;
let mut complexity = BooleanComplexity::default();
for path in request.closed_subjects {
complexity.add_closed_subject(path.len());
if validation_error.is_none() {
validation_error = validate_path64(path, PathKind::Closed).err();
}
}
for path in request.open_subjects {
complexity.add_open_subject(path.len());
if validation_error.is_none() {
validation_error = validate_path64(path, PathKind::Open).err();
}
}
for path in request.clips {
complexity.add_clip(path.len());
if validation_error.is_none() {
validation_error = validate_path64(path, PathKind::Closed).err();
}
}
complexity.check(request.limits, request.clip_type == ClipType::Union)?;
validation_error.map_or(Ok(()), Err)
}
fn validate_bounded_d(request: &BooleanRequest<'_, PathD>) -> Result<(), Error> {
let mut validation_error = None;
let mut complexity = BooleanComplexity::default();
for path in request.closed_subjects {
complexity.add_closed_subject(path.len());
if validation_error.is_none() {
validation_error = validate_path_d(path, PathKind::Closed).err();
}
}
for path in request.open_subjects {
complexity.add_open_subject(path.len());
if validation_error.is_none() {
validation_error = validate_path_d(path, PathKind::Open).err();
}
}
for path in request.clips {
complexity.add_clip(path.len());
if validation_error.is_none() {
validation_error = validate_path_d(path, PathKind::Closed).err();
}
}
complexity.check(request.limits, request.clip_type == ClipType::Union)?;
validation_error.map_or(Ok(()), Err)
}
pub fn intersection(subjects: &[Path64], clips: &[Path64]) -> Result<Paths64, Error> {
boolean_op(closed_request(subjects, clips, ClipType::Intersection, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn union(subjects: &[Path64], clips: &[Path64]) -> Result<Paths64, Error> {
boolean_op(closed_request(subjects, clips, ClipType::Union, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn difference(subjects: &[Path64], clips: &[Path64]) -> Result<Paths64, Error> {
boolean_op(closed_request(subjects, clips, ClipType::Difference, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn xor(subjects: &[Path64], clips: &[Path64]) -> Result<Paths64, Error> {
boolean_op(closed_request(subjects, clips, ClipType::Xor, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn intersection_d(subjects: &[PathD], clips: &[PathD]) -> Result<PathsD, Error> {
boolean_op_d(closed_request(subjects, clips, ClipType::Intersection, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn union_d(subjects: &[PathD], clips: &[PathD]) -> Result<PathsD, Error> {
boolean_op_d(closed_request(subjects, clips, ClipType::Union, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn difference_d(subjects: &[PathD], clips: &[PathD]) -> Result<PathsD, Error> {
boolean_op_d(closed_request(subjects, clips, ClipType::Difference, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn xor_d(subjects: &[PathD], clips: &[PathD]) -> Result<PathsD, Error> {
boolean_op_d(closed_request(subjects, clips, ClipType::Xor, FillRule::EvenOdd))
.map(|output| output.closed)
}
pub fn intersection_path(subject: &Path64, clip: &Path64) -> Result<Paths64, Error> {
intersection(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn union_path(subject: &Path64, clip: &Path64) -> Result<Paths64, Error> {
union(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn difference_path(subject: &Path64, clip: &Path64) -> Result<Paths64, Error> {
difference(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn xor_path(subject: &Path64, clip: &Path64) -> Result<Paths64, Error> {
xor(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn intersection_path_d(subject: &PathD, clip: &PathD) -> Result<PathsD, Error> {
intersection_d(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn union_path_d(subject: &PathD, clip: &PathD) -> Result<PathsD, Error> {
union_d(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn difference_path_d(subject: &PathD, clip: &PathD) -> Result<PathsD, Error> {
difference_d(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
pub fn xor_path_d(subject: &PathD, clip: &PathD) -> Result<PathsD, Error> {
xor_d(std::slice::from_ref(subject), std::slice::from_ref(clip))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn exposes_stable_operation_values() {
assert_eq!(ClipType::Intersection as u8, 1);
assert_eq!(ClipType::Union as u8, 2);
assert_eq!(ClipType::Difference as u8, 3);
assert_eq!(ClipType::Xor as u8, 4);
assert_eq!(FillRule::EvenOdd as u8, 0);
assert_eq!(FillRule::NonZero as u8, 1);
assert_eq!(FillRule::Positive as u8, 2);
assert_eq!(FillRule::Negative as u8, 3);
}
#[test]
fn constructors_preserve_borrowed_inputs_and_options() {
let integer_subject = vec![crate::Point64::new(0, 0)];
let integer_clip = vec![crate::Point64::new(1, 1)];
let integer_request = BooleanRequest::new(
std::slice::from_ref(&integer_subject),
std::slice::from_ref(&integer_clip),
ClipType::Difference,
FillRule::Positive,
);
assert!(std::ptr::eq(
integer_request.closed_subjects[0].as_ptr(),
integer_subject.as_ptr()
));
assert!(std::ptr::eq(integer_request.clips[0].as_ptr(), integer_clip.as_ptr()));
assert_eq!(integer_request.clip_type, ClipType::Difference);
assert_eq!(integer_request.fill_rule, FillRule::Positive);
let cloned = Clone::clone(&integer_request);
assert_eq!(cloned.closed_subjects, integer_request.closed_subjects);
let double_subject = vec![crate::PointD::new(0.0, 0.0)];
let double_clip = vec![crate::PointD::new(1.0, 1.0)];
let double_request = BooleanRequest::new(
std::slice::from_ref(&double_subject),
std::slice::from_ref(&double_clip),
ClipType::Xor,
FillRule::Negative,
);
assert!(std::ptr::eq(double_request.closed_subjects[0].as_ptr(), double_subject.as_ptr()));
assert!(std::ptr::eq(double_request.clips[0].as_ptr(), double_clip.as_ptr()));
assert_eq!(double_request.clip_type, ClipType::Xor);
assert_eq!(double_request.fill_rule, FillRule::Negative);
}
#[test]
fn open_subjects_are_charged_only_against_relevant_filled_boundaries() {
let open = [(0..3_000).map(|x| crate::Point64::new(x, 0)).collect::<Path64>()];
let output = boolean_op(BooleanRequest {
closed_subjects: &[],
open_subjects: &open,
clips: &[],
clip_type: ClipType::Difference,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::new(1, 3_000, 0),
})
.expect("an isolated open polyline has no candidate edge pairs");
assert_eq!(output.open, open);
let open_d = [vec![crate::PointD::new(-1.0, 0.5), crate::PointD::new(2.0, 0.5)]];
let clip_d = [vec![
crate::PointD::new(0.0, 0.0),
crate::PointD::new(1.0, 0.0),
crate::PointD::new(1.0, 1.0),
crate::PointD::new(0.0, 1.0),
]];
let output = boolean_op_d(BooleanRequest {
closed_subjects: &[],
open_subjects: &open_d,
clips: &clip_d,
clip_type: ClipType::Intersection,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::DEFAULT,
})
.expect("valid floating open request");
assert_eq!(
output.open,
vec![vec![crate::PointD::new(0.0, 0.5), crate::PointD::new(1.0, 0.5)]]
);
}
#[test]
fn executes_union_with_empty_clip() {
let square =
vec![crate::Point64::new(0, 0), crate::Point64::new(1, 0), crate::Point64::new(1, 1)];
let request = BooleanRequest {
limits: crate::ComplexityLimits::DEFAULT,
open_subjects: &[],
closed_subjects: &[square],
clips: &[],
clip_type: ClipType::Union,
fill_rule: FillRule::NonZero,
};
assert_eq!(boolean_op(request).expect("valid request").closed.len(), 1);
}
#[test]
fn rejects_invalid_boolean_input_before_kernel() {
let request = BooleanRequest {
limits: crate::ComplexityLimits::DEFAULT,
open_subjects: &[],
closed_subjects: &[vec![crate::Point64::new(0, 0)]],
clips: &[],
clip_type: ClipType::Intersection,
fill_rule: FillRule::EvenOdd,
};
assert!(matches!(boolean_op(request), Err(Error::InvalidPath { .. })));
}
#[test]
fn validation_keeps_scanning_complexity_after_the_first_error() {
let integer_closed = [
vec![crate::Point64::new(0, 0)],
vec![crate::Point64::new(0, 0), crate::Point64::new(2, 0), crate::Point64::new(0, 2)],
];
let integer_open = [vec![crate::Point64::new(0, 0), crate::Point64::new(1, 1)]];
assert!(matches!(
boolean_op(BooleanRequest {
closed_subjects: &integer_closed,
open_subjects: &integer_open,
clips: &[],
clip_type: ClipType::Intersection,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::DEFAULT,
}),
Err(Error::InvalidPath { .. })
));
let double_closed = [
vec![crate::PointD::new(0.0, 0.0)],
vec![
crate::PointD::new(0.0, 0.0),
crate::PointD::new(2.0, 0.0),
crate::PointD::new(0.0, 2.0),
],
];
let double_open = [vec![crate::PointD::new(0.0, 0.0), crate::PointD::new(1.0, 1.0)]];
assert!(matches!(
boolean_op_d(BooleanRequest {
closed_subjects: &double_closed,
open_subjects: &double_open,
clips: &[],
clip_type: ClipType::Intersection,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::DEFAULT,
}),
Err(Error::InvalidPath { .. })
));
}
#[test]
fn open_requests_validate_and_preflight_before_geometry_work() {
let invalid_open = [vec![crate::Point64::new(0, 0)]];
let validation = BooleanRequest {
closed_subjects: &[],
open_subjects: &invalid_open,
clips: &[],
clip_type: ClipType::Intersection,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::DEFAULT,
};
assert!(matches!(
boolean_op(validation),
Err(Error::InvalidPath { kind: PathKind::Open, .. })
));
let oversized = [vec![crate::Point64::new(0, 0), crate::Point64::new(1, 1)]];
let limited = BooleanRequest {
closed_subjects: &[],
open_subjects: &oversized,
clips: &[],
clip_type: ClipType::Difference,
fill_rule: FillRule::EvenOdd,
limits: ComplexityLimits::new(0, 0, 0),
};
assert!(matches!(
boolean_op(limited),
Err(Error::LimitExceeded { resource: crate::ComplexityResource::Paths, .. })
));
}
#[test]
fn executes_and_validates_double_requests() {
let square = vec![
crate::PointD::new(0.0, 0.0),
crate::PointD::new(1.0, 0.0),
crate::PointD::new(1.0, 1.0),
];
let request = BooleanRequest {
limits: crate::ComplexityLimits::DEFAULT,
open_subjects: &[],
closed_subjects: &[square],
clips: &[],
clip_type: ClipType::Union,
fill_rule: FillRule::NonZero,
};
assert_eq!(crate::boolean_op_d(request).expect("valid request").closed.len(), 1);
let bad = BooleanRequest {
limits: crate::ComplexityLimits::DEFAULT,
open_subjects: &[],
closed_subjects: &[vec![
crate::PointD::new(0.0, 0.0),
crate::PointD::new(f64::NAN, 0.0),
]],
clips: &[],
clip_type: ClipType::Union,
fill_rule: FillRule::EvenOdd,
};
assert!(matches!(boolean_op_d(bad), Err(Error::InvalidPath { .. })));
}
#[test]
#[allow(clippy::cast_precision_loss)]
fn convenience_operations_use_even_odd_semantics() {
let subject = vec![
crate::Point64::new(0, 0),
crate::Point64::new(10, 0),
crate::Point64::new(10, 10),
crate::Point64::new(0, 10),
];
let clip = vec![
crate::Point64::new(5, 0),
crate::Point64::new(15, 0),
crate::Point64::new(15, 10),
crate::Point64::new(5, 10),
];
let subjects = [subject];
let clips = [clip];
assert_eq!(intersection(&subjects, &clips).expect("intersection").len(), 1);
assert_eq!(union(&subjects, &clips).expect("union").len(), 1);
assert_eq!(difference(&subjects, &clips).expect("difference").len(), 1);
assert_eq!(xor(&subjects, &clips).expect("xor").len(), 2);
let subjects_d = subjects
.iter()
.map(|path| {
path.iter()
.map(|point| crate::PointD::new(point.x as f64, point.y as f64))
.collect()
})
.collect::<Vec<PathD>>();
let clips_d = clips
.iter()
.map(|path| {
path.iter()
.map(|point| crate::PointD::new(point.x as f64, point.y as f64))
.collect()
})
.collect::<Vec<PathD>>();
assert_eq!(intersection_d(&subjects_d, &clips_d).expect("intersection_d").len(), 1);
assert_eq!(union_d(&subjects_d, &clips_d).expect("union_d").len(), 1);
assert_eq!(difference_d(&subjects_d, &clips_d).expect("difference_d").len(), 1);
assert_eq!(xor_d(&subjects_d, &clips_d).expect("xor_d").len(), 2);
}
#[test]
fn single_ring_helpers_match_collection_helpers() {
let integer_subject = vec![
crate::Point64::new(0, 0),
crate::Point64::new(10, 0),
crate::Point64::new(10, 10),
crate::Point64::new(0, 10),
];
let integer_clip = vec![
crate::Point64::new(5, 0),
crate::Point64::new(15, 0),
crate::Point64::new(15, 10),
crate::Point64::new(5, 10),
];
let integer_subjects = std::slice::from_ref(&integer_subject);
let integer_clips = std::slice::from_ref(&integer_clip);
assert_eq!(
intersection_path(&integer_subject, &integer_clip),
intersection(integer_subjects, integer_clips)
);
assert_eq!(
union_path(&integer_subject, &integer_clip),
union(integer_subjects, integer_clips)
);
assert_eq!(
difference_path(&integer_subject, &integer_clip),
difference(integer_subjects, integer_clips)
);
assert_eq!(xor_path(&integer_subject, &integer_clip), xor(integer_subjects, integer_clips));
let double_subject = vec![
crate::PointD::new(0.0, 0.0),
crate::PointD::new(10.0, 0.0),
crate::PointD::new(10.0, 10.0),
crate::PointD::new(0.0, 10.0),
];
let double_clip = vec![
crate::PointD::new(5.0, 0.0),
crate::PointD::new(15.0, 0.0),
crate::PointD::new(15.0, 10.0),
crate::PointD::new(5.0, 10.0),
];
let double_subjects = std::slice::from_ref(&double_subject);
let double_clips = std::slice::from_ref(&double_clip);
assert_eq!(
intersection_path_d(&double_subject, &double_clip),
intersection_d(double_subjects, double_clips)
);
assert_eq!(
union_path_d(&double_subject, &double_clip),
union_d(double_subjects, double_clips)
);
assert_eq!(
difference_path_d(&double_subject, &double_clip),
difference_d(double_subjects, double_clips)
);
assert_eq!(xor_path_d(&double_subject, &double_clip), xor_d(double_subjects, double_clips));
}
}