toolbox_rs/
convex_hull.rs

1//! Implementation of Andrew's monotone chain convex hull algorithm
2//! The runtime is $O(n\log n)$ by sorting the points lexicographically by
3//! their lon/lat coordinates, and by subsequently constructing upper and
4//! lower hulls.
5//!
6//! Note that the sorting order is lon/lat to make sure the x coordinate has
7//! higher precedence than the y coordinate -- an invariant of the algorithm.
8
9use crate::geometry::{FPCoordinate, is_clock_wise_turn};
10
11pub fn monotone_chain(input_coordinates: &[FPCoordinate]) -> Vec<FPCoordinate> {
12    let n = input_coordinates.len();
13    if n <= 3 {
14        return input_coordinates.into();
15    }
16
17    // TODO: Implement heuristic by Akl-Toussaint to quickly exclude points
18
19    let mut coordinates: Vec<_> = input_coordinates.into();
20    coordinates.sort_unstable_by_key(|a| (a.lon, a.lat));
21
22    // assemble the hull
23    let mut stack = Vec::new();
24    coordinates.iter().for_each(|p| {
25        while stack.len() >= 2
26            && !is_clock_wise_turn(&stack[stack.len() - 2], &stack[stack.len() - 1], p)
27        {
28            stack.pop();
29        }
30        stack.push(*p);
31    });
32    // remove the last element since they are repeated in the beginning of the other half
33    stack.pop();
34
35    // upper hull
36    let lower_stack_len = stack.len();
37    coordinates.iter().rev().for_each(|p| {
38        while stack.len() >= (2 + lower_stack_len)
39            && !is_clock_wise_turn(&stack[stack.len() - 2], &stack[stack.len() - 1], p)
40        {
41            stack.pop();
42        }
43        stack.push(*p);
44    });
45
46    // remove the last element since they are repeated in the beginning of the other half
47    stack.pop();
48    stack
49}
50
51#[cfg(test)]
52mod tests {
53    use crate::{convex_hull::monotone_chain, geometry::FPCoordinate};
54
55    #[test]
56    fn grid() {
57        let mut coordinates: Vec<FPCoordinate> = Vec::new();
58        for i in 0..100 {
59            coordinates.push(FPCoordinate::new(i / 10, i % 10));
60        }
61
62        let expected = vec![
63            FPCoordinate::new(0, 0),
64            FPCoordinate::new(0, 9),
65            FPCoordinate::new(9, 9),
66            FPCoordinate::new(9, 0),
67        ];
68        let result = monotone_chain(&coordinates);
69        assert_eq!(expected, result);
70    }
71
72    #[test]
73    fn handle_overflow() {
74        let coordinates = vec![
75            FPCoordinate::new_from_lat_lon(33.424732, -114.905286),
76            FPCoordinate::new_from_lat_lon(33.412828, -114.981799),
77            FPCoordinate::new_from_lat_lon(33.402066, -114.978244),
78            FPCoordinate::new_from_lat_lon(33.406161, -114.974526),
79            FPCoordinate::new_from_lat_lon(33.393332, -115.000801),
80            FPCoordinate::new_from_lat_lon(33.393065, -114.981161),
81            FPCoordinate::new_from_lat_lon(33.383992, -114.994943),
82            FPCoordinate::new_from_lat_lon(33.415325, -114.933815),
83            FPCoordinate::new_from_lat_lon(33.413086, -114.941854),
84            FPCoordinate::new_from_lat_lon(33.376757, -114.990162),
85            FPCoordinate::new_from_lat_lon(33.373506, -114.970202),
86            FPCoordinate::new_from_lat_lon(33.439025, -114.898966),
87            FPCoordinate::new_from_lat_lon(33.432417, -114.932620),
88            FPCoordinate::new_from_lat_lon(33.438574, -114.913486),
89            FPCoordinate::new_from_lat_lon(33.415171, -114.945400),
90            FPCoordinate::new_from_lat_lon(33.429861, -114.935991),
91            FPCoordinate::new_from_lat_lon(33.413931, -114.968911),
92            FPCoordinate::new_from_lat_lon(33.413785, -115.000715),
93            FPCoordinate::new_from_lat_lon(33.395238, -114.987989),
94            FPCoordinate::new_from_lat_lon(33.390153, -114.990825),
95            FPCoordinate::new_from_lat_lon(33.388738, -114.979194),
96            FPCoordinate::new_from_lat_lon(33.387090, -114.975945),
97            FPCoordinate::new_from_lat_lon(33.382099, -114.974277),
98            FPCoordinate::new_from_lat_lon(33.375377, -114.984210),
99            FPCoordinate::new_from_lat_lon(33.430011, -114.903102),
100            FPCoordinate::new_from_lat_lon(33.424118, -114.909812),
101            FPCoordinate::new_from_lat_lon(33.412820, -114.943641),
102            FPCoordinate::new_from_lat_lon(33.430089, -114.903063),
103            FPCoordinate::new_from_lat_lon(33.359699, -114.945064),
104            FPCoordinate::new_from_lat_lon(33.413760, -115.000801),
105            FPCoordinate::new_from_lat_lon(33.434750, -114.929788),
106            FPCoordinate::new_from_lat_lon(33.412851, -114.948184),
107            FPCoordinate::new_from_lat_lon(33.395008, -114.991292),
108            FPCoordinate::new_from_lat_lon(33.385784, -114.979111),
109            FPCoordinate::new_from_lat_lon(33.406637, -115.000801),
110            FPCoordinate::new_from_lat_lon(33.440700, -114.920131),
111        ];
112
113        let expected = vec![
114            FPCoordinate::new(33393332, -115000801),
115            FPCoordinate::new(33383992, -114994943),
116            FPCoordinate::new(33376756, -114990162),
117            FPCoordinate::new(33359699, -114945064),
118            FPCoordinate::new(33424732, -114905286),
119            FPCoordinate::new(33439025, -114898966),
120            FPCoordinate::new(33440700, -114920131),
121            FPCoordinate::new(33413760, -115000801),
122        ];
123        let convex_hull = monotone_chain(&coordinates);
124        assert_eq!(expected, convex_hull);
125    }
126
127    #[test]
128    fn tiny_instance() {
129        let coordinates = vec![
130            FPCoordinate::new_from_lat_lon(33.424732, -114.905286),
131            FPCoordinate::new_from_lat_lon(33.412828, -114.981799),
132            FPCoordinate::new_from_lat_lon(33.440700, -114.920131),
133        ];
134
135        let expected = vec![
136            FPCoordinate::new(33424732, -114905286),
137            FPCoordinate::new(33412827, -114981799),
138            FPCoordinate::new(33440700, -114920131),
139        ];
140        let convex_hull = monotone_chain(&coordinates);
141        assert_eq!(expected, convex_hull);
142    }
143}
toolbox_rs/convex_hull.rs

toolbox_rs/
convex_hull.rs
