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

qdrant_edge/segment/index/field_index/
geo_hash.rs
