iron_shapes/algorithms/
convex_hull.rs

1// Copyright (c) 2018-2020 Thomas Kramer.
2// SPDX-FileCopyrightText: 2018-2022 Thomas Kramer
3//
4// SPDX-License-Identifier: AGPL-3.0-or-later
5
6//! Compute the convex hull of a list of points.
7
8use crate::prelude::{Edge, Point, Side, SimplePolygon};
9use num_traits::Num;
10
11/// Get the convex hull of the polygon.
12///
13/// Implements Andrew's Monotone Chain algorithm.
14/// See: <http://geomalgorithms.com/a10-_hull-1.html>
15pub fn convex_hull<T>(points: Vec<Point<T>>) -> SimplePolygon<T>
16where
17    T: Num + Ord + Copy,
18{
19    // Sort points by coordinates.
20    let p = {
21        let mut p = points;
22        p.sort();
23        p
24    };
25
26    assert!(p.len() >= 2);
27
28    // minmin = index of P with min x first and min y second
29    let minmin = 0;
30    let p_minmin = p[minmin];
31    // maxmax = index of P with max x first and max y second
32    let maxmax = p.len() - 1;
33    let p_maxmax = p[maxmax];
34    // minmax = index of P with min x first and max y second
35    let minmax = p
36        .iter()
37        .enumerate()
38        .take_while(|(_, p)| p.x == p_minmin.x)
39        .last()
40        .unwrap()
41        .0;
42    let p_minmax = p[minmax];
43    // maxmin = index of P with max x first and min y second
44    let maxmin = p
45        .iter()
46        .enumerate()
47        .rev()
48        .take_while(|(_, p)| p.x == p_maxmax.x)
49        .last()
50        .unwrap()
51        .0;
52    let p_maxmin = p[maxmin];
53
54    debug_assert!(minmin <= minmax);
55    debug_assert!(minmax <= maxmin || p_minmax.x == p_maxmin.x);
56    debug_assert!(maxmin <= maxmax);
57
58    debug_assert!(p.iter().all(|&p| p_minmin <= p));
59    debug_assert!(p.iter().all(|&p| p_maxmax >= p));
60    debug_assert!(p
61        .iter()
62        .all(|&p| p_minmax.x < p.x || (p_minmax.x == p.x && p_minmax.y >= p.y)));
63    debug_assert!(p
64        .iter()
65        .all(|&p| p_maxmin.x > p.x || (p_maxmin.x == p.x && p_maxmin.y <= p.y)));
66
67    // Handle degenerate case where all x coordinates are equal.
68    if p_minmin.x == p_maxmax.x {
69        if p_minmin.y == p_maxmax.y {
70            SimplePolygon::new(vec![p_minmin])
71        } else {
72            SimplePolygon::new(vec![p_minmin, p_maxmax])
73        }
74    } else {
75        let build_half_hull = |l: Edge<T>, points: &[Point<T>]| {
76            // Push starting point on stack.
77            let mut stack = vec![l.start];
78
79            for &pi in points {
80                // Skip all points that are not strictly right of `l`.
81                if l.side_of(pi) == Side::Right {
82                    while stack.len() >= 2 {
83                        let pt1 = stack[stack.len() - 1];
84                        let pt2 = stack[stack.len() - 2];
85
86                        if Edge::new(pt2, pt1).side_of(pi) == Side::Left {
87                            // `pi` is strictly left of the line defined by the top two elements
88                            // on the stack.
89                            break;
90                        }
91                        stack.pop();
92                    }
93                    stack.push(pi);
94                }
95            }
96
97            stack
98        };
99
100        // Compute the lower hull.
101        let l_min = Edge::new(p_minmin, p_maxmin);
102        let mut lower_half_hull = build_half_hull(l_min, &p[minmax + 1..maxmin]);
103
104        // Push p_maxmin on stack if necessary.
105        if p_maxmin != p_maxmax {
106            lower_half_hull.push(p_maxmin);
107        }
108
109        // Compute the upper hull.
110        let l_max = Edge::new(p_maxmax, p_minmax);
111        let mut upper_half_hull = build_half_hull(l_max, &p[minmax + 1..maxmin]);
112
113        // Push p_minmax on stack if necessary.
114        if p_minmax != p_minmin {
115            upper_half_hull.push(p_minmax);
116        }
117
118        // Join both hulls.
119        lower_half_hull.append(&mut upper_half_hull);
120
121        SimplePolygon::new(lower_half_hull).normalized()
122    }
123}
iron_shapes/algorithms/convex_hull.rs

iron_shapes/algorithms/
convex_hull.rs
