Skip to main content

concave_hull/
lib.rs

1//! # concave-hull
2//!
3//! `concave-hull` is an implementation of the [gift opening concave hull algorithm](https://deeplearning.lipingyang.org/wp-content/uploads/2019/07/Project-10-report_Implementation-of-a-fast-and-efficient-concave-hull-algorithm.pdf), written in Rust.
4//!
5//! The top level export is a function called `concave_hull`.
6//! See the docs for that function for details on usage, or check the example at `examples/basic.rs`
7//!
8//! ## Choosing the concavity parameter
9//!
10//! Concave hulls are a somewhat subjective thing.
11//! While it's possible to generate a concave hull which minimizes the area of the final polygon, this is often undesirable, as it leads to very crinkly shapes.
12//! To remedy this, a concavity parameter is exposed, which controls how tight the final concave hull is around the point cloud.
13//! In general, you should pick a concavity parameter which produces "desirable" results on your datasets, whatever that means for your application.
14//! Here is some guidance:
15//! - The concavity parameter ranges from zero to positive infinity
16//! - `0` produces a maximally crinkly shape
17//! - `+inf` prevents any concavity, returning the convex hull of the point cloud
18//! - `40` is usually a good starting point
19//!
20//! Note that the concavity parameter **is not scale invariant**.
21//! This means that a point cloud which covers an area from 0 to 100 will need a smaller concavity parameter than an equivalent point cloud that covers an area from 0 to 1000.
22//!
23//! ## Features
24//!
25//! This crate has two features for precision:
26//! - `f32` (default feature): Enables `f32`-precision versions of the concave hull computation and relevant re-exports (an `f32`-precision point, for example)
27//! - `f64`: Enables `f64`-precision versions of the concave hull computation and relevant re-exports (an `f64`-precision point, for example)
28//!
29//! If neither feature is enabled, then this crate has no public exports.
30//! Enabling both simultaneously is supported (cargo features must be purely additive), with relevant functions being exported under the `f32` or `f64` submodules, respectively.
31//!
32//! This crate has one additional feature, `benches`, which is only used for benchmarks.
33//! End users of this library should never enable it.
34
35#![warn(missing_docs)]
36#![feature(trait_alias)]
37
38use nalgebra::{RealField, Scalar};
39use num_traits::float::TotalOrder;
40
41mod concave;
42mod edge;
43mod segment_intersect;
44
45#[cfg(feature = "benches")]
46pub use edge::Edge;
47#[cfg(feature = "benches")]
48pub use segment_intersect::edges_intersect;
49
50/// Trait bound for scalars we can work with
51///
52/// In practice, I think this is just the float types
53#[cfg(not(feature = "benches"))]
54pub(crate) trait HullScalar = Scalar + RealField + Copy + TotalOrder;
55
56/// Trait bound for scalars we can work with
57///
58/// In practice, I think this is just the float types
59#[cfg(feature = "benches")]
60pub trait HullScalar = Scalar + RealField + Copy + TotalOrder;
61
62/// Spatial points and concave hull generation for [`prim@f32`] precision
63#[cfg(feature = "f32")]
64pub mod f32 {
65    /// [`parry2d`]'s point type, which [`concave_hull`] uses internally for all its math
66    ///
67    /// This is also the point type used in function signatures and returns
68    pub type Point = parry2d::math::Point<f32>;
69    pub use parry2d;
70
71    use crate::concave::concave_hull_inner;
72
73    /// Computes the concave hull of the provided point cloud, using the provided concavity parameter
74    ///
75    /// Inputs:
76    /// - `points`: A list of points, making up the point cloud to generate the concave hull for.
77    /// It is assumed that this list contains no repeat points.
78    /// - `concavity`: A parameter determining how concave the hull should be.
79    ///
80    /// See the crate-level docs for guidance on picking the concavity parameter.
81    /// The returned [`Vec`] contains a tuple of:
82    /// - The index of the hull point in the original slice
83    /// - The value of the point in the original slice
84    ///
85    /// The points are returned in counter-clockwise order.
86    pub fn concave_hull(points: &[Point], concavity: f32) -> Vec<(usize, Point)> {
87        if points.len() <= 1 {
88            // Degenerate case with too few points to make a convex hull
89            // Just return the original point (or nothing)
90            return points.iter().enumerate().map(|(id, p)| (id, *p)).collect();
91        }
92
93        // Get the convex hull from parry
94        let convex = parry2d::transformation::convex_hull_idx(points);
95
96        concave_hull_inner(points, concavity, convex)
97    }
98}
99
100/// Spatial points and concave hull generation for [`prim@f64`] precision
101#[cfg(feature = "f64")]
102pub mod f64 {
103    /// [`parry2d`]'s point type, which [`concave_hull`] uses internally for all its math
104    ///
105    /// This is also the point type used in function signatures and returns
106    pub type Point = parry2d::math::Point<f64>;
107    pub use parry2d_f64 as parry2d;
108
109    use crate::concave::concave_hull_inner;
110
111    /// Computes the concave hull of the provided point cloud, using the provided concavity parameter
112    ///
113    /// Inputs:
114    /// - `points`: A list of points, making up the point cloud to generate the concave hull for.
115    /// It is assumed that this list contains no repeat points.
116    /// - `concavity`: A parameter determining how concave the hull should be.
117    ///
118    /// See the crate-level docs for guidance on picking the concavity parameter.
119    /// The returned [`Vec`] contains a tuple of:
120    /// - The index of the hull point in the original slice
121    /// - The value of the point in the original slice
122    ///
123    /// The points are returned in counter-clockwise order.
124    pub fn concave_hull(points: &[Point], concavity: f64) -> Vec<(usize, Point)> {
125        if points.len() <= 1 {
126            // Degenerate case with too few points to make a convex hull
127            // Just return the original point (or nothing)
128            return points.iter().enumerate().map(|(id, p)| (id, *p)).collect();
129        }
130
131        // Get the convex hull from parry
132        let convex = parry2d::transformation::convex_hull_idx(points);
133
134        concave_hull_inner(points, concavity, convex)
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::f32::*;
141
142    mod small_clouds {
143        use super::*;
144
145        /// An array of points in a numpad grid, in numpad order
146        ///
147        /// 7 8 9
148        /// 4 5 6
149        /// 1 2 3
150        /// 0
151        const POINTS: [Point; 10] = [
152            Point::new(0., 0.),
153            Point::new(0., 1.),
154            Point::new(1., 1.),
155            Point::new(2., 1.),
156            Point::new(0., 2.),
157            Point::new(1., 2.),
158            Point::new(2., 2.),
159            Point::new(0., 3.),
160            Point::new(1., 3.),
161            Point::new(2., 3.),
162        ];
163
164        #[test]
165        fn zero_points() {
166            let hull = concave_hull(&POINTS[0..0], 10.);
167            assert_eq!(hull, Vec::new());
168        }
169
170        #[test]
171        fn one_point() {
172            let hull = concave_hull(&POINTS[0..1], 10.);
173            assert_eq!(hull, Vec::from([(0, POINTS[0])]));
174        }
175
176        #[test]
177        fn two_points() {
178            let hull = concave_hull(&POINTS[0..2], 10.);
179            assert_eq!(hull, Vec::from([(0, POINTS[0]), (1, POINTS[1])]));
180        }
181
182        #[test]
183        fn three_points() {
184            let hull = concave_hull(&POINTS[0..3], 10.);
185            assert_eq!(
186                hull,
187                Vec::from([(0, POINTS[0]), (2, POINTS[2]), (1, POINTS[1]),])
188            );
189        }
190
191        #[test]
192        fn square() {
193            let hull = concave_hull(&[POINTS[1], POINTS[2], POINTS[4], POINTS[5]], 10.);
194            assert_eq!(
195                hull,
196                Vec::from([
197                    (2, POINTS[4]),
198                    (0, POINTS[1]),
199                    (1, POINTS[2]),
200                    (3, POINTS[5]),
201                ])
202            );
203        }
204    }
205
206    mod question_mark {
207        use std::fs::File;
208
209        use csv::ReaderBuilder;
210
211        use super::*;
212
213        fn load_question_mark() -> Vec<Point> {
214            let f = File::open("./test_data/question_mark.csv").unwrap();
215
216            let mut reader = ReaderBuilder::new().has_headers(false).from_reader(f);
217
218            reader
219                .records()
220                .map(|r| {
221                    let r = r.unwrap();
222                    let x = r[0].parse().unwrap();
223                    let y = r[1].parse().unwrap();
224
225                    Point::new(x, y)
226                })
227                .collect()
228        }
229
230        #[test]
231        fn reasonable_concave() {
232            let points = load_question_mark();
233            let hull = concave_hull(&points, 40.);
234
235            let expected = Vec::from([
236                (16, Point::new(187.0, 87.0)),
237                (17, Point::new(173.0, 97.0)),
238                (24, Point::new(177.0, 180.0)),
239                (1, Point::new(182.0, 201.0)),
240                (20, Point::new(179.0, 225.0)),
241                (27, Point::new(182.0, 245.0)),
242                (31, Point::new(187.0, 270.0)),
243                (32, Point::new(204.0, 306.0)),
244                (81, Point::new(221.0, 332.0)),
245                (42, Point::new(248.0, 361.0)),
246                (41, Point::new(243.0, 388.0)),
247                (79, Point::new(247.0, 406.0)),
248                (47, Point::new(240.0, 425.0)),
249                (49, Point::new(228.0, 447.0)),
250                (50, Point::new(211.0, 466.0)),
251                (59, Point::new(192.0, 473.0)),
252                (60, Point::new(156.0, 481.0)),
253                (62, Point::new(128.0, 483.0)),
254                (71, Point::new(100.0, 474.0)),
255                (70, Point::new(80.0, 456.0)),
256                (72, Point::new(60.0, 461.0)),
257                (74, Point::new(34.0, 446.0)),
258                (75, Point::new(32.0, 410.0)),
259                (76, Point::new(53.0, 396.0)),
260                (67, Point::new(78.0, 400.0)),
261                (66, Point::new(100.0, 408.0)),
262                (55, Point::new(134.0, 420.0)),
263                (54, Point::new(165.0, 415.0)),
264                (43, Point::new(177.0, 378.0)),
265                (38, Point::new(179.0, 347.0)),
266                (35, Point::new(158.0, 333.0)),
267                (34, Point::new(145.0, 299.0)),
268                (28, Point::new(141.0, 274.0)),
269                (22, Point::new(134.0, 230.0)),
270                (2, Point::new(141.0, 208.0)),
271                (23, Point::new(143.0, 185.0)),
272                (0, Point::new(162.0, 168.0)),
273                (5, Point::new(160.0, 100.0)),
274                (4, Point::new(141.0, 92.0)),
275                (9, Point::new(134.0, 70.0)),
276                (10, Point::new(126.0, 53.0)),
277                (11, Point::new(139.0, 34.0)),
278                (12, Point::new(160.0, 29.0)),
279                (14, Point::new(182.0, 34.0)),
280                (15, Point::new(192.0, 58.0)),
281            ]);
282
283            assert_eq!(hull, expected);
284        }
285
286        #[test]
287        fn maximally_concave() {
288            let points = load_question_mark();
289            let hull = concave_hull(&points, 0.);
290
291            let expected = Vec::from([
292                (21, Point::new(163.0, 208.0)),
293                (26, Point::new(162.0, 219.0)),
294                (20, Point::new(179.0, 225.0)),
295                (3, Point::new(158.0, 236.0)),
296                (27, Point::new(182.0, 245.0)),
297                (31, Point::new(187.0, 270.0)),
298                (29, Point::new(156.0, 265.0)),
299                (30, Point::new(173.0, 293.0)),
300                (80, Point::new(187.0, 320.0)),
301                (32, Point::new(204.0, 306.0)),
302                (36, Point::new(190.0, 335.0)),
303                (37, Point::new(206.0, 355.0)),
304                (81, Point::new(221.0, 332.0)),
305                (40, Point::new(221.0, 362.0)),
306                (42, Point::new(248.0, 361.0)),
307                (41, Point::new(243.0, 388.0)),
308                (79, Point::new(247.0, 406.0)),
309                (47, Point::new(240.0, 425.0)),
310                (46, Point::new(219.0, 410.0)),
311                (45, Point::new(196.0, 418.0)),
312                (49, Point::new(228.0, 447.0)),
313                (48, Point::new(218.0, 439.0)),
314                (51, Point::new(197.0, 449.0)),
315                (50, Point::new(211.0, 466.0)),
316                (59, Point::new(192.0, 473.0)),
317                (58, Point::new(173.0, 466.0)),
318                (60, Point::new(156.0, 481.0)),
319                (57, Point::new(153.0, 456.0)),
320                (63, Point::new(138.0, 464.0)),
321                (62, Point::new(128.0, 483.0)),
322                (61, Point::new(119.0, 468.0)),
323                (71, Point::new(100.0, 474.0)),
324                (64, Point::new(100.0, 442.0)),
325                (70, Point::new(80.0, 456.0)),
326                (72, Point::new(60.0, 461.0)),
327                (69, Point::new(61.0, 437.0)),
328                (74, Point::new(34.0, 446.0)),
329                (73, Point::new(43.0, 429.0)),
330                (75, Point::new(32.0, 410.0)),
331                (77, Point::new(60.0, 418.0)),
332                (76, Point::new(53.0, 396.0)),
333                (78, Point::new(66.0, 401.0)),
334                (67, Point::new(78.0, 400.0)),
335                (68, Point::new(83.0, 422.0)),
336                (66, Point::new(100.0, 408.0)),
337                (65, Point::new(112.0, 427.0)),
338                (56, Point::new(124.0, 442.0)),
339                (55, Point::new(134.0, 420.0)),
340                (53, Point::new(155.0, 430.0)),
341                (52, Point::new(179.0, 435.0)),
342                (54, Point::new(165.0, 415.0)),
343                (44, Point::new(179.0, 401.0)),
344                (39, Point::new(204.0, 386.0)),
345                (43, Point::new(177.0, 378.0)),
346                (38, Point::new(179.0, 347.0)),
347                (35, Point::new(158.0, 333.0)),
348                (33, Point::new(165.0, 311.0)),
349                (34, Point::new(145.0, 299.0)),
350                (28, Point::new(141.0, 274.0)),
351                (22, Point::new(134.0, 230.0)),
352                (2, Point::new(141.0, 208.0)),
353                (23, Point::new(143.0, 185.0)),
354                (25, Point::new(163.0, 189.0)),
355                (0, Point::new(162.0, 168.0)),
356                (5, Point::new(160.0, 100.0)),
357                (4, Point::new(141.0, 92.0)),
358                (19, Point::new(153.0, 87.0)),
359                (8, Point::new(155.0, 75.0)),
360                (9, Point::new(134.0, 70.0)),
361                (10, Point::new(126.0, 53.0)),
362                (7, Point::new(151.0, 58.0)),
363                (11, Point::new(139.0, 34.0)),
364                (12, Point::new(160.0, 29.0)),
365                (14, Point::new(182.0, 34.0)),
366                (13, Point::new(167.0, 53.0)),
367                (15, Point::new(192.0, 58.0)),
368                (6, Point::new(177.0, 70.0)),
369                (16, Point::new(187.0, 87.0)),
370                (18, Point::new(168.0, 75.0)),
371                (17, Point::new(173.0, 97.0)),
372                (24, Point::new(177.0, 180.0)),
373                (1, Point::new(182.0, 201.0)),
374            ]);
375
376            assert_eq!(hull, expected);
377        }
378
379        #[test]
380        fn minimally_concave() {
381            let points = load_question_mark();
382            let hull = concave_hull(&points, f32::INFINITY);
383
384            let expected = Vec::from([
385                (50, Point::new(211.0, 466.0)),
386                (59, Point::new(192.0, 473.0)),
387                (60, Point::new(156.0, 481.0)),
388                (62, Point::new(128.0, 483.0)),
389                (71, Point::new(100.0, 474.0)),
390                (72, Point::new(60.0, 461.0)),
391                (74, Point::new(34.0, 446.0)),
392                (75, Point::new(32.0, 410.0)),
393                (10, Point::new(126.0, 53.0)),
394                (11, Point::new(139.0, 34.0)),
395                (12, Point::new(160.0, 29.0)),
396                (14, Point::new(182.0, 34.0)),
397                (15, Point::new(192.0, 58.0)),
398                (42, Point::new(248.0, 361.0)),
399                (79, Point::new(247.0, 406.0)),
400                (47, Point::new(240.0, 425.0)),
401                (49, Point::new(228.0, 447.0)),
402            ]);
403
404            assert_eq!(hull, expected);
405        }
406    }
407}