poly2tri_rs/
shape.rs

1use crate::{triangles::TriangleId, PointId};
2
3#[derive(Clone, Copy, Debug)]
4pub struct Edge {
5    /// p is the lower end
6    pub p: PointId,
7    /// q is the higher end
8    pub q: PointId,
9}
10
11impl Edge {
12    pub fn new((p1_id, p1): (PointId, &Point), (p2_id, p2): (PointId, &Point)) -> Self {
13        let mut p: PointId = p1_id;
14        let mut q: PointId = p2_id;
15
16        if p1.y > p2.y {
17            q = p1_id;
18            p = p2_id;
19        } else if p1.y == p2.y {
20            if p1.x > p2.x {
21                q = p1_id;
22                p = p2_id;
23            } else if p1.x == p2.x {
24                assert!(false, "repeat points");
25            }
26        }
27
28        Self { p, q }
29    }
30}
31
32#[derive(Debug, Clone, Copy)]
33pub struct Point {
34    pub x: f64,
35    pub y: f64,
36}
37
38impl Default for Point {
39    fn default() -> Self {
40        Self { x: 0., y: 0. }
41    }
42}
43
44impl Point {
45    pub fn new(x: f64, y: f64) -> Self {
46        Self { x, y }
47    }
48
49    /// whether two points are same.
50    /// Note: the lib don't support duplicate point, so eq means they are same point
51    ///    not two point with equal values
52    pub fn eq(&self, other: &Self) -> bool {
53        self.x == other.x && self.y == other.y
54    }
55}
56
57#[derive(Default, Clone, Copy)]
58pub struct EdgeAttr(u8);
59
60impl std::fmt::Debug for EdgeAttr {
61    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
62        f.debug_struct("EdgeAttr")
63            .field("constrained", &self.is_constrained())
64            .field("delaunay", &self.is_delaunay())
65            .finish()
66    }
67}
68
69impl EdgeAttr {
70    const CONSTRAINED: u8 = 1;
71    const CONSTRAINED_UNSET: u8 = Self::ALL ^ Self::CONSTRAINED;
72    const DELAUNAY: u8 = 1 << 1;
73    const DELAUNAY_UNSET: u8 = Self::ALL ^ Self::DELAUNAY;
74
75    const ALL: u8 = 0xFF;
76
77    fn set_constrained(&mut self, val: bool) {
78        if !val {
79            self.0 &= Self::CONSTRAINED_UNSET;
80        } else {
81            self.0 |= Self::CONSTRAINED;
82        }
83    }
84
85    fn is_constrained(&self) -> bool {
86        self.0 & Self::CONSTRAINED != 0
87    }
88
89    fn set_delaunay(&mut self, val: bool) {
90        if !val {
91            self.0 &= Self::DELAUNAY_UNSET;
92        } else {
93            self.0 |= Self::DELAUNAY;
94        }
95    }
96
97    fn is_delaunay(&self) -> bool {
98        self.0 & Self::DELAUNAY != 0
99    }
100}
101
102/// The triangle struct used internally.
103#[derive(Debug, Clone, Copy)]
104pub struct InnerTriangle {
105    /// triangle points
106    pub points: [PointId; 3],
107
108    /// neighbors
109    pub neighbors: [TriangleId; 3],
110
111    pub edge_attrs: [EdgeAttr; 3],
112
113    /// Has this triangle been marked as an interior triangle?
114    pub interior: bool,
115}
116
117impl InnerTriangle {
118    pub fn new(a: PointId, b: PointId, c: PointId) -> Self {
119        Self {
120            points: [a, b, c],
121            edge_attrs: [Default::default(), Default::default(), Default::default()],
122            neighbors: [TriangleId::INVALID; 3],
123            interior: false,
124        }
125    }
126
127    /// The point clockwise to given point
128    pub fn point_cw(&self, point: PointId) -> PointId {
129        if point == self.points[0] {
130            self.points[2]
131        } else if point == self.points[1] {
132            self.points[0]
133        } else if point == self.points[2] {
134            self.points[1]
135        } else {
136            panic!("point not belongs to triangle");
137        }
138    }
139
140    /// The point counter-clockwise to given point
141    pub fn point_ccw(&self, point: PointId) -> PointId {
142        if point == self.points[0] {
143            self.points[1]
144        } else if point == self.points[1] {
145            self.points[2]
146        } else if point == self.points[2] {
147            self.points[0]
148        } else {
149            panic!("point not belongs to triangle");
150        }
151    }
152
153    /// The opposite point for point in neighbor `from_triangle`
154    pub fn opposite_point(&self, from_triangle: &InnerTriangle, point: PointId) -> PointId {
155        let cw = from_triangle.point_cw(point);
156        self.point_cw(cw)
157    }
158
159    /// get point index
160    #[inline(always)]
161    pub fn point_index(&self, point: PointId) -> Option<usize> {
162        if self.points[0] == point {
163            Some(0)
164        } else if self.points[1] == point {
165            Some(1)
166        } else if self.points[2] == point {
167            Some(2)
168        } else {
169            None
170        }
171    }
172
173    /// set constrained flag for edge identified by `p` and `q`
174    pub fn set_constrained_for_edge(&mut self, p: PointId, q: PointId) {
175        if let Some(index) = self.edge_index(p, q) {
176            self.edge_attrs[index].set_constrained(true);
177        }
178    }
179
180    #[inline(always)]
181    pub fn set_constrained(&mut self, edge_index: usize, val: bool) {
182        self.edge_attrs[edge_index].set_constrained(val);
183    }
184
185    pub fn is_constrained(&self, edge_index: usize) -> bool {
186        self.edge_attrs[edge_index].is_constrained()
187    }
188
189    #[inline(always)]
190    pub fn set_delaunay(&mut self, edge_index: usize, val: bool) {
191        self.edge_attrs[edge_index].set_delaunay(val);
192    }
193
194    pub fn is_delaunay(&self, edge_index: usize) -> bool {
195        self.edge_attrs[edge_index].is_delaunay()
196    }
197
198    pub fn edge_attr_ccw(&self, p: PointId) -> EdgeAttr {
199        if p == self.points[0] {
200            self.edge_attrs[2]
201        } else if p == self.points[1] {
202            self.edge_attrs[0]
203        } else if p == self.points[2] {
204            self.edge_attrs[1]
205        } else {
206            panic!("point not belongs to triangle");
207        }
208    }
209
210    pub fn set_edge_attr_ccw(&mut self, p: PointId, edge_attr: EdgeAttr) {
211        if p == self.points[0] {
212            self.edge_attrs[2] = edge_attr;
213        } else if p == self.points[1] {
214            self.edge_attrs[0] = edge_attr;
215        } else if p == self.points[2] {
216            self.edge_attrs[1] = edge_attr;
217        } else {
218            panic!("point not belongs to triangle");
219        }
220    }
221
222    pub fn set_edge_attr_cw(&mut self, p: PointId, val: EdgeAttr) {
223        if p == self.points[0] {
224            self.edge_attrs[1] = val;
225        } else if p == self.points[1] {
226            self.edge_attrs[2] = val;
227        } else if p == self.points[2] {
228            self.edge_attrs[0] = val;
229        } else {
230            panic!("point not belongs to triangle");
231        }
232    }
233
234    pub fn edge_attr_cw(&self, p: PointId) -> EdgeAttr {
235        if p == self.points[0] {
236            self.edge_attrs[1]
237        } else if p == self.points[1] {
238            self.edge_attrs[2]
239        } else if p == self.points[2] {
240            self.edge_attrs[0]
241        } else {
242            panic!("point not belongs to triangle");
243        }
244    }
245
246    /// constrained edge flag for edge `cw` to given point
247    pub fn constrained_edge_cw(&self, p: PointId) -> bool {
248        match self.point_index(p) {
249            Some(0) => self.edge_attrs[1].is_constrained(),
250            Some(1) => self.edge_attrs[2].is_constrained(),
251            Some(2) => self.edge_attrs[0].is_constrained(),
252            _ => panic!("point not belongs to triangle"),
253        }
254    }
255
256    pub fn neighbor_index(&self, tid: TriangleId) -> usize {
257        if self.neighbors[0] == tid {
258            0
259        } else if self.neighbors[1] == tid {
260            1
261        } else if self.neighbors[2] == tid {
262            2
263        } else {
264            panic!("not valid neighbor")
265        }
266    }
267
268    /// neighbor counter clockwise to given point
269    pub fn neighbor_ccw(&self, p: PointId) -> TriangleId {
270        if p == self.points[0] {
271            self.neighbors[2]
272        } else if p == self.points[1] {
273            self.neighbors[0]
274        } else if p == self.points[2] {
275            self.neighbors[1]
276        } else {
277            panic!("point not belongs to triangle");
278        }
279    }
280
281    /// neighbor clockwise to given point
282    pub fn neighbor_cw(&self, p: PointId) -> TriangleId {
283        if p == self.points[0] {
284            self.neighbors[1]
285        } else if p == self.points[1] {
286            self.neighbors[2]
287        } else if p == self.points[2] {
288            self.neighbors[0]
289        } else {
290            panic!("point not belongs to triangle");
291        }
292    }
293
294    /// neighbor counter clockwise to given point
295    pub fn neighbor_across(&self, p: PointId) -> TriangleId {
296        let Some(point_index) = self.point_index(p) else {
297            panic!("break here");
298        };
299        self.neighbors[point_index]
300    }
301
302    /// Rotate triangle clockwise around `o_point`
303    pub fn rotate_cw(&mut self, o_point: PointId, n_point: PointId) {
304        if o_point == self.points[0] {
305            self.points[1] = self.points[0];
306            self.points[0] = self.points[2];
307            self.points[2] = n_point;
308        } else if o_point == self.points[1] {
309            self.points[2] = self.points[1];
310            self.points[1] = self.points[0];
311            self.points[0] = n_point;
312        } else if o_point == self.points[2] {
313            self.points[0] = self.points[2];
314            self.points[2] = self.points[1];
315            self.points[1] = n_point;
316        } else {
317            panic!("point not belongs to triangle")
318        }
319    }
320
321    pub fn clear_neighbors(&mut self) {
322        self.neighbors = [TriangleId::INVALID; 3];
323    }
324
325    pub fn edge_index(&self, p: PointId, q: PointId) -> Option<usize> {
326        Some(if self.points[0] == p {
327            if self.points[1] == q {
328                2
329            } else if self.points[2] == q {
330                1
331            } else {
332                return None;
333            }
334        } else if self.points[1] == p {
335            if self.points[0] == q {
336                2
337            } else if self.points[2] == q {
338                0
339            } else {
340                return None;
341            }
342        } else if self.points[2] == p {
343            if self.points[0] == q {
344                1
345            } else if self.points[1] == q {
346                0
347            } else {
348                return None;
349            }
350        } else {
351            return None;
352        })
353    }
354
355    pub fn common_edge_index(&self, other: &Self) -> Option<(usize, usize)> {
356        Some(if self.points[1] == other.points[0] {
357            if self.points[2] == other.points[2] {
358                (0, 1)
359            } else if self.points[0] == other.points[1] {
360                (2, 2)
361            } else {
362                return None;
363            }
364        } else if self.points[1] == other.points[1] {
365            if self.points[2] == other.points[0] {
366                (0, 2)
367            } else if self.points[0] == other.points[2] {
368                (2, 0)
369            } else {
370                return None;
371            }
372        } else if self.points[1] == other.points[2] {
373            if self.points[2] == other.points[1] {
374                (0, 0)
375            } else if self.points[0] == other.points[0] {
376                (2, 1)
377            } else {
378                return None;
379            }
380        } else if self.points[0] == other.points[0] {
381            if self.points[2] == other.points[1] {
382                (1, 2)
383            } else if self.points[1] == other.points[2] {
384                (2, 1)
385            } else {
386                return None;
387            }
388        } else if self.points[0] == other.points[2] {
389            if self.points[2] == other.points[0] {
390                (1, 1)
391            } else if self.points[1] == other.points[1] {
392                (2, 0)
393            } else {
394                return None;
395            }
396        } else if self.points[0] == other.points[1] {
397            if self.points[1] == other.points[0] {
398                (2, 2)
399            } else if self.points[2] == other.points[2] {
400                (1, 0)
401            } else {
402                return None;
403            }
404        } else if self.points[2] == other.points[0] {
405            if self.points[0] == other.points[2] {
406                (1, 1)
407            } else if self.points[1] == other.points[1] {
408                (0, 2)
409            } else {
410                return None;
411            }
412        } else if self.points[2] == other.points[1] {
413            if self.points[0] == other.points[0] {
414                (1, 2)
415            } else if self.points[1] == other.points[2] {
416                (0, 0)
417            } else {
418                return None;
419            }
420        } else if self.points[2] == other.points[2] {
421            if self.points[1] == other.points[0] {
422                (0, 1)
423            } else if self.points[0] == other.points[1] {
424                (1, 0)
425            } else {
426                return None;
427            }
428        } else {
429            return None;
430        })
431    }
432}
433
434#[cfg(test)]
435mod tests {
436    use super::*;
437    use crate::PointId;
438
439    #[test]
440    fn test_legalize() {
441        //
442        //      1                1
443        //     /  \              | \
444        //   2  -  3   =>   2    |  3
445        //                       | /
446        //       4               4
447        //
448        let mut t = InnerTriangle::new(PointId(1), PointId(2), PointId(3));
449        t.rotate_cw(PointId(1), PointId(4));
450        assert_eq!(t.points, [PointId(3), PointId(1), PointId(4)]);
451
452        //
453        //       1               1
454        //  4   / \          4 \
455        //     /   \          \    \
456        //    2  -  3   =>      2  - -  3
457        //
458        let mut t = InnerTriangle::new(PointId(1), PointId(2), PointId(3));
459        t.rotate_cw(PointId(3), PointId(4));
460        assert_eq!(t.points, [PointId(3), PointId(4), PointId(2)]);
461
462        let mut t = InnerTriangle::new(PointId(1), PointId(2), PointId(3));
463        t.rotate_cw(PointId(2), PointId(4));
464        assert_eq!(t.points, [PointId(4), PointId(1), PointId(2)]);
465    }
466
467    #[test]
468    fn test_edge_attr() {
469        let mut attr = EdgeAttr::default();
470        assert!(!attr.is_constrained());
471        attr.set_constrained(false);
472        assert!(!attr.is_constrained());
473        attr.set_constrained(true);
474        assert!(attr.is_constrained());
475        attr.set_constrained(false);
476        assert!(!attr.is_constrained());
477
478        assert!(!attr.is_delaunay());
479        attr.set_delaunay(false);
480        assert!(!attr.is_delaunay());
481        attr.set_delaunay(true);
482        assert!(attr.is_delaunay());
483        attr.set_delaunay(false);
484        assert!(!attr.is_delaunay());
485    }
486
487    #[test]
488    fn test_common_edge() {
489        for ((p1_0, p1_1, p1_2), (p2_0, p2_1, p2_2), common_edge) in [
490            // 0 <=> 0
491            ((0, 1, 2), (0, 4, 1), Some((2, 1))),
492            ((0, 1, 2), (0, 2, 4), Some((1, 2))),
493            // 0 <=> 1
494            ((0, 1, 2), (1, 0, 4), Some((2, 2))),
495            ((0, 1, 2), (4, 0, 2), Some((1, 0))),
496            // 0 <=> 2
497            ((0, 1, 2), (4, 1, 0), Some((2, 0))),
498            ((0, 1, 2), (2, 4, 0), Some((1, 1))),
499            // 1 <=> 0
500            ((0, 1, 2), (1, 0, 4), Some((2, 2))),
501            ((0, 1, 2), (1, 4, 2), Some((0, 1))),
502            // 1 <=> 1
503            ((0, 1, 2), (4, 2, 1), Some((0, 0))),
504            ((0, 1, 2), (2, 1, 4), Some((0, 2))),
505            // 1 <=> 2
506            ((0, 1, 2), (0, 4, 1), Some((2, 1))),
507            ((0, 1, 2), (4, 2, 1), Some((0, 0))),
508            // 2 <=> 0
509            ((0, 1, 2), (2, 1, 4), Some((0, 2))),
510            ((0, 1, 2), (2, 4, 0), Some((1, 1))),
511            // 2 <=> 1
512            ((0, 1, 2), (0, 2, 4), Some((1, 2))),
513            ((0, 1, 2), (4, 2, 1), Some((0, 0))),
514            // 2 <=> 0
515            ((0, 1, 2), (2, 4, 0), Some((1, 1))),
516            ((0, 1, 2), (2, 1, 4), Some((0, 2))),
517        ] {
518            let t = InnerTriangle::new(PointId(p1_0), PointId(p1_1), PointId(p1_2));
519            let ot = InnerTriangle::new(PointId(p2_0), PointId(p2_1), PointId(p2_2));
520            assert_eq!(
521                t.common_edge_index(&ot),
522                common_edge,
523                "({p1_0}, {p1_1}, {p1_2}) ({p2_0} {p2_1} {p2_2}) {common_edge:?}",
524            );
525        }
526    }
527}
poly2tri_rs/shape.rs

poly2tri_rs/
shape.rs
