1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
//! Module for turning a polygon into a number of non-overlapping triangles.
use super::Polygon;
use crate::math::{self, LineSegment, Surface, Triangle};
use nalgebra::{RealField, Scalar};
/// Type that saves the flags that match a corner in a space efficient manner.
type Flags = u8;
/// Tells the algorithm that this corner of the polygon is an ear. An ear means the adjacent corners
/// form a triangle with this corner of which the area is entirely contained by the polygon itself.
const FLAG_EAR: Flags = 0b0000_0001;
/// Tells the algorithm that this corner is convex, meaning its internal angle is less than Pi.
/// Useful, because this is a necessary condition for earness. False if the vertex is reflex.
// TODO: The convex flag is a remnant from the previous algorithm, but currently it's not being
// used. Consider removing it entirely.
const FLAG_CONVEX: Flags = 0b0000_0010;
fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags
where
T: RealField,
{
// First, check if it is convex. If it is not, it can also not be an ear.
let prev = (corner + polygon.corners.len() - 1) % polygon.corners.len();
let next = (corner + 1) % polygon.corners.len();
/* Since the angle is also in counterclockwise direction, like the polygon itself, the corner
* is convex if and only if the angle is **not**.
*/
if math::triplet_angle(
polygon.corners[prev],
polygon.corners[corner],
polygon.corners[next],
) < T::pi()
{
// The corner is reflex.
return 0b0;
}
// The corner is convex, check if it is also an ear.
if polygon.contains_line_segment(&LineSegment::new(
polygon.corners[prev],
polygon.corners[next],
)) {
// Corner is an ear.
FLAG_EAR | FLAG_CONVEX
} else {
// Corner is not an ear.
FLAG_CONVEX
}
}
/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)
/// to find an explanation of what exactly is happening.
/// Currently only handles simple polygons, but once the polygon struct supports holes must be
/// extended to also support those.
pub fn triangulate<T: Scalar + Copy>(mut polygon: Polygon<T>) -> Vec<Triangle<T>>
where
T: RealField,
{
assert!(polygon.corners.len() >= 3);
/* Information about the corner of the polygon. See the flags constant for information about
* what the bits mean.
*/
let mut flags = Vec::with_capacity(polygon.corners.len());
for c in 0..polygon.corners.len() {
flags.push(flag_corner(&polygon, c));
}
let mut triangles = Vec::with_capacity(polygon.corners.len() - 2);
// Clip ears until there's only the last triangle left.
/* NOTE: This could be changed to > 2 and the last triangle would be pushed inside the loop,
* because it is also detected as an ear, however this is more logical to the original idea
* imo.
*/
while polygon.corners.len() > 3 {
// Find the ear with the highest index.
let ear = flags
.iter()
.rposition(|&x| (x & FLAG_EAR) != 0)
.expect("Polygon has more than three vertices, but no ear.");
// Add the ear's triangle to the list.
{
let prev = (ear + polygon.corners.len() - 1) % polygon.corners.len();
let next = (ear + 1) % polygon.corners.len();
triangles.push(Triangle::new(
polygon.corners[prev],
polygon.corners[ear],
polygon.corners[next],
));
// Remove the ear from the polygon and the flag list.
polygon.corners.remove(ear);
flags.remove(ear);
}
// Reassess the status of the two adjacent points. Notice that since the ear was removed,
// their array positions have changed.
let prev = if ear == 0 || ear == polygon.corners.len() {
polygon.corners.len() - 1
} else {
ear - 1
};
let next = if ear == polygon.corners.len() { 0 } else { ear };
flags[prev] = flag_corner(&polygon, prev);
flags[next] = flag_corner(&polygon, next);
}
// Push the remaining triangle into the list.
triangles.push(Triangle::new(
polygon.corners[0],
polygon.corners[1],
polygon.corners[2],
));
triangles
}
#[cfg(test)]
mod test {
use super::*;
use crate::math::Vec2;
#[test]
fn triangulate() {
let polygon = Polygon::new(vec![
Vec2::new(0., 0.),
Vec2::new(0., 4.5),
Vec2::new(6.5, 4.5),
Vec2::new(5.5, 0.),
Vec2::new(5.5, 3.),
Vec2::new(1.5, 3.),
Vec2::new(1.5, 1.),
Vec2::new(2., 0.5),
Vec2::new(4., 2.),
Vec2::new(4., 0.),
])
.unwrap();
let triangles = super::triangulate(polygon);
assert_eq!(triangles.len(), 8);
assert_eq!(
triangles[0],
(Triangle::new(Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.)))
);
}
}
|
