dearcut/
math.rs

1// SPDX-FileCopyrightText: 2026 dearcut contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use std::ops::{Add, Mul, Sub};
6
7use num_traits::Zero;
8use rstar::RTreeNum;
9
10#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq, PartialOrd, Ord)]
11pub struct Vector2<K> {
12    x: K,
13    y: K,
14}
15
16impl<K> Vector2<K> {
17    pub fn new(x: K, y: K) -> Self {
18        Self { x, y }
19    }
20
21    pub fn x(&self) -> &K {
22        &self.x
23    }
24
25    pub fn y(&self) -> &K {
26        &self.y
27    }
28}
29
30impl<K: RTreeNum> From<Vector2<K>> for [K; 2] {
31    fn from(from: Vector2<K>) -> Self {
32        [from.x, from.y]
33    }
34}
35
36impl<K: Add<Output = K>> Add for Vector2<K> {
37    type Output = Self;
38
39    fn add(self, other: Self) -> Self::Output {
40        Self {
41            x: self.x + other.x,
42            y: self.y + other.y,
43        }
44    }
45}
46
47impl<K: Sub<Output = K>> Sub for Vector2<K> {
48    type Output = Self;
49
50    fn sub(self, other: Self) -> Self::Output {
51        Self {
52            x: self.x - other.x,
53            y: self.y - other.y,
54        }
55    }
56}
57
58pub(crate) fn point_in_triangle<
59    K: Clone + Sub<Output = K> + Mul<Output = K> + PartialOrd + Zero,
60>(
61    triangle: &[Vector2<K>],
62    position: Vector2<K>,
63) -> bool {
64    let tpdp1 =
65        ternary_perp_dot_product(position.clone(), triangle[0].clone(), triangle[1].clone());
66    let tpdp2 =
67        ternary_perp_dot_product(position.clone(), triangle[1].clone(), triangle[2].clone());
68    let tpdp3 = ternary_perp_dot_product(position, triangle[2].clone(), triangle[0].clone());
69
70    !(((tpdp1 < K::zero()) || (tpdp2 < K::zero()) || (tpdp3 < K::zero()))
71        && ((tpdp1 > K::zero()) || (tpdp2 > K::zero()) || (tpdp3 > K::zero())))
72}
73
74pub fn line_segments_intersect_proper<
75    K: Clone + Sub<Output = K> + Mul<Output = K> + PartialOrd + Zero,
76>(
77    from1: Vector2<K>,
78    to1: Vector2<K>,
79    from2: Vector2<K>,
80    to2: Vector2<K>,
81) -> bool {
82    let tpdp1 = ternary_perp_dot_product(from1.clone(), to1.clone(), from2.clone());
83    let tpdp2 = ternary_perp_dot_product(from1.clone(), to1.clone(), to2.clone());
84    let tpdp3 = ternary_perp_dot_product(from2.clone(), to2.clone(), from1.clone());
85    let tpdp4 = ternary_perp_dot_product(from2.clone(), to2.clone(), to1.clone());
86
87    // There is a proper intersection if and only if both tpdp1 has opposite
88    // sign than tpdp2 and tpdp3 has opposite sign than tpdp3.
89    have_opposite_signs(tpdp1, tpdp2) && have_opposite_signs(tpdp3, tpdp4)
90}
91
92fn have_opposite_signs<K: PartialOrd + Zero>(a: K, b: K) -> bool {
93    (a > K::zero() && b < K::zero()) || (a < K::zero() && b > K::zero())
94}
95
96pub fn is_convex_vertex<K: Clone + Mul<Output = K> + PartialOrd + Sub<Output = K> + Zero>(
97    v1: Vector2<K>,
98    v2: Vector2<K>,
99    v3: Vector2<K>,
100) -> bool {
101    ternary_perp_dot_product(v2, v3, v1) >= K::zero()
102}
103
104pub(crate) fn ternary_perp_dot_product<K: Clone + Sub<Output = K> + Mul<Output = K>>(
105    v1: Vector2<K>,
106    v2: Vector2<K>,
107    v3: Vector2<K>,
108) -> K {
109    perp_dot_product(v1 - v3.clone(), v2 - v3)
110}
111
112pub(crate) fn perp_dot_product<K: Sub<Output = K> + Mul<Output = K>>(
113    v1: Vector2<K>,
114    v2: Vector2<K>,
115) -> K {
116    v1.x * v2.y - v2.x * v1.y
117}
dearcut/math.rs

dearcut/
math.rs
