qdrant_edge/segment/index/field_index/
geo_hash.rs

1use std::fmt::Display;
2use std::ops::{Index, Range};
3
4use ecow::EcoString;
5use geo::{Coord, Distance, Haversine, Intersects, LineString, Point, Polygon};
6use geohash::{Direction, GeohashError, decode, decode_bbox, encode};
7use itertools::Itertools;
8use ordered_float::OrderedFloat;
9
10use crate::segment::common::operation_error::{OperationError, OperationResult};
11use crate::segment::types::{GeoBoundingBox, GeoPoint, GeoPolygon, GeoRadius};
12
13/// Packed representation of a geohash string.
14///
15/// Geohash string is a base32 encoded string.
16/// It means that each character can be represented with 5 bits.
17/// Also, the length of the string is encoded as 4 bits (because max size is `GeoHash::MAX_LEN` = 12).
18/// So, the packed representation is 64 bits long: 5bits * 12chars + 4bits = 64 bits.
19///
20/// Characters are stored in reverse order to keep lexicographical order.
21/// Length is stored in the last 4 bits.
22/// Unused bits are set to 0.
23///
24/// Example for `dr5ruj447`:
25///
26/// ```text
27/// Bit no.     63                                                                    4  3  0
28///             |                                                                     |  |  |
29/// Bit value   01100 10111 00101 10111 11010 10001 00100 00100 00111 00000 00000 00000  1001
30/// Decoded     'd'   'r'   '5'   'r'   'u'   'j'   '4'   '4'   '7'                      9
31/// Meaning     s[0]  s[1]  s[2]  s[3]  s[4]  s[5]  s[6]  s[7]  s[8]  s[9]  s[10] s[11]  length
32/// ```
33#[derive(Default, Clone, Copy, Debug, PartialEq, Hash, Ord, PartialOrd, Eq)]
34pub struct GeoHash(u64);
35
36/// Variation of [`GeoHash`] to serialize/deserialize without validation.
37///
38/// Unlike [`GeoHash`], it might contain invalid bit patterns, e.g. `length > GeoHash::MAX_LEN`,
39/// or non-zeroed unused bits in characters.
40#[derive(Copy, Clone, Debug, bytemuck::Pod, bytemuck::Zeroable)]
41#[repr(C)]
42pub struct GeoHashRaw(pub u64);
43
44impl GeoHashRaw {
45    /// No-op, unless the raw value contains invalid bits.
46    pub fn normalize(self) -> GeoHash {
47        GeoHash::new_from_parts(self.0, self.0 & GeoHash::LEN_MASK)
48    }
49}
50
51impl From<GeoHash> for GeoHashRaw {
52    fn from(hash: GeoHash) -> GeoHashRaw {
53        GeoHashRaw(hash.0)
54    }
55}
56
57const LON_RANGE: Range<f64> = -180.0..180.0;
58const LAT_RANGE: Range<f64> = -90.0..90.0;
59const COORD_EPS: f64 = 1e-12;
60
61impl Index<usize> for GeoHash {
62    type Output = u8;
63
64    fn index(&self, i: usize) -> &Self::Output {
65        assert!(i < self.len());
66        let index = (self.0 >> Self::shift_value(i)) & ((1 << GeoHash::CHAR_BITS) - 1);
67        &GeoHash::BASE32[index as usize]
68    }
69}
70
71impl TryFrom<EcoString> for GeoHash {
72    type Error = GeohashError;
73
74    fn try_from(hash: EcoString) -> Result<Self, Self::Error> {
75        Self::new(hash.as_bytes())
76    }
77}
78
79impl TryFrom<String> for GeoHash {
80    type Error = GeohashError;
81
82    fn try_from(hash: String) -> Result<Self, Self::Error> {
83        Self::new(hash.as_bytes())
84    }
85}
86
87impl From<GeoHash> for EcoString {
88    fn from(hash: GeoHash) -> Self {
89        hash.iter().map(char::from).collect()
90    }
91}
92
93impl Display for GeoHash {
94    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
95        EcoString::from(*self).fmt(f)
96    }
97}
98
99pub struct GeoHashIterator(u64);
100
101impl Iterator for GeoHashIterator {
102    type Item = u8;
103
104    fn next(&mut self) -> Option<Self::Item> {
105        let len = self.0 & GeoHash::LEN_MASK;
106        if len > 0 {
107            // take first character from the packed value
108            let char_index = self.0 >> (GeoHash::BITS - GeoHash::CHAR_BITS);
109
110            // shift packed value to the left to get the next character
111            self.0 = (self.0 << GeoHash::CHAR_BITS) | (len - 1);
112
113            // get character from the base32 alphabet
114            Some(GeoHash::BASE32[char_index as usize])
115        } else {
116            None
117        }
118    }
119}
120
121impl GeoHash {
122    const BITS: u32 = u64::BITS;
123
124    /// Max length of geo-hash used for indexing. size=12 is about 6cm2
125    const MAX_LEN: usize = 12;
126
127    /// Four least significant bits are length.
128    /// The negation of this mask is the packed characters mask.
129    const LEN_MASK: u64 = 0b1111;
130
131    const LEN_BITS: u32 = 4;
132
133    const CHAR_BITS: u32 = 5;
134
135    /// The alphabet for the base32 encoding used in geohashing.
136    const BASE32: [u8; 32] = *b"0123456789bcdefghjkmnpqrstuvwxyz";
137
138    fn new<H>(s: H) -> Result<Self, GeohashError>
139    where
140        H: AsRef<[u8]>,
141    {
142        let s = s.as_ref();
143        if s.len() > GeoHash::MAX_LEN {
144            return Err(GeohashError::InvalidLength(s.len()));
145        }
146        let mut packed: u64 = 0;
147        for (i, c) in s.iter().enumerate() {
148            let index = GeoHash::BASE32.iter().position(|x| x == c).unwrap() as u64;
149            packed |= index << Self::shift_value(i);
150        }
151        packed |= s.len() as u64;
152        Ok(Self(packed))
153    }
154
155    fn new_from_parts(characters: u64, len: u64) -> GeoHash {
156        let len = len.min(GeoHash::MAX_LEN as u64);
157        let characters_mask = !GeoHash::LEN_MASK
158            << (GeoHash::BITS - GeoHash::LEN_BITS - GeoHash::CHAR_BITS * len as u32);
159        GeoHash((characters & characters_mask) | len)
160    }
161
162    pub fn iter(&self) -> GeoHashIterator {
163        GeoHashIterator(self.0)
164    }
165
166    pub fn is_empty(&self) -> bool {
167        self.len() == 0
168    }
169
170    pub fn len(&self) -> usize {
171        (self.0 & GeoHash::LEN_MASK) as usize
172    }
173
174    pub fn truncate(&self, new_len: usize) -> Self {
175        assert!(new_len <= self.len());
176        GeoHash::new_from_parts(self.0, new_len as u64)
177    }
178
179    pub fn starts_with(&self, other: GeoHash) -> bool {
180        if self.len() < other.len() {
181            // other is longer than self
182            return false;
183        }
184        if other.is_empty() {
185            // empty string is a prefix of any string
186            return true;
187        }
188
189        let self_shifted = self.0 >> Self::shift_value(other.len() - 1);
190        let other_shifted = other.0 >> Self::shift_value(other.len() - 1);
191        self_shifted == other_shifted
192    }
193
194    // Returns the shift value. If we apply this shift to the packed value, we get the value of the `i`-th character.
195    fn shift_value(i: usize) -> u32 {
196        assert!(i < GeoHash::MAX_LEN);
197        GeoHash::LEN_BITS + GeoHash::CHAR_BITS * (GeoHash::MAX_LEN as u32 - 1 - i as u32)
198    }
199}
200
201impl From<GeoPoint> for Coord<f64> {
202    fn from(point: GeoPoint) -> Self {
203        Self {
204            x: point.lon.0,
205            y: point.lat.0,
206        }
207    }
208}
209
210pub fn common_hash_prefix(geo_hashes: &[GeoHash]) -> Option<GeoHash> {
211    if geo_hashes.is_empty() {
212        return None;
213    }
214    let first = &geo_hashes[0];
215    let mut prefix: usize = first.len();
216    for geo_hash in geo_hashes.iter().skip(1) {
217        for i in 0..prefix {
218            if first[i] != geo_hash[i] {
219                prefix = i;
220                break;
221            }
222        }
223    }
224    Some(first.truncate(prefix))
225}
226
227/// Fix longitude for spherical overflow
228/// lon: 181.0 -> -179.0
229fn sphere_lon(lon: f64) -> f64 {
230    let mut res_lon = lon;
231    if res_lon > LON_RANGE.end {
232        res_lon = LON_RANGE.start + res_lon - LON_RANGE.end;
233    }
234    if res_lon < LON_RANGE.start {
235        res_lon = LON_RANGE.end + res_lon - LON_RANGE.start;
236    }
237    res_lon
238}
239
240/// Fix latitude for spherical overflow
241fn sphere_lat(lat: f64) -> f64 {
242    let mut res_lat = lat;
243    if res_lat > LAT_RANGE.end {
244        res_lat = LAT_RANGE.end - COORD_EPS;
245    }
246    if res_lat < LAT_RANGE.start {
247        res_lat = LAT_RANGE.start + COORD_EPS;
248    }
249    res_lat
250}
251
252/// Get neighbour geohash even from the other side of coordinates
253fn sphere_neighbor(hash: GeoHash, direction: Direction) -> Result<GeoHash, GeohashError> {
254    let hash_str = EcoString::from(hash);
255    let (coord, lon_err, lat_err) = decode(hash_str.as_str())?;
256    let (dlat, dlng) = direction.to_tuple();
257    let lon = sphere_lon(coord.x + 2f64 * lon_err.abs() * dlng);
258    let lat = sphere_lat(coord.y + 2f64 * lat_err.abs() * dlat);
259
260    let neighbor_coord = Coord { x: lon, y: lat };
261    let encoded_string = encode(neighbor_coord, hash_str.len())?;
262    GeoHash::try_from(encoded_string)
263}
264
265pub fn encode_max_precision(lon: f64, lat: f64) -> Result<GeoHash, GeohashError> {
266    let encoded_string = encode((lon, lat).into(), GeoHash::MAX_LEN)?;
267    GeoHash::try_from(encoded_string)
268}
269
270pub fn geo_hash_to_box(geo_hash: GeoHash) -> GeoBoundingBox {
271    let rectangle = decode_bbox(EcoString::from(geo_hash).as_str()).unwrap();
272    let top_left = GeoPoint {
273        lon: OrderedFloat(rectangle.min().x),
274        lat: OrderedFloat(rectangle.max().y),
275    };
276    let bottom_right = GeoPoint {
277        lon: OrderedFloat(rectangle.max().x),
278        lat: OrderedFloat(rectangle.min().y),
279    };
280
281    GeoBoundingBox {
282        top_left,
283        bottom_right,
284    }
285}
286
287#[derive(Debug)]
288struct GeohashBoundingBox {
289    north_west: GeoHash,
290    south_west: GeoHash,
291    #[cfg_attr(not(test), expect(dead_code))]
292    south_east: GeoHash, // field is not involved in the calculations, but is kept for symmetry
293    north_east: GeoHash,
294}
295
296impl GeohashBoundingBox {
297    /// Calculate geo-hashes covering the rectangular region with given precision
298    ///
299    /// # Arguments
300    ///
301    /// * `precision` - precision of cover
302    /// * `max_regions` - stop early if maximal amount of regions exceeded
303    ///
304    /// # Result
305    ///
306    /// * None - if there are more regions than a limit
307    /// * Some(list of geo-hashes covering the region
308    ///
309    fn geohash_regions(&self, precision: usize, max_regions: usize) -> Option<Vec<GeoHash>> {
310        let mut seen: Vec<GeoHash> = Vec::new();
311
312        let mut from_row: GeoHash = self.north_west.truncate(precision);
313        let mut to_row: GeoHash = self.north_east.truncate(precision);
314
315        let to_column = self.south_west.truncate(precision);
316
317        loop {
318            let mut current = from_row;
319            loop {
320                seen.push(current);
321
322                if seen.len() > max_regions {
323                    return None;
324                }
325
326                if current == to_row {
327                    break;
328                }
329                current = sphere_neighbor(current, Direction::E).unwrap();
330            }
331            if from_row == to_column {
332                break;
333            }
334
335            from_row = sphere_neighbor(from_row, Direction::S).unwrap();
336            to_row = sphere_neighbor(to_row, Direction::S).unwrap();
337        }
338
339        Some(seen)
340    }
341}
342
343impl From<GeoBoundingBox> for GeohashBoundingBox {
344    fn from(bounding_box: GeoBoundingBox) -> Self {
345        let GeoPoint {
346            lat: OrderedFloat(max_lat),
347            lon: OrderedFloat(min_lon),
348        } = bounding_box.top_left;
349        let GeoPoint {
350            lat: OrderedFloat(min_lat),
351            lon: OrderedFloat(max_lon),
352        } = bounding_box.bottom_right;
353
354        // Unwrap is acceptable, as data should be validated before
355        let north_west = encode_max_precision(min_lon, max_lat).unwrap();
356        let south_west = encode_max_precision(min_lon, min_lat).unwrap();
357        let south_east = encode_max_precision(max_lon, min_lat).unwrap();
358        let north_east = encode_max_precision(max_lon, max_lat).unwrap();
359
360        Self {
361            north_west,
362            south_west,
363            south_east,
364            north_east,
365        }
366    }
367}
368
369/// Check if geohash tile intersects the circle
370fn check_circle_intersection(geohash: &str, circle: &GeoRadius) -> bool {
371    let precision = geohash.len();
372    if precision == 0 {
373        return true;
374    }
375    let rect = decode_bbox(geohash).unwrap();
376    let c0 = rect.min();
377    let c1 = rect.max();
378
379    let bbox_center = Point::new((c0.x + c1.x) / 2f64, (c0.y + c1.y) / 2f64);
380    let half_diagonal = Haversine.distance(bbox_center, Point(c0));
381
382    half_diagonal + circle.radius.0
383        > Haversine.distance(
384            bbox_center,
385            Point::new(circle.center.lon.0, circle.center.lat.0),
386        )
387}
388
389/// Check if geohash tile intersects the polygon
390fn check_polygon_intersection(geohash: &str, polygon: &Polygon) -> bool {
391    let precision = geohash.len();
392    if precision == 0 {
393        return true;
394    }
395    let rect = decode_bbox(geohash).unwrap();
396
397    rect.intersects(polygon)
398}
399
400fn create_hashes(
401    mapping_fn: impl Fn(usize) -> Option<Vec<GeoHash>>,
402) -> OperationResult<Vec<GeoHash>> {
403    (0..=GeoHash::MAX_LEN)
404        .map(mapping_fn)
405        .take_while(|hashes| hashes.is_some())
406        .last()
407        .ok_or_else(|| OperationError::service_error("no hash coverage for any precision"))?
408        .ok_or_else(|| OperationError::service_error("geo-hash coverage is empty"))
409}
410
411/// Return as-high-as-possible with maximum of `max_regions`
412/// number of geo-hash guaranteed to contain the whole circle.
413pub fn circle_hashes(circle: &GeoRadius, max_regions: usize) -> OperationResult<Vec<GeoHash>> {
414    if max_regions == 0 {
415        return Err(OperationError::service_error(
416            "max_regions cannot be equal to zero",
417        ));
418    }
419
420    let geo_bounding_box = minimum_bounding_rectangle_for_circle(circle);
421    if geo_bounding_box.top_left.lat.is_nan()
422        || geo_bounding_box.top_left.lon.is_nan()
423        || geo_bounding_box.bottom_right.lat.is_nan()
424        || geo_bounding_box.bottom_right.lon.is_nan()
425    {
426        return Err(OperationError::service_error("Invalid circle"));
427    }
428    let full_geohash_bounding_box: GeohashBoundingBox = geo_bounding_box.into();
429
430    let mapping_fn = |precision| {
431        full_geohash_bounding_box
432            .geohash_regions(precision, max_regions)
433            .map(|hashes| {
434                hashes
435                    .into_iter()
436                    .filter(|hash| {
437                        check_circle_intersection(EcoString::from(*hash).as_str(), circle)
438                    })
439                    .collect_vec()
440            })
441    };
442    create_hashes(mapping_fn)
443}
444
445/// Return as-high-as-possible with maximum of `max_regions`
446/// number of geo-hash guaranteed to contain the whole rectangle.
447pub fn rectangle_hashes(
448    rectangle: &GeoBoundingBox,
449    max_regions: usize,
450) -> OperationResult<Vec<GeoHash>> {
451    if max_regions == 0 {
452        return Err(OperationError::service_error(
453            "max_regions cannot be equal to zero",
454        ));
455    }
456    let full_geohash_bounding_box: GeohashBoundingBox = (*rectangle).into();
457
458    let mapping_fn = |precision| full_geohash_bounding_box.geohash_regions(precision, max_regions);
459    create_hashes(mapping_fn)
460}
461
462/// Return as-high-as-possible with maximum of `max_regions`
463/// number of geo-hash guaranteed to contain a boundary defined by closed LineString.
464fn boundary_hashes(boundary: &LineString, max_regions: usize) -> OperationResult<Vec<GeoHash>> {
465    let geo_bounding_box = minimum_bounding_rectangle_for_boundary(boundary);
466    let full_geohash_bounding_box: GeohashBoundingBox = geo_bounding_box.into();
467    let polygon = Polygon::new(boundary.clone(), vec![]);
468
469    let mapping_fn = |precision| {
470        full_geohash_bounding_box
471            .geohash_regions(precision, max_regions)
472            .map(|hashes| {
473                hashes
474                    .into_iter()
475                    .filter(|hash| {
476                        check_polygon_intersection(EcoString::from(*hash).as_str(), &polygon)
477                    })
478                    .collect_vec()
479            })
480    };
481    create_hashes(mapping_fn)
482}
483
484/// A function used for cardinality estimation.
485///
486/// The first return value is as-high-as-possible with maximum of `max_regions`
487/// number of geo-hash guaranteed to contain the polygon's exterior.
488/// The second return value is all as-high-as-possible with maximum of `max_regions`
489/// number of geo-hash guaranteed to contain each polygon's interior.
490pub fn polygon_hashes_estimation(
491    polygon: &GeoPolygon,
492    max_regions: usize,
493) -> (Vec<GeoHash>, Vec<Vec<GeoHash>>) {
494    assert_ne!(max_regions, 0, "max_regions cannot be equal to zero");
495    let polygon_wrapper = polygon.convert().polygon;
496    let exterior_hashes = boundary_hashes(&polygon_wrapper.exterior().clone(), max_regions);
497    let interiors_hashes = polygon_wrapper
498        .interiors()
499        .iter()
500        .map(|interior| boundary_hashes(interior, max_regions).unwrap())
501        .collect_vec();
502
503    (exterior_hashes.unwrap(), interiors_hashes)
504}
505
506/// Return as-high-as-possible with maximum of `max_regions`
507/// number of geo-hash guaranteed to contain the whole polygon.
508pub fn polygon_hashes(polygon: &GeoPolygon, max_regions: usize) -> OperationResult<Vec<GeoHash>> {
509    if max_regions == 0 {
510        return Err(OperationError::service_error(
511            "max_regions cannot be equal to zero",
512        ));
513    }
514    let polygon_wrapper = polygon.convert().polygon;
515    let geo_bounding_box = minimum_bounding_rectangle_for_boundary(polygon_wrapper.exterior());
516    let full_geohash_bounding_box: GeohashBoundingBox = geo_bounding_box.into();
517
518    let mapping_fn = |precision| {
519        full_geohash_bounding_box
520            .geohash_regions(precision, max_regions)
521            .map(|hashes| {
522                hashes
523                    .into_iter()
524                    .filter(|hash| {
525                        check_polygon_intersection(
526                            EcoString::from(*hash).as_str(),
527                            &polygon_wrapper,
528                        )
529                    })
530                    .collect_vec()
531            })
532    };
533    create_hashes(mapping_fn)
534}
535
536/// A globally-average value is usually considered to be 6,371 kilometres (3,959 mi) with a 0.3% variability (±10 km).
537/// <https://en.wikipedia.org/wiki/Earth_radius>.
538const EARTH_RADIUS_METERS: f64 = 6371.0 * 1000.;
539
540/// Returns the GeoBoundingBox that defines the MBR
541/// <http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates#Longitude>
542fn minimum_bounding_rectangle_for_circle(circle: &GeoRadius) -> GeoBoundingBox {
543    // circle.radius is in meter
544    let angular_radius: f64 = circle.radius.0 / EARTH_RADIUS_METERS;
545
546    let angular_lat = circle.center.lat.to_radians();
547    let mut min_lat = (angular_lat - angular_radius).to_degrees();
548    let mut max_lat = (angular_lat + angular_radius).to_degrees();
549
550    let (min_lon, max_lon) = if LAT_RANGE.start < min_lat && max_lat < LAT_RANGE.end {
551        // Poles are not within the query, default scenario
552        let angular_lon = circle.center.lon.to_radians();
553        let delta_lon = (angular_radius.sin() / angular_lat.cos()).asin();
554
555        let min_lon = (angular_lon - delta_lon).to_degrees();
556        let max_lon = (angular_lon + delta_lon).to_degrees();
557
558        (min_lon, max_lon)
559    } else {
560        // poles are within circle - use whole cup
561        if LAT_RANGE.start > min_lat {
562            min_lat = LAT_RANGE.start + COORD_EPS;
563        }
564        if max_lat > LAT_RANGE.end {
565            max_lat = LAT_RANGE.end - COORD_EPS;
566        }
567
568        (LON_RANGE.start + COORD_EPS, LON_RANGE.end - COORD_EPS)
569    };
570
571    let top_left = GeoPoint {
572        lat: OrderedFloat(max_lat),
573        lon: OrderedFloat(sphere_lon(min_lon)),
574    };
575    let bottom_right = GeoPoint {
576        lat: OrderedFloat(min_lat),
577        lon: OrderedFloat(sphere_lon(max_lon)),
578    };
579
580    GeoBoundingBox {
581        top_left,
582        bottom_right,
583    }
584}
585
586fn minimum_bounding_rectangle_for_boundary(boundary: &LineString) -> GeoBoundingBox {
587    let mut min_lon = f64::MAX;
588    let mut max_lon = f64::MIN;
589    let mut min_lat = f64::MAX;
590    let mut max_lat = f64::MIN;
591
592    for point in boundary.coords() {
593        if point.x < min_lon {
594            min_lon = point.x;
595        }
596        if point.x > max_lon {
597            max_lon = point.x;
598        }
599        if point.y < min_lat {
600            min_lat = point.y;
601        }
602        if point.y > max_lat {
603            max_lat = point.y;
604        }
605    }
606
607    let top_left = GeoPoint {
608        lon: OrderedFloat(min_lon),
609        lat: OrderedFloat(max_lat),
610    };
611    let bottom_right = GeoPoint {
612        lon: OrderedFloat(max_lon),
613        lat: OrderedFloat(min_lat),
614    };
615
616    GeoBoundingBox {
617        top_left,
618        bottom_right,
619    }
620}
621
622#[cfg(test)]
623mod tests {
624    use rand::rngs::StdRng;
625    use rand::{RngExt, SeedableRng};
626
627    use super::*;
628    use crate::segment::types::CheckGeoPoint;
629    use crate::segment::types::test_utils::{build_polygon, build_polygon_with_interiors};
630
631    const BERLIN: GeoPoint = GeoPoint {
632        lat: OrderedFloat(52.52437),
633        lon: OrderedFloat(13.41053),
634    };
635
636    const NYC: GeoPoint = GeoPoint {
637        lat: OrderedFloat(40.75798),
638        lon: OrderedFloat(-73.991516),
639    };
640
641    #[test]
642    fn geohash_ordering() {
643        let mut v: Vec<&[u8]> = vec![
644            b"dr5ru",
645            b"uft56",
646            b"hhbcd",
647            b"uft560000000",
648            b"h",
649            b"hbcd",
650            b"887hh1234567",
651            b"",
652            b"hwx98",
653            b"hbc",
654            b"dr5rukz",
655        ];
656        let mut hashes = v.iter().map(|s| GeoHash::new(s).unwrap()).collect_vec();
657        hashes.sort_unstable();
658        v.sort_unstable();
659        for (a, b) in hashes.iter().zip(v) {
660            assert_eq!(a.to_string().as_bytes(), b);
661        }
662
663        // special case for hash which ends with 0
664        // "uft56" and "uft560000000" have the same encoded chars, but different length
665        assert_eq!(
666            GeoHash::new(b"uft5600")
667                .unwrap()
668                .cmp(&GeoHash::new(b"uft560000000").unwrap()),
669            "uft5600".cmp("uft560000000"),
670        );
671        assert_eq!(
672            GeoHash::new(b"")
673                .unwrap()
674                .cmp(&GeoHash::new(b"000000000000").unwrap()),
675            "".cmp("000000000000"),
676        );
677    }
678
679    #[test]
680    fn geohash_starts_with() {
681        let samples: [&[u8]; 6] = [
682            b"",
683            b"uft5601",
684            b"uft560100000",
685            b"uft56010000r",
686            b"uft5602",
687            b"uft560200000",
688        ];
689        for a in &samples {
690            let a_hash = GeoHash::new(a).unwrap();
691            for b in &samples {
692                let b_hash = GeoHash::new(b).unwrap();
693                if a.starts_with(b) {
694                    assert!(
695                        a_hash.starts_with(b_hash),
696                        "{a:?} expected to start with {b:?}",
697                    );
698                } else {
699                    assert!(
700                        !a_hash.starts_with(b_hash),
701                        "{a:?} expected to not start with {b:?}",
702                    );
703                }
704            }
705        }
706    }
707
708    #[test]
709    #[expect(clippy::unusual_byte_groupings)]
710    fn geohash_normalize() {
711        let valid_samples: [&[u8]; _] = [
712            b"dr5ru",
713            b"uft56",
714            b"hhbcd",
715            b"uft560000000",
716            b"h",
717            b"hbcd",
718            b"887hh1234567",
719            b"",
720            b"hwx98",
721            b"hbc",
722            b"dr5rukz",
723        ];
724        // Normalization should not change valid hashes
725        for s in valid_samples {
726            let hash = GeoHash::new(s).unwrap();
727            assert_eq!(hash, GeoHashRaw::from(hash).normalize());
728        }
729
730        let raw = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__0011;
731        let fxd = 0b_00001_00010_00011_00000_00000_00000_00000_00000_00000_00000_00000_00000__0011;
732        // Zero-fill unused chars:     ^^^^^ ^^^^^ ^^^^^^^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
733        assert_eq!(GeoHashRaw(raw).normalize().0, fxd);
734
735        let raw = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__1111;
736        let fxd = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__1100;
737        // Truncate length:                                                                   ^^^^
738        assert_eq!(GeoHashRaw(raw).normalize().0, fxd);
739    }
740
741    #[test]
742    fn geohash_encode_longitude_first() {
743        let center_hash = GeoHash::new(encode(Coord::from(NYC), GeoHash::MAX_LEN).unwrap());
744        assert_eq!(center_hash.ok(), GeoHash::new(b"dr5ru7c02wnv").ok());
745        let center_hash = GeoHash::new(encode(Coord::from(NYC), 6).unwrap());
746        assert_eq!(center_hash.ok(), GeoHash::new(b"dr5ru7").ok());
747        let center_hash = GeoHash::new(encode(Coord::from(BERLIN), GeoHash::MAX_LEN).unwrap());
748        assert_eq!(center_hash.ok(), GeoHash::new(b"u33dc1v0xupz").ok());
749        let center_hash = GeoHash::new(encode(Coord::from(BERLIN), 6).unwrap());
750        assert_eq!(center_hash.ok(), GeoHash::new(b"u33dc1").ok());
751    }
752
753    #[test]
754    fn rectangle_geo_hash_nyc() {
755        // data from https://www.titanwolf.org/Network/q/a98ba365-14c5-48f4-8839-86a0962e0ab9/y
756        let near_nyc_circle = GeoRadius {
757            center: NYC,
758            radius: OrderedFloat(800.0),
759        };
760
761        let bounding_box = minimum_bounding_rectangle_for_circle(&near_nyc_circle);
762        let rectangle: GeohashBoundingBox = bounding_box.into();
763        assert_eq!(rectangle.north_west, GeoHash::new(b"dr5ruj4477kd").unwrap());
764        assert_eq!(rectangle.south_west, GeoHash::new(b"dr5ru46ne2ux").unwrap());
765        assert_eq!(rectangle.south_east, GeoHash::new(b"dr5ru6ryw0cp").unwrap());
766        assert_eq!(rectangle.north_east, GeoHash::new(b"dr5rumpfq534").unwrap());
767    }
768
769    #[test]
770    fn top_level_rectangle_geo_area() {
771        let rect = GeohashBoundingBox {
772            north_west: GeoHash::new(b"u").unwrap(),
773            south_west: GeoHash::new(b"s").unwrap(),
774            south_east: GeoHash::new(b"t").unwrap(),
775            north_east: GeoHash::new(b"v").unwrap(),
776        };
777        let mut geo_area = rect.geohash_regions(1, 100).unwrap();
778        let mut expected = vec![
779            GeoHash::new(b"u").unwrap(),
780            GeoHash::new(b"s").unwrap(),
781            GeoHash::new(b"v").unwrap(),
782            GeoHash::new(b"t").unwrap(),
783        ];
784
785        geo_area.sort_unstable();
786        expected.sort_unstable();
787        assert_eq!(geo_area, expected);
788    }
789
790    #[test]
791    fn nyc_rectangle_geo_area_high_precision() {
792        let rect = GeohashBoundingBox {
793            north_west: GeoHash::new(b"dr5ruj4477kd").unwrap(),
794            south_west: GeoHash::new(b"dr5ru46ne2ux").unwrap(),
795            south_east: GeoHash::new(b"dr5ru6ryw0cp").unwrap(),
796            north_east: GeoHash::new(b"dr5rumpfq534").unwrap(),
797        };
798
799        // calling `rect.geohash_regions()` is too expensive
800        assert!(rect.geohash_regions(12, 100).is_none());
801    }
802
803    #[test]
804    fn nyc_rectangle_geo_area_medium_precision() {
805        let rect = GeohashBoundingBox {
806            north_west: GeoHash::new(b"dr5ruj4").unwrap(),
807            south_west: GeoHash::new(b"dr5ru46").unwrap(),
808            south_east: GeoHash::new(b"dr5ru6r").unwrap(),
809            north_east: GeoHash::new(b"dr5rump").unwrap(),
810        };
811
812        let geo_area = rect.geohash_regions(7, 1000).unwrap();
813        assert_eq!(14 * 12, geo_area.len());
814    }
815
816    #[test]
817    fn nyc_rectangle_geo_area_low_precision() {
818        let rect = GeohashBoundingBox {
819            north_west: GeoHash::new(b"dr5ruj").unwrap(),
820            south_west: GeoHash::new(b"dr5ru4").unwrap(),
821            south_east: GeoHash::new(b"dr5ru6").unwrap(),
822            north_east: GeoHash::new(b"dr5rum").unwrap(),
823        };
824
825        let mut geo_area = rect.geohash_regions(6, 100).unwrap();
826        let mut expected = vec![
827            GeoHash::new(b"dr5ru4").unwrap(),
828            GeoHash::new(b"dr5ru5").unwrap(),
829            GeoHash::new(b"dr5ru6").unwrap(),
830            GeoHash::new(b"dr5ru7").unwrap(),
831            GeoHash::new(b"dr5ruh").unwrap(),
832            GeoHash::new(b"dr5ruj").unwrap(),
833            GeoHash::new(b"dr5rum").unwrap(),
834            GeoHash::new(b"dr5ruk").unwrap(),
835        ];
836
837        expected.sort_unstable();
838        geo_area.sort_unstable();
839        assert_eq!(geo_area, expected);
840    }
841
842    #[test]
843    fn rectangle_hashes_nyc() {
844        // conversion to lon/lat http://geohash.co/
845        // "dr5ruj4477kd"
846        let top_left = GeoPoint {
847            lon: OrderedFloat(-74.00101399),
848            lat: OrderedFloat(40.76517460),
849        };
850
851        // "dr5ru6ryw0cp"
852        let bottom_right = GeoPoint {
853            lon: OrderedFloat(-73.98201792),
854            lat: OrderedFloat(40.75078539),
855        };
856
857        let near_nyc_rectangle = GeoBoundingBox {
858            top_left,
859            bottom_right,
860        };
861
862        let nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 200);
863        let nyc_hashes = nyc_hashes_result.unwrap();
864        assert_eq!(nyc_hashes.len(), 168);
865        assert!(nyc_hashes.iter().all(|h| h.len() == 7)); // geohash precision
866
867        let mut nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 10);
868        nyc_hashes_result.as_mut().unwrap().sort_unstable();
869        let mut expected = vec![
870            GeoHash::new(b"dr5ruj").unwrap(),
871            GeoHash::new(b"dr5ruh").unwrap(),
872            GeoHash::new(b"dr5ru5").unwrap(),
873            GeoHash::new(b"dr5ru4").unwrap(),
874            GeoHash::new(b"dr5rum").unwrap(),
875            GeoHash::new(b"dr5ruk").unwrap(),
876            GeoHash::new(b"dr5ru7").unwrap(),
877            GeoHash::new(b"dr5ru6").unwrap(),
878        ];
879        expected.sort_unstable();
880
881        assert_eq!(nyc_hashes_result.unwrap(), expected);
882
883        // Graphical proof using https://www.movable-type.co.uk/scripts/geohash.html
884
885        // dr5rgy dr5run dr5ruq dr5ruw
886        // dr5rgv dr5ruj dr5rum dr5rut
887        // dr5rgu dr5ruh dr5ruk dr5rus
888        // dr5rgg dr5ru5 dr5ru7 dr5rue
889        // dr5rgf dr5ru4 dr5ru6 dr5rud
890        // dr5rgc dr5ru1 dr5ru3 dr5ru9
891
892        // XXXXXX XXXXXX XXXXXX XXXXXX
893        // XXXXXX dr5ruj dr5rum XXXXXX
894        // XXXXXX dr5ruh dr5ruk XXXXXX
895        // XXXXXX dr5ru5 dr5ru7 XXXXXX
896        // XXXXXX dr5ru4 Xr5ru6 XXXXXX
897        // XXXXXX XXXXXX XXXXXX XXXXXX
898
899        // falls back to finest region that encompasses the whole area
900        let nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 7);
901        assert_eq!(
902            nyc_hashes_result.unwrap(),
903            [GeoHash::new(b"dr5ru").unwrap()],
904        );
905    }
906
907    #[test]
908    fn rectangle_hashes_crossing_antimeridian() {
909        // conversion to lon/lat http://geohash.co/
910        // "ztnv2hjxn03k"
911        let top_left = GeoPoint {
912            lat: OrderedFloat(74.071028),
913            lon: OrderedFloat(167.0),
914        };
915
916        // "dr5ru7c02wnv"
917        let bottom_right = GeoPoint {
918            lat: OrderedFloat(40.75798),
919            lon: OrderedFloat(-73.991516),
920        };
921
922        let crossing_usa_rectangle = GeoBoundingBox {
923            top_left,
924            bottom_right,
925        };
926
927        let usa_hashes_result = rectangle_hashes(&crossing_usa_rectangle, 200);
928        let usa_hashes = usa_hashes_result.unwrap();
929        assert_eq!(usa_hashes.len(), 84);
930        assert!(usa_hashes.iter().all(|h| h.len() == 2)); // low geohash precision
931
932        let mut usa_hashes_result = rectangle_hashes(&crossing_usa_rectangle, 10);
933        usa_hashes_result.as_mut().unwrap().sort_unstable();
934        let mut expected = vec![
935            GeoHash::new(b"8").unwrap(),
936            GeoHash::new(b"9").unwrap(),
937            GeoHash::new(b"b").unwrap(),
938            GeoHash::new(b"c").unwrap(),
939            GeoHash::new(b"d").unwrap(),
940            GeoHash::new(b"f").unwrap(),
941            GeoHash::new(b"x").unwrap(),
942            GeoHash::new(b"z").unwrap(),
943        ];
944        expected.sort_unstable();
945
946        assert_eq!(usa_hashes_result.unwrap(), expected);
947
948        // Graphical proof using https://www.movable-type.co.uk/scripts/geohash.html
949
950        // n p 0 1 4 5
951        // y z b c f g
952        // w x 8 9 d e
953        // q r 2 3 6 7
954
955        // - - - - - -
956        // | z b c f |
957        // | x 8 9 d |
958        // - - - - - -
959    }
960
961    #[test]
962    fn polygon_hashes_nyc() {
963        // conversion to lon/lat http://geohash.co/
964        // "dr5ruj4477kd"
965        let near_nyc_polygon = build_polygon(vec![
966            (-74.00101399, 40.76517460),
967            (-73.98201792, 40.76517460),
968            (-73.98201792, 40.75078539),
969            (-74.00101399, 40.75078539),
970            (-74.00101399, 40.76517460),
971        ]);
972
973        let nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 200);
974        let nyc_hashes = nyc_hashes_result.unwrap();
975        assert_eq!(nyc_hashes.len(), 168);
976        assert!(nyc_hashes.iter().all(|h| h.len() == 7)); // geohash precision
977
978        let mut nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 10);
979        nyc_hashes_result.as_mut().unwrap().sort_unstable();
980        let mut expected = vec![
981            GeoHash::new(b"dr5ruj").unwrap(),
982            GeoHash::new(b"dr5ruh").unwrap(),
983            GeoHash::new(b"dr5ru5").unwrap(),
984            GeoHash::new(b"dr5ru4").unwrap(),
985            GeoHash::new(b"dr5rum").unwrap(),
986            GeoHash::new(b"dr5ruk").unwrap(),
987            GeoHash::new(b"dr5ru7").unwrap(),
988            GeoHash::new(b"dr5ru6").unwrap(),
989        ];
990        expected.sort_unstable();
991
992        assert_eq!(nyc_hashes_result.unwrap(), expected);
993
994        // falls back to finest region that encompasses the whole area
995        let nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 7);
996        assert_eq!(
997            nyc_hashes_result.unwrap(),
998            [GeoHash::new(b"dr5ru").unwrap()],
999        );
1000    }
1001
1002    #[test]
1003    fn random_circles() {
1004        let mut rnd = StdRng::seed_from_u64(42);
1005        for _ in 0..1000 {
1006            let r_meters = rnd.random_range(1.0..10000.0);
1007            let query = GeoRadius {
1008                center: GeoPoint::new_unchecked(
1009                    rnd.random_range(LON_RANGE),
1010                    rnd.random_range(LAT_RANGE),
1011                ),
1012                radius: OrderedFloat(r_meters),
1013            };
1014            let max_hashes = rnd.random_range(1..32);
1015            let hashes = circle_hashes(&query, max_hashes);
1016            assert!(hashes.unwrap().len() <= max_hashes);
1017        }
1018    }
1019
1020    #[test]
1021    fn test_check_polygon_intersection() {
1022        fn check_intersection(geohash: &str, polygon: &GeoPolygon, expected: bool) {
1023            let intersect = check_polygon_intersection(geohash, &polygon.convert().polygon);
1024            assert_eq!(intersect, expected);
1025        }
1026
1027        // Create a geohash as (-56.2, 33.75), (-56.2, 39.375), (-45, 39.375), (-45, 33.75)
1028        let geohash = encode(Coord { x: -50.0, y: 35.0 }, 2).unwrap();
1029
1030        // Test a polygon intersect with the geohash
1031        check_intersection(
1032            &geohash,
1033            &build_polygon(vec![
1034                (-60.0, 37.0),
1035                (-60.0, 45.0),
1036                (-50.0, 45.0),
1037                (-50.0, 37.0),
1038                (-60.0, 37.0),
1039            ]),
1040            true,
1041        );
1042
1043        // Test a polygon does not intersect with the geohash
1044        check_intersection(
1045            &geohash,
1046            &build_polygon(vec![
1047                (-70.2, 50.8),
1048                (-70.2, 55.9),
1049                (-65.6, 55.9),
1050                (-65.6, 50.8),
1051                (-70.2, 50.8),
1052            ]),
1053            false,
1054        );
1055
1056        // Test a polygon that overlap with the geohash
1057        check_intersection(
1058            &geohash,
1059            &build_polygon(vec![
1060                (-56.2, 33.75),
1061                (-56.2, 39.375),
1062                (-45.0, 39.375),
1063                (-45.0, 33.75),
1064                (-56.2, 33.75),
1065            ]),
1066            true,
1067        );
1068
1069        // Test a polygon that only share one edge with the geohash
1070        check_intersection(
1071            &geohash,
1072            &build_polygon(vec![
1073                (-45.0, 39.375),
1074                (-45.0, 45.0),
1075                (-30.9, 45.0),
1076                (-30.9, 39.375),
1077                (-45.0, 39.375),
1078            ]),
1079            true,
1080        );
1081
1082        // Test a polygon that is within the geohash
1083        check_intersection(
1084            &geohash,
1085            &build_polygon(vec![
1086                (-55.7, 34.3),
1087                (-55.7, 38.0),
1088                (-46.8, 38.0),
1089                (-46.8, 34.3),
1090                (-55.7, 34.3),
1091            ]),
1092            true,
1093        );
1094
1095        // Test a polygon that contains the geohash
1096        check_intersection(
1097            &geohash,
1098            &build_polygon(vec![
1099                (-60.0, 33.0),
1100                (-60.0, 40.0),
1101                (-44.0, 40.0),
1102                (-44.0, 33.0),
1103                (-60.0, 33.0),
1104            ]),
1105            true,
1106        );
1107
1108        // The geohash is in the exterior of the polygon
1109        check_intersection(
1110            &geohash,
1111            &build_polygon_with_interiors(
1112                vec![
1113                    (-70.0, 13.0),
1114                    (-70.0, 50.0),
1115                    (-34.0, 50.0),
1116                    (-34.0, 13.0),
1117                    (-70.0, 13.0),
1118                ],
1119                vec![vec![
1120                    (-60.0, 33.0),
1121                    (-60.0, 40.0),
1122                    (-44.0, 40.0),
1123                    (-44.0, 33.0),
1124                    (-60.0, 33.0),
1125                ]],
1126            ),
1127            false,
1128        );
1129    }
1130
1131    #[test]
1132    fn test_lon_threshold() {
1133        let query = GeoRadius {
1134            center: GeoPoint {
1135                lon: OrderedFloat(179.987181),
1136                lat: OrderedFloat(44.9811609411936),
1137            },
1138            radius: OrderedFloat(100000.),
1139        };
1140
1141        let max_hashes = 10;
1142        let hashes = circle_hashes(&query, max_hashes);
1143        assert_eq!(
1144            hashes.unwrap(),
1145            vec![
1146                GeoHash::new(b"zbp").unwrap(),
1147                GeoHash::new(b"b00").unwrap(),
1148                GeoHash::new(b"xzz").unwrap(),
1149                GeoHash::new(b"8pb").unwrap(),
1150            ],
1151        );
1152    }
1153
1154    #[test]
1155    fn wide_circle_meridian() {
1156        let query = GeoRadius {
1157            center: GeoPoint {
1158                lon: OrderedFloat(-17.81718188959701),
1159                lat: OrderedFloat(89.9811609411936),
1160            },
1161            radius: OrderedFloat(9199.481636468849),
1162        };
1163
1164        let max_hashes = 10;
1165        let hashes = circle_hashes(&query, max_hashes);
1166        let vec = hashes.unwrap();
1167        assert!(vec.len() <= max_hashes);
1168        assert_eq!(
1169            vec,
1170            [
1171                GeoHash::new(b"b").unwrap(),
1172                GeoHash::new(b"c").unwrap(),
1173                GeoHash::new(b"f").unwrap(),
1174                GeoHash::new(b"g").unwrap(),
1175                GeoHash::new(b"u").unwrap(),
1176                GeoHash::new(b"v").unwrap(),
1177                GeoHash::new(b"y").unwrap(),
1178                GeoHash::new(b"z").unwrap(),
1179            ],
1180        );
1181    }
1182
1183    #[test]
1184    fn tight_circle_meridian() {
1185        let query = GeoRadius {
1186            center: GeoPoint {
1187                lon: OrderedFloat(-17.81718188959701),
1188                lat: OrderedFloat(89.9811609411936),
1189            },
1190            radius: OrderedFloat(1000.0),
1191        };
1192
1193        let max_hashes = 10;
1194        let hashes_result = circle_hashes(&query, max_hashes);
1195        let hashes = hashes_result.unwrap();
1196        assert!(hashes.len() <= max_hashes);
1197        assert_eq!(
1198            hashes,
1199            [
1200                GeoHash::new(b"fz").unwrap(),
1201                GeoHash::new(b"gp").unwrap(),
1202                GeoHash::new(b"gr").unwrap(),
1203                GeoHash::new(b"gx").unwrap(),
1204                GeoHash::new(b"gz").unwrap(),
1205                GeoHash::new(b"up").unwrap(),
1206            ],
1207        );
1208    }
1209
1210    #[test]
1211    fn wide_circle_south_pole() {
1212        let query = GeoRadius {
1213            center: GeoPoint {
1214                lon: OrderedFloat(155.85591760141335),
1215                lat: OrderedFloat(-74.19418872656166),
1216            },
1217            radius: OrderedFloat(7133.775526733084),
1218        };
1219        let max_hashes = 10;
1220        let hashes_result = circle_hashes(&query, max_hashes);
1221        let hashes = hashes_result.unwrap();
1222        assert!(hashes.len() <= max_hashes);
1223        assert_eq!(
1224            hashes,
1225            [
1226                GeoHash::new(b"p6yd").unwrap(),
1227                GeoHash::new(b"p6yf").unwrap(),
1228                GeoHash::new(b"p6y9").unwrap(),
1229                GeoHash::new(b"p6yc").unwrap(),
1230            ],
1231        );
1232    }
1233
1234    #[test]
1235    fn tight_circle_south_pole() {
1236        let query = GeoRadius {
1237            center: GeoPoint {
1238                lon: OrderedFloat(155.85591760141335),
1239                lat: OrderedFloat(-74.19418872656166),
1240            },
1241            radius: OrderedFloat(1000.0),
1242        };
1243        let max_hashes = 10;
1244        let hashes_result = circle_hashes(&query, max_hashes);
1245        let hashes = hashes_result.unwrap();
1246        assert!(hashes.len() <= max_hashes);
1247        assert_eq!(
1248            hashes,
1249            [
1250                GeoHash::new(b"p6ycc").unwrap(),
1251                GeoHash::new(b"p6ycf").unwrap(),
1252                GeoHash::new(b"p6ycg").unwrap(),
1253            ],
1254        );
1255    }
1256
1257    #[test]
1258    fn circle_hashes_nyc() {
1259        let near_nyc_circle = GeoRadius {
1260            center: NYC,
1261            radius: OrderedFloat(800.0),
1262        };
1263
1264        let nyc_hashes_result = circle_hashes(&near_nyc_circle, 200).unwrap();
1265        assert!(nyc_hashes_result.iter().all(|h| h.len() == 7)); // geohash precision
1266
1267        let mut nyc_hashes_result = circle_hashes(&near_nyc_circle, 10);
1268        nyc_hashes_result.as_mut().unwrap().sort_unstable();
1269        let mut expected = [
1270            GeoHash::new(b"dr5ruj").unwrap(),
1271            GeoHash::new(b"dr5ruh").unwrap(),
1272            GeoHash::new(b"dr5ru5").unwrap(),
1273            GeoHash::new(b"dr5ru4").unwrap(),
1274            GeoHash::new(b"dr5rum").unwrap(),
1275            GeoHash::new(b"dr5ruk").unwrap(),
1276            GeoHash::new(b"dr5ru7").unwrap(),
1277            GeoHash::new(b"dr5ru6").unwrap(),
1278        ];
1279        expected.sort_unstable();
1280        assert_eq!(nyc_hashes_result.unwrap(), expected);
1281
1282        // falls back to finest region that encompasses the whole area
1283        let nyc_hashes_result = circle_hashes(&near_nyc_circle, 7);
1284        assert_eq!(
1285            nyc_hashes_result.unwrap(),
1286            [GeoHash::new(b"dr5ru").unwrap()],
1287        );
1288    }
1289
1290    #[test]
1291    fn go_north() {
1292        let mut geohash = sphere_neighbor(GeoHash::new(b"ww8p").unwrap(), Direction::N).unwrap();
1293        for _ in 0..1000 {
1294            geohash = sphere_neighbor(geohash, Direction::N).unwrap();
1295        }
1296    }
1297
1298    #[test]
1299    fn go_west() {
1300        let starting_hash = GeoHash::new(b"ww8").unwrap();
1301        let mut geohash = sphere_neighbor(starting_hash, Direction::W).unwrap();
1302        let mut is_earth_round = false;
1303        for _ in 0..1000 {
1304            geohash = sphere_neighbor(geohash, Direction::W).unwrap();
1305            if geohash == starting_hash {
1306                is_earth_round = true;
1307            }
1308        }
1309        assert!(is_earth_round)
1310    }
1311
1312    #[test]
1313    fn sphere_neighbor_corner_cases() {
1314        assert_eq!(
1315            &EcoString::from(sphere_neighbor(GeoHash::new(b"z").unwrap(), Direction::NE).unwrap()),
1316            "b",
1317        );
1318        assert_eq!(
1319            &EcoString::from(sphere_neighbor(GeoHash::new(b"zz").unwrap(), Direction::NE).unwrap()),
1320            "bp",
1321        );
1322        assert_eq!(
1323            &EcoString::from(sphere_neighbor(GeoHash::new(b"0").unwrap(), Direction::SW).unwrap()),
1324            "p",
1325        );
1326        assert_eq!(
1327            &EcoString::from(sphere_neighbor(GeoHash::new(b"00").unwrap(), Direction::SW).unwrap()),
1328            "pb",
1329        );
1330
1331        assert_eq!(
1332            &EcoString::from(sphere_neighbor(GeoHash::new(b"8").unwrap(), Direction::W).unwrap()),
1333            "x",
1334        );
1335        assert_eq!(
1336            &EcoString::from(sphere_neighbor(GeoHash::new(b"8h").unwrap(), Direction::W).unwrap()),
1337            "xu",
1338        );
1339        assert_eq!(
1340            &EcoString::from(sphere_neighbor(GeoHash::new(b"r").unwrap(), Direction::E).unwrap()),
1341            "2",
1342        );
1343        assert_eq!(
1344            &EcoString::from(sphere_neighbor(GeoHash::new(b"ru").unwrap(), Direction::E).unwrap()),
1345            "2h",
1346        );
1347
1348        assert_eq!(
1349            EcoString::from(
1350                sphere_neighbor(GeoHash::new(b"ww8p1r4t8").unwrap(), Direction::SE).unwrap()
1351            ),
1352            EcoString::from(&geohash::neighbor("ww8p1r4t8", Direction::SE).unwrap()),
1353        );
1354    }
1355
1356    #[test]
1357    fn long_overflow_distance() {
1358        let dist = Haversine.distance(Point::new(-179.999, 66.0), Point::new(179.999, 66.0));
1359        eprintln!("dist` = {dist:#?}");
1360        assert_eq!(dist, 90.45422731917998);
1361        let dist = Haversine.distance(Point::new(0.99, 90.), Point::new(0.99, -90.0));
1362        assert_eq!(dist, 20015114.442035925);
1363    }
1364
1365    #[test]
1366    fn turn_geo_hash_to_box() {
1367        let geo_box = geo_hash_to_box(GeoHash::new(b"dr5ruj4477kd").unwrap());
1368        let center = GeoPoint {
1369            lat: OrderedFloat(40.76517460),
1370            lon: OrderedFloat(-74.00101399),
1371        };
1372        assert!(geo_box.check_point(&center));
1373    }
1374
1375    #[test]
1376    fn common_prefix() {
1377        let geo_hashes = vec![
1378            GeoHash::new(b"zbcd123").unwrap(),
1379            GeoHash::new(b"zbcd2233").unwrap(),
1380            GeoHash::new(b"zbcd3213").unwrap(),
1381            GeoHash::new(b"zbcd533").unwrap(),
1382        ];
1383
1384        let common_prefix = common_hash_prefix(&geo_hashes).unwrap();
1385        println!("common_prefix = {:?}", EcoString::from(common_prefix));
1386
1387        //assert_eq!(common_prefix, GeoHash::new("zbcd").unwrap());
1388
1389        let geo_hashes = vec![
1390            GeoHash::new(b"zbcd123").unwrap(),
1391            GeoHash::new(b"bbcd2233").unwrap(),
1392            GeoHash::new(b"cbcd3213").unwrap(),
1393            GeoHash::new(b"dbcd533").unwrap(),
1394        ];
1395
1396        let common_prefix = common_hash_prefix(&geo_hashes).unwrap();
1397        println!("common_prefix = {:?}", EcoString::from(common_prefix));
1398
1399        assert_eq!(common_prefix, GeoHash::new(b"").unwrap());
1400    }
1401
1402    #[test]
1403    fn max_regions_cannot_be_equal_to_zero() {
1404        let invalid_max_hashes = 0;
1405
1406        // circle
1407        let sample_circle = GeoRadius {
1408            center: GeoPoint {
1409                lon: OrderedFloat(179.987181),
1410                lat: OrderedFloat(44.9811609411936),
1411            },
1412            radius: OrderedFloat(100000.),
1413        };
1414        let circle_hashes = circle_hashes(&sample_circle, invalid_max_hashes);
1415        assert!(circle_hashes.is_err());
1416
1417        // rectangle
1418        let top_left = GeoPoint {
1419            lon: OrderedFloat(-74.00101399),
1420            lat: OrderedFloat(40.76517460),
1421        };
1422
1423        let bottom_right = GeoPoint {
1424            lon: OrderedFloat(-73.98201792),
1425            lat: OrderedFloat(40.75078539),
1426        };
1427
1428        let sample_rectangle = GeoBoundingBox {
1429            top_left,
1430            bottom_right,
1431        };
1432        let rectangle_hashes = rectangle_hashes(&sample_rectangle, invalid_max_hashes);
1433        assert!(rectangle_hashes.is_err());
1434
1435        // polygon
1436        let sample_polygon = build_polygon(vec![
1437            (-74.00101399, 40.76517460),
1438            (-73.98201792, 40.75078539),
1439        ]);
1440
1441        let polygon_hashes = polygon_hashes(&sample_polygon, invalid_max_hashes);
1442        assert!(polygon_hashes.is_err());
1443    }
1444
1445    #[test]
1446    fn geo_radius_zero_division() {
1447        let circle = GeoRadius {
1448            center: GeoPoint {
1449                lon: OrderedFloat(45.0),
1450                lat: OrderedFloat(80.0),
1451            },
1452            radius: OrderedFloat(1000.0),
1453        };
1454        let hashes = circle_hashes(&circle, GeoHash::MAX_LEN);
1455        assert!(hashes.is_ok());
1456
1457        let circle2 = GeoRadius {
1458            center: GeoPoint {
1459                lon: OrderedFloat(45.0),
1460                lat: OrderedFloat(90.0),
1461            },
1462            radius: OrderedFloat(-1.0),
1463        };
1464        let hashes2 = circle_hashes(&circle2, GeoHash::MAX_LEN);
1465        assert!(hashes2.is_err());
1466    }
1467}
qdrant_edge/segment/index/field_index/geo_hash.rs

qdrant_edge/segment/index/field_index/
geo_hash.rs
