use core::cmp::Ordering;
use num_bigint::BigInt;
use crate::{
BooleanRequest, ClipType, Error, FillRule, PathKind, PathValidationError, boolean_op,
boolean_op_d,
};
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(C)]
pub struct Point64 {
pub x: i64,
pub y: i64,
}
impl Point64 {
#[must_use]
pub const fn new(x: i64, y: i64) -> Self {
Self { x, y }
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(C)]
pub struct PointD {
pub x: f64,
pub y: f64,
}
impl PointD {
#[must_use]
pub const fn new(x: f64, y: f64) -> Self {
Self { x, y }
}
}
pub type Path64 = Vec<Point64>;
pub type Paths64 = Vec<Path64>;
pub type PathD = Vec<PointD>;
pub type PathsD = Vec<PathD>;
#[allow(clippy::cast_precision_loss)]
pub(crate) fn paths64_to_local_d(paths: &[Path64]) -> Result<(Point64, PathsD), Error> {
let origin = paths64_local_origin(paths)?;
let mut local = Vec::with_capacity(paths.len());
for path in paths {
let mut local_path = Vec::with_capacity(path.len());
for point in path {
local_path.push(PointD::new(
(i128::from(point.x) - i128::from(origin.x)) as f64,
(i128::from(point.y) - i128::from(origin.y)) as f64,
));
}
local.push(local_path);
}
Ok((origin, local))
}
pub(crate) fn paths64_local_origin(paths: &[Path64]) -> Result<Point64, Error> {
const MAX_EXACT_INTEGER: i128 = 1 << 53;
let Some(first) = paths.iter().flatten().next().copied() else {
return Ok(Point64::new(0, 0));
};
let (mut min_x, mut min_y, mut max_x, mut max_y) = (first.x, first.y, first.x, first.y);
for point in paths.iter().flatten() {
min_x = min_x.min(point.x);
min_y = min_y.min(point.y);
max_x = max_x.max(point.x);
max_y = max_y.max(point.y);
}
if i128::from(max_x) - i128::from(min_x) > MAX_EXACT_INTEGER
|| i128::from(max_y) - i128::from(min_y) > MAX_EXACT_INTEGER
{
return Err(Error::ArithmeticOverflow);
}
Ok(Point64::new(min_x, min_y))
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
pub enum Orientation {
Clockwise,
Collinear,
CounterClockwise,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
pub enum PointLocation {
Outside,
Inside,
Boundary,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(C)]
pub struct Rect64 {
pub min_x: i64,
pub min_y: i64,
pub max_x: i64,
pub max_y: i64,
}
impl Rect64 {
#[must_use]
pub const fn new(first_x: i64, first_y: i64, second_x: i64, second_y: i64) -> Self {
let (min_x, max_x) =
if first_x <= second_x { (first_x, second_x) } else { (second_x, first_x) };
let (min_y, max_y) =
if first_y <= second_y { (first_y, second_y) } else { (second_y, first_y) };
Self { min_x, min_y, max_x, max_y }
}
fn path(self) -> Path64 {
vec![
Point64::new(self.min_x, self.min_y),
Point64::new(self.max_x, self.min_y),
Point64::new(self.max_x, self.max_y),
Point64::new(self.min_x, self.max_y),
]
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(C)]
pub struct RectD {
pub min_x: f64,
pub min_y: f64,
pub max_x: f64,
pub max_y: f64,
}
impl RectD {
#[must_use]
pub const fn new(first_x: f64, first_y: f64, second_x: f64, second_y: f64) -> Self {
let (min_x, max_x) =
if first_x <= second_x { (first_x, second_x) } else { (second_x, first_x) };
let (min_y, max_y) =
if first_y <= second_y { (first_y, second_y) } else { (second_y, first_y) };
Self { min_x, min_y, max_x, max_y }
}
fn path(self) -> PathD {
vec![
PointD::new(self.min_x, self.min_y),
PointD::new(self.max_x, self.min_y),
PointD::new(self.max_x, self.max_y),
PointD::new(self.min_x, self.max_y),
]
}
}
pub fn validate_path64(path: &[Point64], kind: PathKind) -> Result<(), Error> {
let minimum_vertices = match kind {
PathKind::Closed => 3,
PathKind::Open => 2,
};
if path.is_empty() || path.len() >= minimum_vertices {
Ok(())
} else {
Err(Error::InvalidPath { kind, minimum_vertices, actual_vertices: path.len() })
}
}
pub fn validate_paths64(paths: &[Path64], kind: PathKind) -> Result<(), Error> {
for path in paths {
validate_path64(path, kind)?;
}
Ok(())
}
pub fn validate_paths64_located(
paths: &[Path64],
kind: PathKind,
) -> Result<(), PathValidationError> {
for (path_index, path) in paths.iter().enumerate() {
validate_path64(path, kind).map_err(|error| PathValidationError::new(path_index, error))?;
}
Ok(())
}
pub fn validate_path_d(path: &[PointD], kind: PathKind) -> Result<(), Error> {
let minimum_vertices = match kind {
PathKind::Closed => 3,
PathKind::Open => 2,
};
if !path.is_empty() && path.len() < minimum_vertices {
return Err(Error::InvalidPath { kind, minimum_vertices, actual_vertices: path.len() });
}
for (point_index, point) in path.iter().enumerate() {
if !point.x.is_finite() || !point.y.is_finite() {
return Err(Error::NonFiniteCoordinate { point_index });
}
}
Ok(())
}
pub fn validate_paths_d(paths: &[PathD], kind: PathKind) -> Result<(), Error> {
for path in paths {
validate_path_d(path, kind)?;
}
Ok(())
}
pub fn validate_paths_d_located(
paths: &[PathD],
kind: PathKind,
) -> Result<(), PathValidationError> {
for (path_index, path) in paths.iter().enumerate() {
validate_path_d(path, kind).map_err(|error| PathValidationError::new(path_index, error))?;
}
Ok(())
}
#[must_use]
pub fn normalize_path64(path: &[Point64], kind: PathKind) -> Path64 {
let mut normalized = Vec::with_capacity(path.len());
for &point in path {
if normalized.last().copied() != Some(point) {
normalized.push(point);
}
}
if kind == PathKind::Closed && normalized.len() > 1 && normalized.first() == normalized.last() {
normalized.pop();
}
normalized
}
#[must_use]
pub fn normalize_path_d(path: &[PointD], kind: PathKind) -> PathD {
let mut normalized = Vec::with_capacity(path.len());
for &point in path {
if normalized.last().copied() != Some(point) {
normalized.push(point);
}
}
if kind == PathKind::Closed && normalized.len() > 1 && normalized.first() == normalized.last() {
normalized.pop();
}
normalized
}
pub fn signed_area2(path: &[Point64]) -> Result<i128, Error> {
if path.len() < 3 {
return Ok(0);
}
let mut area = 0_i128;
for (a, b) in path.iter().copied().zip(path.iter().copied().cycle().skip(1)).take(path.len()) {
let term = i128::from(a.x)
.checked_mul(i128::from(b.y))
.and_then(|left| {
i128::from(a.y)
.checked_mul(i128::from(b.x))
.and_then(|right| left.checked_sub(right))
})
.ok_or(Error::ArithmeticOverflow)?;
area = area.checked_add(term).ok_or(Error::ArithmeticOverflow)?;
}
Ok(area)
}
pub(crate) fn signed_area2_d(path: &[PointD]) -> f64 {
path.iter()
.zip(path.iter().cycle().skip(1))
.take(path.len())
.map(|(start, end)| start.x * end.y - start.y * end.x)
.sum()
}
#[must_use]
pub fn orientation(a: Point64, b: Point64, c: Point64) -> Orientation {
match cross_ordering(a, b, c) {
Ordering::Less => Orientation::Clockwise,
Ordering::Equal => Orientation::Collinear,
Ordering::Greater => Orientation::CounterClockwise,
}
}
pub fn point_in_polygon(point: Point64, path: &[Point64]) -> Result<PointLocation, Error> {
validate_path64(path, PathKind::Closed)?;
if path.is_empty() {
return Ok(PointLocation::Outside);
}
let mut inside = false;
for (a, b) in path.iter().copied().zip(path.iter().copied().cycle().skip(1)).take(path.len()) {
if point_on_segment(point, a, b) {
return Ok(PointLocation::Boundary);
}
if (a.y > point.y) != (b.y > point.y) {
let cross = cross_ordering(a, b, point);
let crosses_right =
if b.y > a.y { cross == Ordering::Greater } else { cross == Ordering::Less };
if crosses_right {
inside = !inside;
}
}
}
Ok(if inside { PointLocation::Inside } else { PointLocation::Outside })
}
#[must_use]
pub fn reverse_path64(path: &[Point64]) -> Path64 {
path.iter().copied().rev().collect()
}
#[must_use]
pub fn reverse_path_d(path: &[PointD]) -> PathD {
path.iter().copied().rev().collect()
}
pub fn translate_path64(path: &[Point64], dx: i64, dy: i64) -> Result<Path64, Error> {
path.iter()
.map(|point| {
Ok(Point64::new(
point.x.checked_add(dx).ok_or(Error::ArithmeticOverflow)?,
point.y.checked_add(dy).ok_or(Error::ArithmeticOverflow)?,
))
})
.collect()
}
pub fn translate_path_d(path: &[PointD], dx: f64, dy: f64) -> Result<PathD, Error> {
if !dx.is_finite() || !dy.is_finite() {
return Err(Error::NonFiniteCoordinate { point_index: 0 });
}
path.iter()
.enumerate()
.map(|(point_index, point)| {
let translated = PointD::new(point.x + dx, point.y + dy);
if point.x.is_finite()
&& point.y.is_finite()
&& translated.x.is_finite()
&& translated.y.is_finite()
{
Ok(translated)
} else {
Err(Error::NonFiniteCoordinate { point_index })
}
})
.collect()
}
pub fn trim_collinear64(path: &[Point64], kind: PathKind) -> Result<Path64, Error> {
validate_path64(path, kind)?;
let mut points = normalize_path64(path, kind);
loop {
if points.len() < 3 {
return Ok(points);
}
let mut changed = false;
let mut cleaned = Vec::with_capacity(points.len());
for index in 0..points.len() {
let removable = match kind {
PathKind::Closed => {
let previous = points[(index + points.len() - 1) % points.len()];
let current = points[index];
let next = points[(index + 1) % points.len()];
collinear_between64(previous, current, next)
}
PathKind::Open if index > 0 && index + 1 < points.len() => {
collinear_between64(points[index - 1], points[index], points[index + 1])
}
PathKind::Open => false,
};
if removable {
changed = true;
} else {
cleaned.push(points[index]);
}
}
points = cleaned;
if !changed {
return Ok(points);
}
}
}
pub fn trim_collinear_d(path: &[PointD], kind: PathKind) -> Result<PathD, Error> {
validate_path_d(path, kind)?;
let mut points = normalize_path_d(path, kind);
loop {
if points.len() < 3 {
return Ok(points);
}
let mut changed = false;
let mut cleaned = Vec::with_capacity(points.len());
for index in 0..points.len() {
let removable = match kind {
PathKind::Closed => {
let previous = points[(index + points.len() - 1) % points.len()];
let current = points[index];
let next = points[(index + 1) % points.len()];
collinear_between_d(previous, current, next)
}
PathKind::Open if index > 0 && index + 1 < points.len() => {
collinear_between_d(points[index - 1], points[index], points[index + 1])
}
PathKind::Open => false,
};
if removable {
changed = true;
} else {
cleaned.push(points[index]);
}
}
points = cleaned;
if !changed {
return Ok(points);
}
}
}
pub fn simplify_paths64(paths: &[Path64], fill_rule: FillRule) -> Result<Paths64, Error> {
boolean_op(BooleanRequest::new(paths, &[], ClipType::Union, fill_rule))
.map(|output| output.closed)
}
pub fn simplify_paths_d(paths: &[PathD], fill_rule: FillRule) -> Result<PathsD, Error> {
boolean_op_d(BooleanRequest::new(paths, &[], ClipType::Union, fill_rule))
.map(|output| output.closed)
}
pub fn clip_to_rect64(
paths: &[Path64],
rectangle: Rect64,
fill_rule: FillRule,
) -> Result<Paths64, Error> {
let clip = rectangle.path();
boolean_op(BooleanRequest::new(
paths,
std::slice::from_ref(&clip),
ClipType::Intersection,
fill_rule,
))
.map(|output| output.closed)
}
pub fn clip_to_rect_d(
paths: &[PathD],
rectangle: RectD,
fill_rule: FillRule,
) -> Result<PathsD, Error> {
if !rectangle.min_x.is_finite()
|| !rectangle.min_y.is_finite()
|| !rectangle.max_x.is_finite()
|| !rectangle.max_y.is_finite()
{
return Err(Error::NonFiniteCoordinate { point_index: 0 });
}
let clip = rectangle.path();
boolean_op_d(BooleanRequest::new(
paths,
std::slice::from_ref(&clip),
ClipType::Intersection,
fill_rule,
))
.map(|output| output.closed)
}
fn collinear_between64(previous: Point64, current: Point64, next: Point64) -> bool {
if cross_ordering(previous, current, next) != Ordering::Equal {
return false;
}
current.x >= previous.x.min(next.x)
&& current.x <= previous.x.max(next.x)
&& current.y >= previous.y.min(next.y)
&& current.y <= previous.y.max(next.y)
}
fn collinear_between_d(previous: PointD, current: PointD, next: PointD) -> bool {
let first_x = current.x - previous.x;
let first_y = current.y - previous.y;
let second_x = next.x - current.x;
let second_y = next.y - current.y;
let cross = first_x * second_y - first_y * second_x;
let dot = first_x * second_x + first_y * second_y;
cross == 0.0 && dot >= 0.0
}
fn checked_cross(a: Point64, b: Point64, c: Point64) -> Result<i128, Error> {
let first_x = i128::from(b.x) - i128::from(a.x);
let first_y = i128::from(b.y) - i128::from(a.y);
let second_x = i128::from(c.x) - i128::from(a.x);
let second_y = i128::from(c.y) - i128::from(a.y);
first_x
.checked_mul(second_y)
.and_then(|left| first_y.checked_mul(second_x).and_then(|right| left.checked_sub(right)))
.ok_or(Error::ArithmeticOverflow)
}
pub(crate) fn cross_ordering(a: Point64, b: Point64, c: Point64) -> Ordering {
if let Ok(cross) = checked_cross(a, b, c) {
return cross.cmp(&0);
}
let first_x = BigInt::from(i128::from(b.x) - i128::from(a.x));
let first_y = BigInt::from(i128::from(b.y) - i128::from(a.y));
let second_x = BigInt::from(i128::from(c.x) - i128::from(a.x));
let second_y = BigInt::from(i128::from(c.y) - i128::from(a.y));
(first_x * second_y - first_y * second_x).cmp(&BigInt::from(0))
}
fn point_on_segment(point: Point64, a: Point64, b: Point64) -> bool {
if cross_ordering(a, b, point) != Ordering::Equal {
return false;
}
let px = i128::from(point.x);
let py = i128::from(point.y);
let min_x = i128::from(a.x).min(i128::from(b.x));
let max_x = i128::from(a.x).max(i128::from(b.x));
let min_y = i128::from(a.y).min(i128::from(b.y));
let max_y = i128::from(a.y).max(i128::from(b.y));
px >= min_x && px <= max_x && py >= min_y && py <= max_y
}
#[cfg(test)]
mod tests {
use super::*;
const A: Point64 = Point64::new(0, 0);
const B: Point64 = Point64::new(10, 0);
const C: Point64 = Point64::new(10, 10);
#[test]
fn validates_empty_and_minimum_shapes() {
assert!(validate_path64(&[], PathKind::Closed).is_ok());
assert!(validate_path64(&[A], PathKind::Closed).is_err());
assert!(validate_path64(&[A, B], PathKind::Closed).is_err());
assert!(validate_path64(&[A, B], PathKind::Open).is_ok());
assert!(validate_path64(&[A], PathKind::Open).is_err());
assert!(validate_paths64(&[vec![A, B]], PathKind::Open).is_ok());
assert!(validate_paths64(&[vec![A]], PathKind::Closed).is_err());
assert!(validate_paths_d(&[], PathKind::Closed).is_ok());
assert!(
validate_paths_d(&[vec![PointD::new(0.0, 0.0), PointD::new(1.0, 0.0)]], PathKind::Open)
.is_ok()
);
assert!(validate_paths_d(&[vec![PointD::new(0.0, 0.0)]], PathKind::Closed).is_err());
}
#[test]
fn converts_integer_paths_in_one_exact_local_coordinate_frame() {
assert_eq!(paths64_to_local_d(&[]), Ok((Point64::new(0, 0), Vec::new())));
let origin = i64::MAX - 100;
let paths = [vec![
Point64::new(origin, origin),
Point64::new(origin + 10, origin),
Point64::new(origin + 10, origin + 20),
]];
let (actual_origin, local) = paths64_to_local_d(&paths).unwrap();
assert_eq!(actual_origin, Point64::new(origin, origin));
assert_eq!(local[0][2], PointD::new(10.0, 20.0));
let exact_limit = 1_i64 << 53;
let ring = vec![
Point64::new(-exact_limit, 0),
Point64::new(0, exact_limit),
Point64::new(exact_limit, 0),
];
for start in 0..ring.len() {
let mut rotated = ring.clone();
rotated.rotate_left(start);
assert_eq!(
paths64_to_local_d(&[rotated]),
Err(Error::ArithmeticOverflow),
"ring start {start}"
);
}
let within_exact_span = [vec![
Point64::new(-exact_limit / 2, 0),
Point64::new(0, exact_limit / 2),
Point64::new(exact_limit / 2, 0),
]];
assert!(paths64_to_local_d(&within_exact_span).is_ok());
let excessive_span =
[vec![Point64::new(i64::MIN, 0), Point64::new(i64::MAX, 0), Point64::new(0, 1)]];
assert_eq!(paths64_to_local_d(&excessive_span), Err(Error::ArithmeticOverflow));
let excessive_y_span =
[vec![Point64::new(0, i64::MIN), Point64::new(0, i64::MAX), Point64::new(1, 0)]];
assert_eq!(paths64_to_local_d(&excessive_y_span), Err(Error::ArithmeticOverflow));
}
#[test]
fn validates_double_finiteness() {
assert!(validate_path_d(&[], PathKind::Closed).is_ok());
assert!(validate_path_d(&[PointD::new(0.0, 0.0)], PathKind::Closed).is_err());
assert!(
validate_path_d(&[PointD::new(0.0, 0.0), PointD::new(1.0, 0.0)], PathKind::Open)
.is_ok()
);
let error = validate_path_d(
&[PointD::new(0.0, 0.0), PointD::new(f64::NAN, 0.0), PointD::new(1.0, 1.0)],
PathKind::Closed,
)
.expect_err("NaN must be rejected");
assert_eq!(error, Error::NonFiniteCoordinate { point_index: 1 });
assert!(
validate_path_d(
&[PointD::new(0.0, 0.0), PointD::new(1.0, 0.0), PointD::new(f64::INFINITY, 1.0),],
PathKind::Closed,
)
.is_err()
);
assert!(
validate_path_d(
&[PointD::new(0.0, 0.0), PointD::new(1.0, 0.0), PointD::new(0.0, f64::INFINITY)],
PathKind::Closed,
)
.is_err()
);
}
#[test]
fn located_validation_reports_path_and_point_indices() {
let integer_error =
validate_paths64_located(&[vec![A, B, C], vec![A]], PathKind::Closed).unwrap_err();
assert_eq!(integer_error.path_index(), 1);
assert_eq!(integer_error.point_index(), None);
assert!(integer_error.to_string().starts_with("path 1:"));
assert!(std::error::Error::source(&integer_error).is_some());
assert!(matches!(integer_error.error(), Error::InvalidPath { .. }));
assert!(matches!(integer_error.into_error(), Error::InvalidPath { .. }));
let floating_error = validate_paths_d_located(
&[
vec![PointD::new(0.0, 0.0), PointD::new(1.0, 0.0), PointD::new(0.0, 1.0)],
vec![PointD::new(0.0, 0.0), PointD::new(1.0, 0.0), PointD::new(f64::NAN, 1.0)],
],
PathKind::Closed,
)
.unwrap_err();
assert_eq!(floating_error.path_index(), 1);
assert_eq!(floating_error.point_index(), Some(2));
assert!(floating_error.to_string().starts_with("path 1, point 2:"));
assert!(validate_paths64_located(&[], PathKind::Closed).is_ok());
assert!(validate_paths_d_located(&[], PathKind::Closed).is_ok());
}
#[test]
fn normalizes_integer_and_double_paths() {
let input = [A, A, B, B, C, A, A];
assert_eq!(normalize_path64(&input, PathKind::Closed), vec![A, B, C]);
assert_eq!(normalize_path64(&[A, B, C], PathKind::Closed), vec![A, B, C]);
assert_eq!(normalize_path64(&input, PathKind::Open), vec![A, B, C, A]);
assert!(normalize_path64(&[], PathKind::Closed).is_empty());
let doubles = [PointD::new(0.0, 0.0), PointD::new(0.0, 0.0), PointD::new(1.0, 0.0)];
assert_eq!(normalize_path_d(&doubles, PathKind::Open).len(), 2);
let closed_doubles = [
PointD::new(0.0, 0.0),
PointD::new(1.0, 0.0),
PointD::new(0.0, 1.0),
PointD::new(0.0, 0.0),
];
assert_eq!(normalize_path_d(&closed_doubles, PathKind::Closed).len(), 3);
assert_eq!(
normalize_path_d(
&[PointD::new(0.0, 0.0), PointD::new(1.0, 0.0), PointD::new(0.0, 1.0)],
PathKind::Closed,
)
.len(),
3
);
assert_eq!(normalize_path_d(&[], PathKind::Closed), Vec::<PointD>::new());
}
#[test]
fn computes_area_and_orientation() {
let square = vec![A, B, C, Point64::new(0, 10)];
assert_eq!(signed_area2(&square), Ok(200));
let mut reverse = square.clone();
reverse.reverse();
assert_eq!(signed_area2(&reverse), Ok(-200));
let square_d = vec![
PointD::new(0.0, 0.0),
PointD::new(10.0, 0.0),
PointD::new(10.0, 10.0),
PointD::new(0.0, 10.0),
];
assert!((signed_area2_d(&square_d) - 200.0).abs() < f64::EPSILON);
assert_eq!(signed_area2(&[A, B]), Ok(0));
assert_eq!(orientation(A, B, C), Orientation::CounterClockwise);
assert_eq!(orientation(C, B, A), Orientation::Clockwise);
assert_eq!(orientation(A, B, Point64::new(20, 0)), Orientation::Collinear);
}
#[test]
fn reports_arithmetic_overflow() {
let extreme = vec![
Point64::new(i64::MAX, i64::MAX),
Point64::new(i64::MIN, i64::MAX),
Point64::new(i64::MIN, i64::MIN),
Point64::new(i64::MAX, i64::MIN),
];
assert_eq!(signed_area2(&extreme), Err(Error::ArithmeticOverflow));
assert_eq!(
signed_area2(&[
Point64::new(i64::MIN, i64::MIN),
Point64::new(i64::MIN, 1),
Point64::new(i64::MAX, i64::MIN),
]),
Err(Error::ArithmeticOverflow)
);
assert_eq!(
orientation(
Point64::new(i64::MIN, i64::MIN),
Point64::new(i64::MAX, i64::MAX),
Point64::new(i64::MIN, i64::MAX)
),
Orientation::CounterClockwise
);
assert_eq!(
checked_cross(
Point64::new(i64::MIN, i64::MIN),
Point64::new(i64::MIN, i64::MAX),
Point64::new(i64::MAX, i64::MIN),
),
Err(Error::ArithmeticOverflow)
);
assert_eq!(
checked_cross(
Point64::new(i64::MIN, -1),
Point64::new(-1, i64::MIN),
Point64::new(i64::MAX, i64::MAX),
),
Err(Error::ArithmeticOverflow)
);
}
#[test]
fn classifies_points_and_empty_paths() {
let square = vec![A, B, C, Point64::new(0, 10)];
assert_eq!(point_in_polygon(Point64::new(5, 5), &square), Ok(PointLocation::Inside));
assert_eq!(point_in_polygon(Point64::new(15, 5), &square), Ok(PointLocation::Outside));
assert_eq!(point_in_polygon(Point64::new(20, 0), &square), Ok(PointLocation::Outside));
assert_eq!(point_in_polygon(Point64::new(-1, 0), &square), Ok(PointLocation::Outside));
assert_eq!(point_in_polygon(Point64::new(10, 20), &square), Ok(PointLocation::Outside));
assert_eq!(point_in_polygon(Point64::new(10, -1), &square), Ok(PointLocation::Outside));
assert_eq!(point_in_polygon(Point64::new(10, 5), &square), Ok(PointLocation::Boundary));
assert_eq!(point_in_polygon(A, &[]), Ok(PointLocation::Outside));
assert!(point_in_polygon(A, &[A, B]).is_err());
let extreme = vec![
Point64::new(i64::MAX, i64::MAX),
Point64::new(i64::MIN, i64::MAX),
Point64::new(i64::MIN, i64::MIN),
Point64::new(i64::MAX, i64::MIN),
];
assert_eq!(point_in_polygon(Point64::new(0, 0), &extreme), Ok(PointLocation::Inside));
assert_eq!(
point_in_polygon(Point64::new(i64::MIN, 0), &extreme),
Ok(PointLocation::Boundary)
);
}
#[test]
fn transforms_and_trims_paths() {
assert!(!collinear_between64(Point64::new(0, 0), Point64::new(0, 2), Point64::new(0, 1),));
assert!(!collinear_between64(Point64::new(0, 0), Point64::new(0, -1), Point64::new(0, 1),));
let square = vec![A, B, C, Point64::new(0, 10)];
let with_collinear = vec![A, Point64::new(5, 0), B, C, Point64::new(0, 10), A];
assert_eq!(trim_collinear64(&with_collinear, PathKind::Closed), Ok(square.clone()));
assert_eq!(
trim_collinear64(&[A, Point64::new(5, 0), B, C], PathKind::Open,),
Ok(vec![A, B, C])
);
assert_eq!(reverse_path64(&square), vec![Point64::new(0, 10), C, B, A]);
assert_eq!(
translate_path64(&square, 5, -2),
Ok(vec![
Point64::new(5, -2),
Point64::new(15, -2),
Point64::new(15, 8),
Point64::new(5, 8),
])
);
assert_eq!(
translate_path64(&[Point64::new(i64::MAX, 0)], 1, 0),
Err(Error::ArithmeticOverflow)
);
let double_path = vec![
PointD::new(0.0, 0.0),
PointD::new(10.0, 0.0),
PointD::new(10.0, 10.0),
PointD::new(0.0, 10.0),
];
assert_eq!(
reverse_path_d(&double_path),
double_path.iter().copied().rev().collect::<Vec<_>>()
);
assert_eq!(
trim_collinear_d(
&[
PointD::new(0.0, 0.0),
PointD::new(5.0, 0.0),
PointD::new(10.0, 0.0),
PointD::new(10.0, 10.0),
],
PathKind::Open,
)
.unwrap()
.len(),
3
);
assert_eq!(
translate_path_d(&[PointD::new(1.0, 2.0)], 3.0, -1.0),
Ok(vec![PointD::new(4.0, 1.0)])
);
assert!(translate_path_d(&[PointD::new(1.0, 2.0)], f64::INFINITY, 0.0).is_err());
assert!(translate_path_d(&[PointD::new(1.0, 2.0)], 0.0, f64::INFINITY).is_err());
assert!(translate_path_d(&[PointD::new(f64::INFINITY, 2.0)], 0.0, 0.0).is_err());
assert!(translate_path_d(&[PointD::new(1.0, f64::INFINITY)], 0.0, 0.0).is_err());
assert!(translate_path_d(&[PointD::new(f64::MAX, 0.0)], f64::MAX, 0.0).is_err());
assert!(translate_path_d(&[PointD::new(0.0, f64::MAX)], 0.0, f64::MAX).is_err());
let collinear_closed64 = [A, Point64::new(5, 0), B];
assert_eq!(trim_collinear64(&collinear_closed64, PathKind::Closed), Ok(vec![A, B]));
let collinear_closed_d =
[PointD::new(0.0, 0.0), PointD::new(5.0, 0.0), PointD::new(10.0, 0.0)];
assert_eq!(
trim_collinear_d(&collinear_closed_d, PathKind::Closed),
Ok(vec![PointD::new(0.0, 0.0), PointD::new(10.0, 0.0)])
);
}
#[test]
fn simplifies_and_clips_to_rectangles() {
let bow_tie = vec![
Point64::new(0, 0),
Point64::new(20, 20),
Point64::new(0, 20),
Point64::new(20, 0),
];
let simplified = simplify_paths64(&[bow_tie], FillRule::EvenOdd).unwrap();
assert_eq!(simplified.len(), 2);
assert_eq!(
simplified.iter().map(|path| signed_area2(path).unwrap().abs()).sum::<i128>(),
400
);
let subject = vec![
Point64::new(0, 0),
Point64::new(20, 0),
Point64::new(20, 20),
Point64::new(0, 20),
];
let clipped =
clip_to_rect64(&[subject], Rect64::new(5, 5, 15, 15), FillRule::EvenOdd).unwrap();
assert_eq!(clipped.len(), 1);
assert_eq!(signed_area2(&clipped[0]), Ok(200));
assert_eq!(Rect64::new(15, 15, 5, 5), Rect64::new(5, 5, 15, 15));
let subject_d = vec![
PointD::new(0.0, 0.0),
PointD::new(20.0, 0.0),
PointD::new(20.0, 20.0),
PointD::new(0.0, 20.0),
];
let clipped_d =
clip_to_rect_d(&[subject_d], RectD::new(5.5, 5.5, 15.5, 15.5), FillRule::EvenOdd)
.unwrap();
assert_eq!(clipped_d.len(), 1);
assert!((signed_area2_d(&clipped_d[0]).abs() - 200.0).abs() < f64::EPSILON);
assert!(
clip_to_rect_d(&[], RectD::new(f64::NAN, 0.0, 1.0, 1.0), FillRule::EvenOdd,).is_err()
);
for rectangle in [
RectD::new(0.0, f64::NAN, 1.0, 1.0),
RectD::new(0.0, 0.0, f64::NAN, 1.0),
RectD::new(0.0, 0.0, 1.0, f64::NAN),
] {
assert!(clip_to_rect_d(&[], rectangle, FillRule::EvenOdd).is_err());
}
}
}