voronoi_go/
point.rs

1//! Points, and the exact key that gives them identity.
2
3use core::hash::{Hash, Hasher};
4
5/// The bit pattern of positive zero.
6const POS_ZERO_BITS: u64 = 0.0_f64.to_bits();
7/// The bit pattern of negative zero.
8const NEG_ZERO_BITS: u64 = (-0.0_f64).to_bits();
9
10/// A position on the board, in units where a stone has radius
11/// [`STONE_RADIUS`](crate::STONE_RADIUS).
12///
13/// Equality is **exact**: it compares [`PointKey`]s, so two points are the same
14/// point only when their coordinates are bit-identical (with `-0.0` and `0.0`
15/// treated alike). There is no tolerance in it, deliberately — see
16/// `docs/design.md`.
17#[derive(Clone, Copy, Debug, Default)]
18pub struct Point {
19    /// Horizontal coordinate, increasing rightwards.
20    pub x: f64,
21    /// Vertical coordinate, increasing downwards.
22    pub y: f64,
23}
24
25impl Point {
26    /// A point at `(x, y)`.
27    #[must_use]
28    pub const fn new(x: f64, y: f64) -> Self {
29        Self { x, y }
30    }
31
32    /// This point's identity key.
33    #[must_use]
34    pub const fn key(self) -> PointKey {
35        PointKey::new(self.x, self.y)
36    }
37
38    /// Whether both coordinates are finite numbers.
39    ///
40    /// A point that is not finite is not a position, and the rules say so
41    /// explicitly rather than letting a comparison decide: every ordering
42    /// against a `NaN` is false, so "not outside the board" and "inside the
43    /// board" are different statements about it, and a predicate phrased as the
44    /// first quietly admits it. See `docs/design.md` § "A position is a point on
45    /// the board".
46    #[must_use]
47    pub fn is_finite(self) -> bool {
48        self.x.is_finite() && self.y.is_finite()
49    }
50
51    /// Squared distance to `other`.
52    #[must_use]
53    pub fn distance_squared(self, other: Self) -> f64 {
54        let dx = self.x - other.x;
55        let dy = self.y - other.y;
56        dx * dx + dy * dy
57    }
58
59    /// Euclidean distance to `other`.
60    #[must_use]
61    pub fn distance(self, other: Self) -> f64 {
62        self.distance_squared(other).sqrt()
63    }
64}
65
66impl PartialEq for Point {
67    fn eq(&self, other: &Self) -> bool {
68        self.key() == other.key()
69    }
70}
71
72impl Eq for Point {}
73
74impl Hash for Point {
75    fn hash<H: Hasher>(&self, state: &mut H) {
76        self.key().hash(state);
77    }
78}
79
80/// The identity of a [`Point`]: the exact bit patterns of its coordinates.
81///
82/// This is the only way points are compared for identity anywhere in the crate.
83/// `-0.0` is normalized to `0.0` first, so the two zeroes are one point; every
84/// other value keys on itself and nothing else. Ordering is by bit pattern —
85/// meaningless geometrically, but total and stable, which is what a `BTreeMap`
86/// needs to keep iteration reproducible.
87#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
88pub struct PointKey {
89    /// Bits of the x coordinate.
90    x: u64,
91    /// Bits of the y coordinate.
92    y: u64,
93}
94
95impl PointKey {
96    /// The key for the coordinate pair `(x, y)`.
97    #[must_use]
98    pub const fn new(x: f64, y: f64) -> Self {
99        Self {
100            x: normalize_bits(x),
101            y: normalize_bits(y),
102        }
103    }
104
105    /// The raw `(x, y)` bit patterns.
106    #[must_use]
107    pub const fn bits(self) -> (u64, u64) {
108        (self.x, self.y)
109    }
110}
111
112impl From<Point> for PointKey {
113    fn from(point: Point) -> Self {
114        point.key()
115    }
116}
117
118/// `f64::to_bits`, with negative zero folded onto positive zero so that the two
119/// zeroes are the same point.
120const fn normalize_bits(value: f64) -> u64 {
121    let bits = value.to_bits();
122    if bits == NEG_ZERO_BITS {
123        POS_ZERO_BITS
124    } else {
125        bits
126    }
127}
128
129#[cfg(test)]
130mod tests {
131    #![allow(clippy::unwrap_used, clippy::expect_used)]
132
133    use super::{Point, PointKey};
134    use std::collections::HashMap;
135
136    #[test]
137    fn zeroes_are_one_point() {
138        assert_eq!(Point::new(-0.0, -0.0), Point::new(0.0, 0.0));
139        assert_eq!(PointKey::new(-0.0, 1.0), PointKey::new(0.0, 1.0));
140        assert_eq!(PointKey::new(0.0, -0.0).bits(), (0, 0));
141    }
142
143    #[test]
144    fn identity_has_no_tolerance() {
145        let a = Point::new(1.0, 1.0);
146        let b = Point::new(1.0 + f64::EPSILON, 1.0);
147        assert_ne!(a, b);
148        assert_ne!(a.key(), b.key());
149    }
150
151    #[test]
152    fn key_survives_a_hash_map_round_trip() {
153        let mut map = HashMap::new();
154        map.insert(Point::new(3.5, -0.0).key(), "here");
155        assert_eq!(map.get(&Point::new(3.5, 0.0).key()), Some(&"here"));
156        assert_eq!(map.get(&Point::new(3.5, 1e-300).key()), None);
157    }
158
159    #[test]
160    fn nan_is_not_equal_to_itself_bitwise_but_keys_alike() {
161        // NaN is never produced by the engine's geometry; this only pins that
162        // the key is a pure bit comparison and does not special-case it.
163        let nan = Point::new(f64::NAN, 0.0);
164        assert_eq!(nan.key(), nan.key());
165    }
166
167    #[test]
168    fn distance_is_euclidean() {
169        let a = Point::new(0.0, 0.0);
170        let b = Point::new(3.0, 4.0);
171        assert!((a.distance(b) - 5.0).abs() < 1e-15);
172        assert!((a.distance_squared(b) - 25.0).abs() < 1e-15);
173    }
174}
voronoi_go/point.rs

voronoi_go/
point.rs
