axiolid_exact_arrangement/
ring.rs

1//! Canonical form of output rings.
2
3use axiolid_core::Point2;
4
5/// Order of points by `x`, then `y` (total order on binary64).
6pub fn point_order(left: &Point2, right: &Point2) -> std::cmp::Ordering {
7    left.x
8        .total_cmp(&right.x)
9        .then_with(|| left.y.total_cmp(&right.y))
10}
11
12/// Lexicographic order of point sequences; a prefix sorts first.
13pub fn sequence_order(left: &[Point2], right: &[Point2]) -> std::cmp::Ordering {
14    left.iter()
15        .zip(right)
16        .map(|(a, b)| point_order(a, b))
17        .find(|order| order.is_ne())
18        .unwrap_or_else(|| left.len().cmp(&right.len()))
19}
20
21/// Index at which a ring starts to be canonical: at its lexicographically
22/// smallest point; of several equal smallest points the rotation that orders
23/// lowest wins.
24pub fn canonical_start(points: &[Point2]) -> usize {
25    let rotated = |start: usize| -> Vec<Point2> {
26        points[start..]
27            .iter()
28            .chain(&points[..start])
29            .copied()
30            .collect()
31    };
32    let smallest = points.iter().min_by(|l, r| point_order(l, r)).copied();
33    (0..points.len())
34        .filter(|&start| Some(points[start]) == smallest)
35        .min_by(|&left, &right| sequence_order(&rotated(left), &rotated(right)))
36        .unwrap_or(0)
37}
38
39/// Rotate a ring to start at its lexicographically smallest point; of
40/// several equal smallest points the rotation that orders lowest wins.
41pub fn canonical_rotation(points: Vec<Point2>) -> Vec<Point2> {
42    let start = canonical_start(&points);
43    points[start..]
44        .iter()
45        .chain(&points[..start])
46        .copied()
47        .collect()
48}
axiolid_exact_arrangement/ring.rs

axiolid_exact_arrangement/
ring.rs
