h3o/coord/localij.rs
1//! Local IJ Coordinates
2//!
3//! Algorithms working with hexagons may want to refer to grid coordinates that
4//! are not interrupted by base cells or faces. These coordinates have 2
5//! coordinate axes spaced 120° apart, with the coordinates anchored by an
6//! origin H3 index.
7//!
8//! - local coordinates are only comparable when they have the same origin
9//! index.
10//! - local coordinates are only valid near the origin. Practically, this is
11//! within the same base cell or a neighboring base cell, except for
12//! pentagons.
13//! - the coordinate space may have deleted or warped regions due to pentagon
14//! distortion.
15//! - there may be multiple coordinates for the same index, with the same
16//! origin.
17//! - the origin may not be at (0, 0) in the local coordinate space.
18
19use super::{CoordIJ, CoordIJK};
20use crate::{
21 BaseCell, CCW, CW, CellIndex, DEFAULT_CELL_INDEX, Direction, Resolution,
22 error::{HexGridError, LocalIjError},
23 index::bits,
24};
25use core::{fmt, num::NonZeroU8};
26
27// -----------------------------------------------------------------------------
28
29/// `IJK` coordinates anchored by an origin.
30#[derive(Debug, Clone, Copy, Eq, PartialEq)]
31pub struct LocalIJK {
32 /// Anchor cell.
33 pub anchor: CellIndex,
34 /// `IJK` coordinates.
35 pub coord: CoordIJK,
36}
37
38impl LocalIJK {
39 /// Return the `IJK` coordinate.
40 pub const fn coord(&self) -> &CoordIJK {
41 &self.coord
42 }
43}
44
45impl TryFrom<LocalIJK> for CellIndex {
46 type Error = LocalIjError;
47
48 fn try_from(value: LocalIJK) -> Result<Self, Self::Error> {
49 let resolution = value.anchor.resolution();
50 let origin_base_cell = value.anchor.base_cell();
51 let origin_on_pent = origin_base_cell.is_pentagon();
52
53 // Initialize the index.
54 let mut bits = bits::set_resolution(DEFAULT_CELL_INDEX, resolution);
55
56 // Check for res 0/base cell.
57 if resolution == Resolution::Zero {
58 let dir = Direction::try_from(value.coord)?;
59 // Bail out if we're moving in an invalid direction off a pentagon.
60 let new_base_cell = origin_base_cell
61 .neighbor(dir)
62 .ok_or(Self::Error::Pentagon)?;
63 return Ok(Self::new_unchecked(h3o_bit::set_base_cell(
64 bits,
65 new_base_cell.into(),
66 )));
67 }
68
69 // We need to find the correct base cell offset (if any) for this H3
70 // index; start with the passed in base cell and resolution res ijk
71 // coordinates in that base cell's coordinate system.
72 let ijk = checked_directions_bits_from_ijk(
73 value.coord,
74 &mut bits,
75 resolution,
76 )
77 .ok_or_else(|| HexGridError::new("IJ coordinates overflow"))?;
78
79 // Lookup the correct base cell.
80 let mut dir = Direction::try_from(ijk)?;
81 let mut base_cell = origin_base_cell.neighbor(dir);
82 // If `base_cell` is invalid, it must be because the origin base cell is
83 // a pentagon, and because pentagon base cells do not border each other,
84 // `base_cell` must not be a pentagon.
85 let index_on_pent = base_cell.is_some_and(BaseCell::is_pentagon);
86
87 if dir != Direction::Center {
88 // If the index is in a warped direction, we need to unwarp the base
89 // cell direction. There may be further need to rotate the index
90 // digits.
91 let mut pentagon_rotations = 0;
92 if origin_on_pent {
93 let leading_direction = bits::first_axe(value.anchor.into())
94 .map_or_else(|| 0, NonZeroU8::get);
95 pentagon_rotations = PENTAGON_ROTATIONS_REVERSE
96 [usize::from(leading_direction)][usize::from(dir)];
97 assert_ne!(pentagon_rotations, 0xff);
98 dir = dir.rotate60::<CCW>(pentagon_rotations.into());
99
100 // The pentagon rotations are being chosen so that dir is not
101 // the deleted direction. If it still happens, it means we're
102 // moving into a deleted subsequence, so there is no index here.
103 let fixed_base_cell = origin_base_cell
104 .neighbor(dir)
105 .ok_or(Self::Error::Pentagon)?;
106 base_cell = Some(fixed_base_cell);
107 debug_assert!(!fixed_base_cell.is_pentagon());
108 }
109 let fixed_base_cell = base_cell.expect("fixed base cell");
110
111 // Now we can determine the relation between the origin and target
112 // base cell.
113 let base_cell_rotations = origin_base_cell.neighbor_rotation(dir);
114
115 // Adjust for pentagon warping within the base cell. The base cell
116 // should be in the right location, so now we need to rotate the
117 // index back. We might not need to check for errors since we would
118 // just be double mapping.
119 if index_on_pent {
120 let rev_dir = usize::from(
121 fixed_base_cell
122 .direction(origin_base_cell)
123 .expect("reverse direction"),
124 );
125
126 // Adjust for the different coordinate space in the two base
127 // cells. This is done first because we need to do the pentagon
128 // rotations based on the leading digit in the pentagon's
129 // coordinate system.
130 bits = bits::rotate60::<CCW>(bits, base_cell_rotations.into());
131
132 let leading_direction = usize::from(
133 bits::first_axe(bits).map_or_else(|| 0, NonZeroU8::get),
134 );
135 let pentagon_rotations = if fixed_base_cell.is_polar_pentagon()
136 {
137 PENTAGON_ROTATIONS_REVERSE_POLAR[rev_dir][leading_direction]
138 } else {
139 PENTAGON_ROTATIONS_REVERSE_NONPOLAR[rev_dir]
140 [leading_direction]
141 };
142 // For this to occur, `rev_direction` would need to be 1. Since
143 // `rev_direction` is from the index base cell (which is a
144 // pentagon) towards the origin, this should never be the case.
145 assert_ne!(pentagon_rotations, 0xff);
146
147 bits = (0..pentagon_rotations)
148 .fold(bits, |acc, _| bits::pentagon_rotate60::<CCW>(acc));
149 } else {
150 assert!(pentagon_rotations != 0xff);
151 let count =
152 usize::from(pentagon_rotations + base_cell_rotations);
153 bits = bits::rotate60::<CCW>(bits, count);
154 }
155 } else if origin_on_pent && index_on_pent {
156 let origin_leading_dir = usize::from(
157 bits::first_axe(value.anchor.into())
158 .map_or_else(|| 0, NonZeroU8::get),
159 );
160 let index_leading_dir = usize::from(
161 bits::first_axe(bits).map_or_else(|| 0, NonZeroU8::get),
162 );
163
164 let rotations = PENTAGON_ROTATIONS_REVERSE[origin_leading_dir]
165 [index_leading_dir];
166 assert!(rotations != 0xff, "invalid K axis digit");
167 bits = bits::rotate60::<CCW>(bits, rotations.into());
168 }
169
170 if index_on_pent {
171 // TODO: There are cases which are failed but not accounted for
172 // here, instead just fail if the recovered index is invalid.
173 if bits::first_axe(bits) == Direction::K.axe() {
174 return Err(Self::Error::Pentagon);
175 }
176 }
177
178 let base_cell = base_cell
179 .ok_or_else(|| HexGridError::new("cannot resolve base cell"))?;
180 Ok(Self::new_unchecked(h3o_bit::set_base_cell(
181 bits,
182 base_cell.into(),
183 )))
184 }
185}
186
187/// Set the directions of a cell index (in-place) from finest resolution up.
188///
189/// IJK coordinates are adjusted during the traversal so that, at the end, they
190/// should match the IJK of the base cell in the coordinate system of the
191/// current base cell.
192///
193/// Returns the adjusted `IJK` coordinates.
194#[expect(
195 clippy::inline_always,
196 reason = "4-5% boost, up to 13% at resolution 1"
197)]
198#[inline(always)]
199pub fn checked_directions_bits_from_ijk(
200 mut ijk: CoordIJK,
201 bits: &mut u64,
202 resolution: Resolution,
203) -> Option<CoordIJK> {
204 for res in Resolution::range(Resolution::One, resolution).rev() {
205 let last_ijk = ijk;
206 let last_center = if res.is_class3() {
207 // Rotate CCW.
208 ijk = ijk.checked_up_aperture7::<{ CCW }>()?;
209 ijk.down_aperture7::<{ CCW }>()
210 } else {
211 // Rotate CW.
212 ijk = ijk.checked_up_aperture7::<{ CW }>()?;
213 ijk.down_aperture7::<{ CW }>()
214 };
215
216 let diff = (last_ijk - last_center).normalize();
217 let direction = Direction::try_from(diff).expect("unit IJK coordinate");
218 // SAFETY: `res` is in [resolution; 1], thus valid.
219 *bits = bits::set_direction(*bits, direction.into(), res);
220 }
221
222 Some(ijk)
223}
224
225// -----------------------------------------------------------------------------
226
227/// `IJ` coordinates anchored by an origin.
228#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
229#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
230pub struct LocalIJ {
231 /// Anchor cell.
232 pub anchor: CellIndex,
233 /// `IJ` coordinates.
234 pub coord: CoordIJ,
235}
236
237impl LocalIJ {
238 /// Initialize a new `LocalIJ` from its components.
239 ///
240 /// Could be used to build invalid local IJ coordinate, only used for tests.
241 #[must_use]
242 pub const fn new(anchor: CellIndex, coord: CoordIJ) -> Self {
243 Self { anchor, coord }
244 }
245}
246
247impl TryFrom<LocalIJ> for CellIndex {
248 type Error = LocalIjError;
249
250 fn try_from(value: LocalIJ) -> Result<Self, Self::Error> {
251 let local_ijk = LocalIJK {
252 anchor: value.anchor,
253 coord: CoordIJK::try_from(value.coord)?,
254 };
255 Self::try_from(local_ijk)
256 }
257}
258
259impl fmt::Display for LocalIJ {
260 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
261 write!(f, "{} {}", self.anchor, self.coord)
262 }
263}
264
265// -----------------------------------------------------------------------------
266
267// In the lookup table below, it would be nice to use `u8` with a custom niche.
268// Not supported yet though: https://github.com/rust-lang/rfcs/pull/3334
269
270/// Reverse base cell direction -> leading index digit -> rotations 60 CCW.
271///
272/// For reversing the rotation introduced in `PENTAGON_ROTATIONS` when the
273/// origin is on a pentagon (regardless of the base cell of the index).
274#[rustfmt::skip]
275const PENTAGON_ROTATIONS_REVERSE: [[u8; 7]; 7] = [
276 [ 0, 0, 0, 0, 0, 0, 0], // 0
277 [ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff], // 1
278 [ 0, 1, 0, 0, 0, 0, 0], // 2
279 [ 0, 1, 0, 0, 0, 1, 0], // 3
280 [ 0, 5, 0, 0, 0, 0, 0], // 4
281 [ 0, 5, 0, 5, 0, 0, 0], // 5
282 [ 0, 0, 0, 0, 0, 0, 0], // 6
283];
284
285/// Reverse base cell direction -> leading index digit -> rotations 60 CCW.
286///
287/// For reversing the rotation introduced in `PENTAGON_ROTATIONS` when the index
288/// is on a pentagon and the origin is not.
289#[rustfmt::skip]
290const PENTAGON_ROTATIONS_REVERSE_NONPOLAR: [[u8; 7]; 7] = [
291 [ 0, 0, 0, 0, 0, 0, 0], // 0
292 [ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff], // 1
293 [ 0, 1, 0, 0, 0, 0, 0], // 2
294 [ 0, 1, 0, 0, 0, 1, 0], // 3
295 [ 0, 5, 0, 0, 0, 0, 0], // 4
296 [ 0, 1, 0, 5, 1, 1, 0], // 5
297 [ 0, 0, 0, 0, 0, 0, 0], // 6
298];
299
300/// Reverse base cell direction -> leading index digit -> rotations 60 CCW.
301///
302/// For reversing the rotation introduced in `PENTAGON_ROTATIONS` when the index
303/// is on a polar pentagon and the origin is not.
304#[rustfmt::skip]
305const PENTAGON_ROTATIONS_REVERSE_POLAR: [[u8; 7]; 7] = [
306 [ 0, 0, 0, 0, 0, 0, 0], // 0
307 [ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff], // 1
308 [ 0, 1, 1, 1, 1, 1, 1], // 2
309 [ 0, 1, 0, 0, 0, 1, 0], // 3
310 [ 0, 1, 0, 0, 1, 1, 1], // 4
311 [ 0, 1, 0, 5, 1, 1, 0], // 5
312 [ 0, 1, 1, 0, 1, 1, 1], // 6
313];
314
315#[cfg(test)]
316#[path = "./localij_tests.rs"]
317mod tests;