exact_poly/
signed.rs

1//! Signed arithmetic for geometry computations.
2//!
3//! Move lacks native signed integers, so it uses (magnitude: u128, negative: bool) pairs.
4//! Rust has native i128, so we use it directly — behavior matches signed.move exactly.
5//!
6//! Key function: cross_sign(ax,ay, bx,by, cx,cy) → i128
7//! Computes (B−A) × (C−A), the 2D cross product used for convexity and orientation.
8//! Always cast i64 → i128 BEFORE multiplying to prevent overflow.
9
10/// Compute (B−A) × (C−A) cross product for three 2D points A, B, C.
11///
12/// Returns:
13/// - Positive: left turn (CCW)  
14/// - Negative: right turn (CW)
15/// - Zero: collinear
16///
17/// All coordinates are i64 (fixed-point, SCALE=1_000_000).
18/// Uses i128 internally — safe: max cross product ≈ (4×10¹³)² = 1.6×10²⁷, i128 max ≈ 1.7×10³⁸.
19///
20/// Matches behavior of signed::cross_sign() in signed.move:149-184.
21pub fn cross_sign(ax: i64, ay: i64, bx: i64, by: i64, cx: i64, cy: i64) -> i128 {
22    let dx1 = (bx as i128) - (ax as i128);
23    let dy1 = (by as i128) - (ay as i128);
24    let dx2 = (cx as i128) - (ax as i128);
25    let dy2 = (cy as i128) - (ay as i128);
26    dx1 * dy2 - dy1 * dx2
27}
28
29/// Signed subtraction of two u64 values, returning i128.
30/// Equivalent to signed::sub_u64() in signed.move:56-62.
31pub fn sub_u64(a: u64, b: u64) -> i128 {
32    (a as i128) - (b as i128)
33}
34
35/// Sign of a value: +1, 0, or -1.
36pub fn sign(v: i128) -> i32 {
37    v.cmp(&0) as i32
38}
39
40/// True if cross product indicates a left turn (strictly positive).
41pub fn is_left_turn(cross: i128) -> bool {
42    cross > 0
43}
44
45/// True if cross product indicates a right turn (strictly negative).
46pub fn is_right_turn(cross: i128) -> bool {
47    cross < 0
48}
49
50/// True if cross product indicates collinearity (zero).
51pub fn is_collinear(cross: i128) -> bool {
52    cross == 0
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58
59    #[test]
60    fn cross_sign_left_turn_is_positive() {
61        // A=(0,0), B=(2,0), C=(2,2): left turn (CCW)
62        let result = cross_sign(0, 0, 2_000_000, 0, 2_000_000, 2_000_000);
63        assert!(result > 0, "left turn should be positive, got {result}");
64    }
65
66    #[test]
67    fn cross_sign_right_turn_is_negative() {
68        // A=(0,0), B=(2,2), C=(4,0): right turn (CW)
69        let result = cross_sign(0, 0, 2_000_000, 2_000_000, 4_000_000, 0);
70        assert!(result < 0, "right turn should be negative, got {result}");
71    }
72
73    #[test]
74    fn cross_sign_collinear_is_zero() {
75        // A=(0,0), B=(1,0), C=(2,0): collinear
76        let result = cross_sign(0, 0, 1_000_000, 0, 2_000_000, 0);
77        assert_eq!(result, 0, "collinear should be zero");
78    }
79
80    #[test]
81    fn cross_sign_matches_move_test_vectors() {
82        // From signed.move test: cross_sign(0,2, 1,1, 2,0) → zero (collinear diagonal)
83        let zero = cross_sign(0, 2, 1, 1, 2, 0);
84        assert_eq!(zero, 0);
85
86        // From signed.move test: cross_sign(0,0, 2,0, 2,2) → positive (left turn), magnitude=4
87        let left = cross_sign(0, 0, 2, 0, 2, 2);
88        assert_eq!(left, 4);
89
90        // From signed.move test: cross_sign(0,0, 2,2, 4,0) → negative (right turn)
91        let right = cross_sign(0, 0, 2, 2, 4, 0);
92        assert!(right < 0);
93    }
94
95    #[test]
96    fn cross_sign_no_overflow_with_max_world_coordinates() {
97        // MAX_WORLD = 40_075_017_000_000 ≈ 4×10¹³
98        // Worst case cross product ≈ (4×10¹³)² = 1.6×10²⁷, i128 max ≈ 1.7×10³⁸ — safe
99        const MAX_WORLD: i64 = 40_075_017_000_000;
100        let result = cross_sign(0, 0, MAX_WORLD, 0, 0, MAX_WORLD);
101        // Should be MAX_WORLD^2 = 1.605e27
102        let expected = (MAX_WORLD as i128) * (MAX_WORLD as i128);
103        assert_eq!(result, expected);
104    }
105
106    #[test]
107    fn cross_sign_large_negative_no_overflow() {
108        const MAX_WORLD: i64 = 40_075_017_000_000;
109        // Opposite orientation
110        let result = cross_sign(0, MAX_WORLD, MAX_WORLD, 0, 0, 0);
111        assert!(result < 0);
112    }
113
114    #[test]
115    fn sub_u64_positive_and_negative() {
116        assert_eq!(sub_u64(10, 5), 5_i128);
117        assert_eq!(sub_u64(5, 10), -5_i128);
118        assert_eq!(sub_u64(7, 7), 0_i128);
119    }
120
121    #[test]
122    fn sign_returns_correct_values() {
123        assert_eq!(sign(42), 1);
124        assert_eq!(sign(-42), -1);
125        assert_eq!(sign(0), 0);
126    }
127}
exact_poly/signed.rs

exact_poly/
signed.rs
