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
use crate::triangulate;
use geomutil_util::{Edge2D, Point2D, Shape2D, Triangle2D};
use std::collections::{HashMap, VecDeque};
struct AlphaShape2D {
triangles: Vec<Triangle2D>,
connections: HashMap<usize, [Option<usize>; 3]>,
}
impl AlphaShape2D {
fn new(triangles: Vec<Triangle2D>) -> Self {
Self {
triangles,
connections: HashMap::new(),
}
}
fn prune(&mut self, alpha: f32) {
self.triangles = self
.triangles
.iter()
.filter(|t| t.circumcircle_radius_squared().unwrap() <= (1.0 / alpha) * (1.0 / alpha))
.copied()
.collect::<Vec<_>>();
}
fn build_connections_graph(&mut self) {
let mut adjacent_edges: HashMap<Edge2D, [Option<usize>; 2]> = HashMap::new();
for (i, t) in self.triangles.iter().enumerate() {
for e in t.edges() {
let e = e.canonical();
adjacent_edges
.entry(e)
.and_modify(|adjacent: &mut _| adjacent[1] = Some(i))
.or_insert([Some(i), None]);
}
}
for (_, neighbours) in adjacent_edges {
for (i, j) in [
(neighbours[0], neighbours[1]),
(neighbours[1], neighbours[0]),
] {
if let (Some(i), Some(j)) = (i, j) {
self.connections
.entry(i)
.and_modify(|adjacent: &mut _| {
if let Some(neigh) = adjacent.iter_mut().find(|a| a.is_none()) {
neigh.replace(j);
}
})
.or_insert([Some(j), None, None]);
}
}
}
}
fn shapes(&self) -> Vec<Shape2D> {
let mut queue = VecDeque::new();
let mut visited = vec![false; self.triangles.len()];
let mut shapes = Vec::new();
for i in 0..self.triangles.len() {
if visited[i] {
continue;
}
queue.push_back(i);
let mut shape = Vec::new();
while let Some(i) = queue.pop_front() {
visited[i] = true;
shape.push(self.triangles[i]);
for neigh_i in self.connections[&i].into_iter().flatten() {
if !visited[neigh_i] {
queue.push_back(neigh_i);
}
}
}
shapes.push(Shape2D::new(shape));
}
shapes
}
}
pub fn alpha_shape_2d(points: &[Point2D], alpha: f32) -> Option<Vec<Shape2D>> {
let triangulation = triangulate(points)?;
let mut alpha_shape = AlphaShape2D::new(triangulation.triangles);
alpha_shape.prune(alpha);
alpha_shape.build_connections_graph();
let shapes = alpha_shape.shapes();
Some(shapes)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_two_disconnected_rectangles() {
// Define points for two rectangles
let points = vec![
Point2D::new(0.0, 0.0), // p0
Point2D::new(1.0, 0.0), // p1
Point2D::new(1.0, 1.0), // p2
Point2D::new(0.0, 1.0), // p3
Point2D::new(3.0, 0.0), // p4
Point2D::new(4.0, 0.0), // p5
Point2D::new(4.0, 1.0), // p6
Point2D::new(3.0, 1.0), // p7
];
// Choose an alpha value.
// - Internal triangles (e.g., (0,0)-(1,0)-(1,1)) have R^2 = 0.5.
// - Bridging triangles (e.g., (1,0)-(3,0)-(1,1)) have R^2 = 1.25.
//
// We want to prune triangles where R^2 > (1/alpha)^2.
// To prune bridging triangles (R^2 = 1.25) but keep internal ones (R^2 = 0.5),
// we need (1/alpha)^2 to be between 0.5 and 1.25.
// Let's pick (1/alpha)^2 = 1.0, which means 1/alpha = 1.0, so alpha = 1.0.
//
// With alpha = 1.0:
// - Internal triangles (R^2 = 0.5): 0.5 <= 1.0, so KEPT.
// - Bridging triangles (R^2 = 1.25): 1.25 > 1.0, so PRUNED.
let alpha = 1.0;
let result = alpha_shape_2d(&points, alpha);
// Assert that the result is Some and contains exactly two shapes
assert!(
result.is_some(),
"alpha_shape_2d should return Some for valid input."
);
let shapes = result.unwrap();
assert_eq!(shapes.len(), 2, "Expected 2 disconnected shapes.");
// Optionally, you can add more assertions to check the content of the shapes,
// e.g., verify that each shape contains triangles forming one of the rectangles.
// This would involve iterating through the shapes and checking their constituent triangles.
// For this specific test, verifying the count of shapes is sufficient for the requirement.
}
}