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_LENGTH`] = 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_LENGTH`,
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    #[allow(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::test_utils::{build_polygon, build_polygon_with_interiors};
629
630    const BERLIN: GeoPoint = GeoPoint {
631        lat: OrderedFloat(52.52437),
632        lon: OrderedFloat(13.41053),
633    };
634
635    const NYC: GeoPoint = GeoPoint {
636        lat: OrderedFloat(40.75798),
637        lon: OrderedFloat(-73.991516),
638    };
639
640    #[test]
641    fn geohash_ordering() {
642        let mut v: Vec<&[u8]> = vec![
643            b"dr5ru",
644            b"uft56",
645            b"hhbcd",
646            b"uft560000000",
647            b"h",
648            b"hbcd",
649            b"887hh1234567",
650            b"",
651            b"hwx98",
652            b"hbc",
653            b"dr5rukz",
654        ];
655        let mut hashes = v.iter().map(|s| GeoHash::new(s).unwrap()).collect_vec();
656        hashes.sort_unstable();
657        v.sort_unstable();
658        for (a, b) in hashes.iter().zip(v) {
659            assert_eq!(a.to_string().as_bytes(), b);
660        }
661
662        // special case for hash which ends with 0
663        // "uft56" and "uft560000000" have the same encoded chars, but different length
664        assert_eq!(
665            GeoHash::new(b"uft5600")
666                .unwrap()
667                .cmp(&GeoHash::new(b"uft560000000").unwrap()),
668            "uft5600".cmp("uft560000000"),
669        );
670        assert_eq!(
671            GeoHash::new(b"")
672                .unwrap()
673                .cmp(&GeoHash::new(b"000000000000").unwrap()),
674            "".cmp("000000000000"),
675        );
676    }
677
678    #[test]
679    fn geohash_starts_with() {
680        let samples: [&[u8]; 6] = [
681            b"",
682            b"uft5601",
683            b"uft560100000",
684            b"uft56010000r",
685            b"uft5602",
686            b"uft560200000",
687        ];
688        for a in &samples {
689            let a_hash = GeoHash::new(a).unwrap();
690            for b in &samples {
691                let b_hash = GeoHash::new(b).unwrap();
692                if a.starts_with(b) {
693                    assert!(
694                        a_hash.starts_with(b_hash),
695                        "{a:?} expected to start with {b:?}",
696                    );
697                } else {
698                    assert!(
699                        !a_hash.starts_with(b_hash),
700                        "{a:?} expected to not start with {b:?}",
701                    );
702                }
703            }
704        }
705    }
706
707    #[test]
708    #[expect(clippy::unusual_byte_groupings)]
709    fn geohash_normalize() {
710        let valid_samples: [&[u8]; _] = [
711            b"dr5ru",
712            b"uft56",
713            b"hhbcd",
714            b"uft560000000",
715            b"h",
716            b"hbcd",
717            b"887hh1234567",
718            b"",
719            b"hwx98",
720            b"hbc",
721            b"dr5rukz",
722        ];
723        // Normalization should not change valid hashes
724        for s in valid_samples {
725            let hash = GeoHash::new(s).unwrap();
726            assert_eq!(hash, GeoHashRaw::from(hash).normalize());
727        }
728
729        let raw = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__0011;
730        let fxd = 0b_00001_00010_00011_00000_00000_00000_00000_00000_00000_00000_00000_00000__0011;
731        // Zero-fill unused chars:     ^^^^^ ^^^^^ ^^^^^^^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
732        assert_eq!(GeoHashRaw(raw).normalize().0, fxd);
733
734        let raw = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__1111;
735        let fxd = 0b_00001_00010_00011_00100_00101_00110_00111_01000_01001_01010_01100_01101__1100;
736        // Truncate length:                                                                   ^^^^
737        assert_eq!(GeoHashRaw(raw).normalize().0, fxd);
738    }
739
740    #[test]
741    fn geohash_encode_longitude_first() {
742        let center_hash = GeoHash::new(encode(Coord::from(NYC), GeoHash::MAX_LEN).unwrap());
743        assert_eq!(center_hash.ok(), GeoHash::new(b"dr5ru7c02wnv").ok());
744        let center_hash = GeoHash::new(encode(Coord::from(NYC), 6).unwrap());
745        assert_eq!(center_hash.ok(), GeoHash::new(b"dr5ru7").ok());
746        let center_hash = GeoHash::new(encode(Coord::from(BERLIN), GeoHash::MAX_LEN).unwrap());
747        assert_eq!(center_hash.ok(), GeoHash::new(b"u33dc1v0xupz").ok());
748        let center_hash = GeoHash::new(encode(Coord::from(BERLIN), 6).unwrap());
749        assert_eq!(center_hash.ok(), GeoHash::new(b"u33dc1").ok());
750    }
751
752    #[test]
753    fn rectangle_geo_hash_nyc() {
754        // data from https://www.titanwolf.org/Network/q/a98ba365-14c5-48f4-8839-86a0962e0ab9/y
755        let near_nyc_circle = GeoRadius {
756            center: NYC,
757            radius: OrderedFloat(800.0),
758        };
759
760        let bounding_box = minimum_bounding_rectangle_for_circle(&near_nyc_circle);
761        let rectangle: GeohashBoundingBox = bounding_box.into();
762        assert_eq!(rectangle.north_west, GeoHash::new(b"dr5ruj4477kd").unwrap());
763        assert_eq!(rectangle.south_west, GeoHash::new(b"dr5ru46ne2ux").unwrap());
764        assert_eq!(rectangle.south_east, GeoHash::new(b"dr5ru6ryw0cp").unwrap());
765        assert_eq!(rectangle.north_east, GeoHash::new(b"dr5rumpfq534").unwrap());
766    }
767
768    #[test]
769    fn top_level_rectangle_geo_area() {
770        let rect = GeohashBoundingBox {
771            north_west: GeoHash::new(b"u").unwrap(),
772            south_west: GeoHash::new(b"s").unwrap(),
773            south_east: GeoHash::new(b"t").unwrap(),
774            north_east: GeoHash::new(b"v").unwrap(),
775        };
776        let mut geo_area = rect.geohash_regions(1, 100).unwrap();
777        let mut expected = vec![
778            GeoHash::new(b"u").unwrap(),
779            GeoHash::new(b"s").unwrap(),
780            GeoHash::new(b"v").unwrap(),
781            GeoHash::new(b"t").unwrap(),
782        ];
783
784        geo_area.sort_unstable();
785        expected.sort_unstable();
786        assert_eq!(geo_area, expected);
787    }
788
789    #[test]
790    fn nyc_rectangle_geo_area_high_precision() {
791        let rect = GeohashBoundingBox {
792            north_west: GeoHash::new(b"dr5ruj4477kd").unwrap(),
793            south_west: GeoHash::new(b"dr5ru46ne2ux").unwrap(),
794            south_east: GeoHash::new(b"dr5ru6ryw0cp").unwrap(),
795            north_east: GeoHash::new(b"dr5rumpfq534").unwrap(),
796        };
797
798        // calling `rect.geohash_regions()` is too expensive
799        assert!(rect.geohash_regions(12, 100).is_none());
800    }
801
802    #[test]
803    fn nyc_rectangle_geo_area_medium_precision() {
804        let rect = GeohashBoundingBox {
805            north_west: GeoHash::new(b"dr5ruj4").unwrap(),
806            south_west: GeoHash::new(b"dr5ru46").unwrap(),
807            south_east: GeoHash::new(b"dr5ru6r").unwrap(),
808            north_east: GeoHash::new(b"dr5rump").unwrap(),
809        };
810
811        let geo_area = rect.geohash_regions(7, 1000).unwrap();
812        assert_eq!(14 * 12, geo_area.len());
813    }
814
815    #[test]
816    fn nyc_rectangle_geo_area_low_precision() {
817        let rect = GeohashBoundingBox {
818            north_west: GeoHash::new(b"dr5ruj").unwrap(),
819            south_west: GeoHash::new(b"dr5ru4").unwrap(),
820            south_east: GeoHash::new(b"dr5ru6").unwrap(),
821            north_east: GeoHash::new(b"dr5rum").unwrap(),
822        };
823
824        let mut geo_area = rect.geohash_regions(6, 100).unwrap();
825        let mut expected = vec![
826            GeoHash::new(b"dr5ru4").unwrap(),
827            GeoHash::new(b"dr5ru5").unwrap(),
828            GeoHash::new(b"dr5ru6").unwrap(),
829            GeoHash::new(b"dr5ru7").unwrap(),
830            GeoHash::new(b"dr5ruh").unwrap(),
831            GeoHash::new(b"dr5ruj").unwrap(),
832            GeoHash::new(b"dr5rum").unwrap(),
833            GeoHash::new(b"dr5ruk").unwrap(),
834        ];
835
836        expected.sort_unstable();
837        geo_area.sort_unstable();
838        assert_eq!(geo_area, expected);
839    }
840
841    #[test]
842    fn rectangle_hashes_nyc() {
843        // conversion to lon/lat http://geohash.co/
844        // "dr5ruj4477kd"
845        let top_left = GeoPoint {
846            lon: OrderedFloat(-74.00101399),
847            lat: OrderedFloat(40.76517460),
848        };
849
850        // "dr5ru6ryw0cp"
851        let bottom_right = GeoPoint {
852            lon: OrderedFloat(-73.98201792),
853            lat: OrderedFloat(40.75078539),
854        };
855
856        let near_nyc_rectangle = GeoBoundingBox {
857            top_left,
858            bottom_right,
859        };
860
861        let nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 200);
862        let nyc_hashes = nyc_hashes_result.unwrap();
863        assert_eq!(nyc_hashes.len(), 168);
864        assert!(nyc_hashes.iter().all(|h| h.len() == 7)); // geohash precision
865
866        let mut nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 10);
867        nyc_hashes_result.as_mut().unwrap().sort_unstable();
868        let mut expected = vec![
869            GeoHash::new(b"dr5ruj").unwrap(),
870            GeoHash::new(b"dr5ruh").unwrap(),
871            GeoHash::new(b"dr5ru5").unwrap(),
872            GeoHash::new(b"dr5ru4").unwrap(),
873            GeoHash::new(b"dr5rum").unwrap(),
874            GeoHash::new(b"dr5ruk").unwrap(),
875            GeoHash::new(b"dr5ru7").unwrap(),
876            GeoHash::new(b"dr5ru6").unwrap(),
877        ];
878        expected.sort_unstable();
879
880        assert_eq!(nyc_hashes_result.unwrap(), expected);
881
882        // Graphical proof using https://www.movable-type.co.uk/scripts/geohash.html
883
884        // dr5rgy dr5run dr5ruq dr5ruw
885        // dr5rgv dr5ruj dr5rum dr5rut
886        // dr5rgu dr5ruh dr5ruk dr5rus
887        // dr5rgg dr5ru5 dr5ru7 dr5rue
888        // dr5rgf dr5ru4 dr5ru6 dr5rud
889        // dr5rgc dr5ru1 dr5ru3 dr5ru9
890
891        // XXXXXX XXXXXX XXXXXX XXXXXX
892        // XXXXXX dr5ruj dr5rum XXXXXX
893        // XXXXXX dr5ruh dr5ruk XXXXXX
894        // XXXXXX dr5ru5 dr5ru7 XXXXXX
895        // XXXXXX dr5ru4 Xr5ru6 XXXXXX
896        // XXXXXX XXXXXX XXXXXX XXXXXX
897
898        // falls back to finest region that encompasses the whole area
899        let nyc_hashes_result = rectangle_hashes(&near_nyc_rectangle, 7);
900        assert_eq!(
901            nyc_hashes_result.unwrap(),
902            [GeoHash::new(b"dr5ru").unwrap()],
903        );
904    }
905
906    #[test]
907    fn rectangle_hashes_crossing_antimeridian() {
908        // conversion to lon/lat http://geohash.co/
909        // "ztnv2hjxn03k"
910        let top_left = GeoPoint {
911            lat: OrderedFloat(74.071028),
912            lon: OrderedFloat(167.0),
913        };
914
915        // "dr5ru7c02wnv"
916        let bottom_right = GeoPoint {
917            lat: OrderedFloat(40.75798),
918            lon: OrderedFloat(-73.991516),
919        };
920
921        let crossing_usa_rectangle = GeoBoundingBox {
922            top_left,
923            bottom_right,
924        };
925
926        let usa_hashes_result = rectangle_hashes(&crossing_usa_rectangle, 200);
927        let usa_hashes = usa_hashes_result.unwrap();
928        assert_eq!(usa_hashes.len(), 84);
929        assert!(usa_hashes.iter().all(|h| h.len() == 2)); // low geohash precision
930
931        let mut usa_hashes_result = rectangle_hashes(&crossing_usa_rectangle, 10);
932        usa_hashes_result.as_mut().unwrap().sort_unstable();
933        let mut expected = vec![
934            GeoHash::new(b"8").unwrap(),
935            GeoHash::new(b"9").unwrap(),
936            GeoHash::new(b"b").unwrap(),
937            GeoHash::new(b"c").unwrap(),
938            GeoHash::new(b"d").unwrap(),
939            GeoHash::new(b"f").unwrap(),
940            GeoHash::new(b"x").unwrap(),
941            GeoHash::new(b"z").unwrap(),
942        ];
943        expected.sort_unstable();
944
945        assert_eq!(usa_hashes_result.unwrap(), expected);
946
947        // Graphical proof using https://www.movable-type.co.uk/scripts/geohash.html
948
949        // n p 0 1 4 5
950        // y z b c f g
951        // w x 8 9 d e
952        // q r 2 3 6 7
953
954        // - - - - - -
955        // | z b c f |
956        // | x 8 9 d |
957        // - - - - - -
958    }
959
960    #[test]
961    fn polygon_hashes_nyc() {
962        // conversion to lon/lat http://geohash.co/
963        // "dr5ruj4477kd"
964        let near_nyc_polygon = build_polygon(vec![
965            (-74.00101399, 40.76517460),
966            (-73.98201792, 40.76517460),
967            (-73.98201792, 40.75078539),
968            (-74.00101399, 40.75078539),
969            (-74.00101399, 40.76517460),
970        ]);
971
972        let nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 200);
973        let nyc_hashes = nyc_hashes_result.unwrap();
974        assert_eq!(nyc_hashes.len(), 168);
975        assert!(nyc_hashes.iter().all(|h| h.len() == 7)); // geohash precision
976
977        let mut nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 10);
978        nyc_hashes_result.as_mut().unwrap().sort_unstable();
979        let mut expected = vec![
980            GeoHash::new(b"dr5ruj").unwrap(),
981            GeoHash::new(b"dr5ruh").unwrap(),
982            GeoHash::new(b"dr5ru5").unwrap(),
983            GeoHash::new(b"dr5ru4").unwrap(),
984            GeoHash::new(b"dr5rum").unwrap(),
985            GeoHash::new(b"dr5ruk").unwrap(),
986            GeoHash::new(b"dr5ru7").unwrap(),
987            GeoHash::new(b"dr5ru6").unwrap(),
988        ];
989        expected.sort_unstable();
990
991        assert_eq!(nyc_hashes_result.unwrap(), expected);
992
993        // falls back to finest region that encompasses the whole area
994        let nyc_hashes_result = polygon_hashes(&near_nyc_polygon, 7);
995        assert_eq!(
996            nyc_hashes_result.unwrap(),
997            [GeoHash::new(b"dr5ru").unwrap()],
998        );
999    }
1000
1001    #[test]
1002    fn random_circles() {
1003        let mut rnd = StdRng::seed_from_u64(42);
1004        for _ in 0..1000 {
1005            let r_meters = rnd.random_range(1.0..10000.0);
1006            let query = GeoRadius {
1007                center: GeoPoint::new_unchecked(
1008                    rnd.random_range(LON_RANGE),
1009                    rnd.random_range(LAT_RANGE),
1010                ),
1011                radius: OrderedFloat(r_meters),
1012            };
1013            let max_hashes = rnd.random_range(1..32);
1014            let hashes = circle_hashes(&query, max_hashes);
1015            assert!(hashes.unwrap().len() <= max_hashes);
1016        }
1017    }
1018
1019    #[test]
1020    fn test_check_polygon_intersection() {
1021        fn check_intersection(geohash: &str, polygon: &GeoPolygon, expected: bool) {
1022            let intersect = check_polygon_intersection(geohash, &polygon.convert().polygon);
1023            assert_eq!(intersect, expected);
1024        }
1025
1026        // Create a geohash as (-56.2, 33.75), (-56.2, 39.375), (-45, 39.375), (-45, 33.75)
1027        let geohash = encode(Coord { x: -50.0, y: 35.0 }, 2).unwrap();
1028
1029        // Test a polygon intersect with the geohash
1030        check_intersection(
1031            &geohash,
1032            &build_polygon(vec![
1033                (-60.0, 37.0),
1034                (-60.0, 45.0),
1035                (-50.0, 45.0),
1036                (-50.0, 37.0),
1037                (-60.0, 37.0),
1038            ]),
1039            true,
1040        );
1041
1042        // Test a polygon does not intersect with the geohash
1043        check_intersection(
1044            &geohash,
1045            &build_polygon(vec![
1046                (-70.2, 50.8),
1047                (-70.2, 55.9),
1048                (-65.6, 55.9),
1049                (-65.6, 50.8),
1050                (-70.2, 50.8),
1051            ]),
1052            false,
1053        );
1054
1055        // Test a polygon that overlap with the geohash
1056        check_intersection(
1057            &geohash,
1058            &build_polygon(vec![
1059                (-56.2, 33.75),
1060                (-56.2, 39.375),
1061                (-45.0, 39.375),
1062                (-45.0, 33.75),
1063                (-56.2, 33.75),
1064            ]),
1065            true,
1066        );
1067
1068        // Test a polygon that only share one edge with the geohash
1069        check_intersection(
1070            &geohash,
1071            &build_polygon(vec![
1072                (-45.0, 39.375),
1073                (-45.0, 45.0),
1074                (-30.9, 45.0),
1075                (-30.9, 39.375),
1076                (-45.0, 39.375),
1077            ]),
1078            true,
1079        );
1080
1081        // Test a polygon that is within the geohash
1082        check_intersection(
1083            &geohash,
1084            &build_polygon(vec![
1085                (-55.7, 34.3),
1086                (-55.7, 38.0),
1087                (-46.8, 38.0),
1088                (-46.8, 34.3),
1089                (-55.7, 34.3),
1090            ]),
1091            true,
1092        );
1093
1094        // Test a polygon that contains the geohash
1095        check_intersection(
1096            &geohash,
1097            &build_polygon(vec![
1098                (-60.0, 33.0),
1099                (-60.0, 40.0),
1100                (-44.0, 40.0),
1101                (-44.0, 33.0),
1102                (-60.0, 33.0),
1103            ]),
1104            true,
1105        );
1106
1107        // The geohash is in the exterior of the polygon
1108        check_intersection(
1109            &geohash,
1110            &build_polygon_with_interiors(
1111                vec![
1112                    (-70.0, 13.0),
1113                    (-70.0, 50.0),
1114                    (-34.0, 50.0),
1115                    (-34.0, 13.0),
1116                    (-70.0, 13.0),
1117                ],
1118                vec![vec![
1119                    (-60.0, 33.0),
1120                    (-60.0, 40.0),
1121                    (-44.0, 40.0),
1122                    (-44.0, 33.0),
1123                    (-60.0, 33.0),
1124                ]],
1125            ),
1126            false,
1127        );
1128    }
1129
1130    #[test]
1131    fn test_lon_threshold() {
1132        let query = GeoRadius {
1133            center: GeoPoint {
1134                lon: OrderedFloat(179.987181),
1135                lat: OrderedFloat(44.9811609411936),
1136            },
1137            radius: OrderedFloat(100000.),
1138        };
1139
1140        let max_hashes = 10;
1141        let hashes = circle_hashes(&query, max_hashes);
1142        assert_eq!(
1143            hashes.unwrap(),
1144            vec![
1145                GeoHash::new(b"zbp").unwrap(),
1146                GeoHash::new(b"b00").unwrap(),
1147                GeoHash::new(b"xzz").unwrap(),
1148                GeoHash::new(b"8pb").unwrap(),
1149            ],
1150        );
1151    }
1152
1153    #[test]
1154    fn wide_circle_meridian() {
1155        let query = GeoRadius {
1156            center: GeoPoint {
1157                lon: OrderedFloat(-17.81718188959701),
1158                lat: OrderedFloat(89.9811609411936),
1159            },
1160            radius: OrderedFloat(9199.481636468849),
1161        };
1162
1163        let max_hashes = 10;
1164        let hashes = circle_hashes(&query, max_hashes);
1165        let vec = hashes.unwrap();
1166        assert!(vec.len() <= max_hashes);
1167        assert_eq!(
1168            vec,
1169            [
1170                GeoHash::new(b"b").unwrap(),
1171                GeoHash::new(b"c").unwrap(),
1172                GeoHash::new(b"f").unwrap(),
1173                GeoHash::new(b"g").unwrap(),
1174                GeoHash::new(b"u").unwrap(),
1175                GeoHash::new(b"v").unwrap(),
1176                GeoHash::new(b"y").unwrap(),
1177                GeoHash::new(b"z").unwrap(),
1178            ],
1179        );
1180    }
1181
1182    #[test]
1183    fn tight_circle_meridian() {
1184        let query = GeoRadius {
1185            center: GeoPoint {
1186                lon: OrderedFloat(-17.81718188959701),
1187                lat: OrderedFloat(89.9811609411936),
1188            },
1189            radius: OrderedFloat(1000.0),
1190        };
1191
1192        let max_hashes = 10;
1193        let hashes_result = circle_hashes(&query, max_hashes);
1194        let hashes = hashes_result.unwrap();
1195        assert!(hashes.len() <= max_hashes);
1196        assert_eq!(
1197            hashes,
1198            [
1199                GeoHash::new(b"fz").unwrap(),
1200                GeoHash::new(b"gp").unwrap(),
1201                GeoHash::new(b"gr").unwrap(),
1202                GeoHash::new(b"gx").unwrap(),
1203                GeoHash::new(b"gz").unwrap(),
1204                GeoHash::new(b"up").unwrap(),
1205            ],
1206        );
1207    }
1208
1209    #[test]
1210    fn wide_circle_south_pole() {
1211        let query = GeoRadius {
1212            center: GeoPoint {
1213                lon: OrderedFloat(155.85591760141335),
1214                lat: OrderedFloat(-74.19418872656166),
1215            },
1216            radius: OrderedFloat(7133.775526733084),
1217        };
1218        let max_hashes = 10;
1219        let hashes_result = circle_hashes(&query, max_hashes);
1220        let hashes = hashes_result.unwrap();
1221        assert!(hashes.len() <= max_hashes);
1222        assert_eq!(
1223            hashes,
1224            [
1225                GeoHash::new(b"p6yd").unwrap(),
1226                GeoHash::new(b"p6yf").unwrap(),
1227                GeoHash::new(b"p6y9").unwrap(),
1228                GeoHash::new(b"p6yc").unwrap(),
1229            ],
1230        );
1231    }
1232
1233    #[test]
1234    fn tight_circle_south_pole() {
1235        let query = GeoRadius {
1236            center: GeoPoint {
1237                lon: OrderedFloat(155.85591760141335),
1238                lat: OrderedFloat(-74.19418872656166),
1239            },
1240            radius: OrderedFloat(1000.0),
1241        };
1242        let max_hashes = 10;
1243        let hashes_result = circle_hashes(&query, max_hashes);
1244        let hashes = hashes_result.unwrap();
1245        assert!(hashes.len() <= max_hashes);
1246        assert_eq!(
1247            hashes,
1248            [
1249                GeoHash::new(b"p6ycc").unwrap(),
1250                GeoHash::new(b"p6ycf").unwrap(),
1251                GeoHash::new(b"p6ycg").unwrap(),
1252            ],
1253        );
1254    }
1255
1256    #[test]
1257    fn circle_hashes_nyc() {
1258        let near_nyc_circle = GeoRadius {
1259            center: NYC,
1260            radius: OrderedFloat(800.0),
1261        };
1262
1263        let nyc_hashes_result = circle_hashes(&near_nyc_circle, 200).unwrap();
1264        assert!(nyc_hashes_result.iter().all(|h| h.len() == 7)); // geohash precision
1265
1266        let mut nyc_hashes_result = circle_hashes(&near_nyc_circle, 10);
1267        nyc_hashes_result.as_mut().unwrap().sort_unstable();
1268        let mut expected = [
1269            GeoHash::new(b"dr5ruj").unwrap(),
1270            GeoHash::new(b"dr5ruh").unwrap(),
1271            GeoHash::new(b"dr5ru5").unwrap(),
1272            GeoHash::new(b"dr5ru4").unwrap(),
1273            GeoHash::new(b"dr5rum").unwrap(),
1274            GeoHash::new(b"dr5ruk").unwrap(),
1275            GeoHash::new(b"dr5ru7").unwrap(),
1276            GeoHash::new(b"dr5ru6").unwrap(),
1277        ];
1278        expected.sort_unstable();
1279        assert_eq!(nyc_hashes_result.unwrap(), expected);
1280
1281        // falls back to finest region that encompasses the whole area
1282        let nyc_hashes_result = circle_hashes(&near_nyc_circle, 7);
1283        assert_eq!(
1284            nyc_hashes_result.unwrap(),
1285            [GeoHash::new(b"dr5ru").unwrap()],
1286        );
1287    }
1288
1289    #[test]
1290    fn go_north() {
1291        let mut geohash = sphere_neighbor(GeoHash::new(b"ww8p").unwrap(), Direction::N).unwrap();
1292        for _ in 0..1000 {
1293            geohash = sphere_neighbor(geohash, Direction::N).unwrap();
1294        }
1295    }
1296
1297    #[test]
1298    fn go_west() {
1299        let starting_hash = GeoHash::new(b"ww8").unwrap();
1300        let mut geohash = sphere_neighbor(starting_hash, Direction::W).unwrap();
1301        let mut is_earth_round = false;
1302        for _ in 0..1000 {
1303            geohash = sphere_neighbor(geohash, Direction::W).unwrap();
1304            if geohash == starting_hash {
1305                is_earth_round = true;
1306            }
1307        }
1308        assert!(is_earth_round)
1309    }
1310
1311    #[test]
1312    fn sphere_neighbor_corner_cases() {
1313        assert_eq!(
1314            &EcoString::from(sphere_neighbor(GeoHash::new(b"z").unwrap(), Direction::NE).unwrap()),
1315            "b",
1316        );
1317        assert_eq!(
1318            &EcoString::from(sphere_neighbor(GeoHash::new(b"zz").unwrap(), Direction::NE).unwrap()),
1319            "bp",
1320        );
1321        assert_eq!(
1322            &EcoString::from(sphere_neighbor(GeoHash::new(b"0").unwrap(), Direction::SW).unwrap()),
1323            "p",
1324        );
1325        assert_eq!(
1326            &EcoString::from(sphere_neighbor(GeoHash::new(b"00").unwrap(), Direction::SW).unwrap()),
1327            "pb",
1328        );
1329
1330        assert_eq!(
1331            &EcoString::from(sphere_neighbor(GeoHash::new(b"8").unwrap(), Direction::W).unwrap()),
1332            "x",
1333        );
1334        assert_eq!(
1335            &EcoString::from(sphere_neighbor(GeoHash::new(b"8h").unwrap(), Direction::W).unwrap()),
1336            "xu",
1337        );
1338        assert_eq!(
1339            &EcoString::from(sphere_neighbor(GeoHash::new(b"r").unwrap(), Direction::E).unwrap()),
1340            "2",
1341        );
1342        assert_eq!(
1343            &EcoString::from(sphere_neighbor(GeoHash::new(b"ru").unwrap(), Direction::E).unwrap()),
1344            "2h",
1345        );
1346
1347        assert_eq!(
1348            EcoString::from(
1349                sphere_neighbor(GeoHash::new(b"ww8p1r4t8").unwrap(), Direction::SE).unwrap()
1350            ),
1351            EcoString::from(&geohash::neighbor("ww8p1r4t8", Direction::SE).unwrap()),
1352        );
1353    }
1354
1355    #[test]
1356    fn long_overflow_distance() {
1357        let dist = Haversine.distance(Point::new(-179.999, 66.0), Point::new(179.999, 66.0));
1358        eprintln!("dist` = {dist:#?}");
1359        assert_eq!(dist, 90.45422731917998);
1360        let dist = Haversine.distance(Point::new(0.99, 90.), Point::new(0.99, -90.0));
1361        assert_eq!(dist, 20015114.442035925);
1362    }
1363
1364    #[test]
1365    fn turn_geo_hash_to_box() {
1366        let geo_box = geo_hash_to_box(GeoHash::new(b"dr5ruj4477kd").unwrap());
1367        let center = GeoPoint {
1368            lat: OrderedFloat(40.76517460),
1369            lon: OrderedFloat(-74.00101399),
1370        };
1371        assert!(geo_box.check_point(&center));
1372    }
1373
1374    #[test]
1375    fn common_prefix() {
1376        let geo_hashes = vec![
1377            GeoHash::new(b"zbcd123").unwrap(),
1378            GeoHash::new(b"zbcd2233").unwrap(),
1379            GeoHash::new(b"zbcd3213").unwrap(),
1380            GeoHash::new(b"zbcd533").unwrap(),
1381        ];
1382
1383        let common_prefix = common_hash_prefix(&geo_hashes).unwrap();
1384        println!("common_prefix = {:?}", EcoString::from(common_prefix));
1385
1386        //assert_eq!(common_prefix, GeoHash::new("zbcd").unwrap());
1387
1388        let geo_hashes = vec![
1389            GeoHash::new(b"zbcd123").unwrap(),
1390            GeoHash::new(b"bbcd2233").unwrap(),
1391            GeoHash::new(b"cbcd3213").unwrap(),
1392            GeoHash::new(b"dbcd533").unwrap(),
1393        ];
1394
1395        let common_prefix = common_hash_prefix(&geo_hashes).unwrap();
1396        println!("common_prefix = {:?}", EcoString::from(common_prefix));
1397
1398        assert_eq!(common_prefix, GeoHash::new(b"").unwrap());
1399    }
1400
1401    #[test]
1402    fn max_regions_cannot_be_equal_to_zero() {
1403        let invalid_max_hashes = 0;
1404
1405        // circle
1406        let sample_circle = GeoRadius {
1407            center: GeoPoint {
1408                lon: OrderedFloat(179.987181),
1409                lat: OrderedFloat(44.9811609411936),
1410            },
1411            radius: OrderedFloat(100000.),
1412        };
1413        let circle_hashes = circle_hashes(&sample_circle, invalid_max_hashes);
1414        assert!(circle_hashes.is_err());
1415
1416        // rectangle
1417        let top_left = GeoPoint {
1418            lon: OrderedFloat(-74.00101399),
1419            lat: OrderedFloat(40.76517460),
1420        };
1421
1422        let bottom_right = GeoPoint {
1423            lon: OrderedFloat(-73.98201792),
1424            lat: OrderedFloat(40.75078539),
1425        };
1426
1427        let sample_rectangle = GeoBoundingBox {
1428            top_left,
1429            bottom_right,
1430        };
1431        let rectangle_hashes = rectangle_hashes(&sample_rectangle, invalid_max_hashes);
1432        assert!(rectangle_hashes.is_err());
1433
1434        // polygon
1435        let sample_polygon = build_polygon(vec![
1436            (-74.00101399, 40.76517460),
1437            (-73.98201792, 40.75078539),
1438        ]);
1439
1440        let polygon_hashes = polygon_hashes(&sample_polygon, invalid_max_hashes);
1441        assert!(polygon_hashes.is_err());
1442    }
1443
1444    #[test]
1445    fn geo_radius_zero_division() {
1446        let circle = GeoRadius {
1447            center: GeoPoint {
1448                lon: OrderedFloat(45.0),
1449                lat: OrderedFloat(80.0),
1450            },
1451            radius: OrderedFloat(1000.0),
1452        };
1453        let hashes = circle_hashes(&circle, GeoHash::MAX_LEN);
1454        assert!(hashes.is_ok());
1455
1456        let circle2 = GeoRadius {
1457            center: GeoPoint {
1458                lon: OrderedFloat(45.0),
1459                lat: OrderedFloat(90.0),
1460            },
1461            radius: OrderedFloat(-1.0),
1462        };
1463        let hashes2 = circle_hashes(&circle2, GeoHash::MAX_LEN);
1464        assert!(hashes2.is_err());
1465    }
1466}
qdrant_edge/segment/index/field_index/geo_hash.rs

qdrant_edge/segment/index/field_index/
geo_hash.rs
