hilbert_geometry/
lib.rs

1use bincode::{
2    config,
3    config::Configuration,
4    error::{DecodeError, EncodeError},
5    Decode, Encode,
6};
7use fast_hilbert::{h2xy, xy2h};
8use geo_types::{
9    Coord, Geometry, LineString, MultiLineString, MultiPoint, MultiPolygon, Point, Polygon,
10};
11
12/// Represents a Hilbert-encoded point.
13#[derive(Debug, Clone, Copy, Decode, Encode)]
14pub struct HilbertPoint(pub u128);
15
16/// Represents a Hilbert-encoded geometry.
17#[derive(Debug, Clone, Decode, Encode)]
18pub enum HilbertGeometry {
19    Point(HilbertPoint),
20    LineString(Vec<HilbertPoint>),
21    Polygon(Vec<Vec<HilbertPoint>>),
22    MultiPoint(Vec<HilbertPoint>),
23    MultiLineString(Vec<Vec<HilbertPoint>>),
24    MultiPolygon(Vec<Vec<Vec<HilbertPoint>>>),
25}
26
27/// Encodes a 2D coordinate into a Hilbert index.
28fn encode_coord(coord: Coord<f64>) -> HilbertPoint {
29    HilbertPoint(xy2h(coord.x.to_bits(), coord.y.to_bits(), 32))
30}
31
32/// Decodes a Hilbert index back into a 2D coordinate.
33fn decode_coord(p: HilbertPoint) -> Coord<f64> {
34    let (x, y) = h2xy(p.0, 32);
35    Coord {
36        x: f64::from_bits(x),
37        y: f64::from_bits(y),
38    }
39}
40
41/// Encodes a `geo-types` geometry into a Hilbert-encoded geometry.
42pub fn encode_geometry(geom: &Geometry<f64>) -> HilbertGeometry {
43    let make_point = |pt: &Point| HilbertGeometry::Point(encode_coord(pt.0));
44    let make_linestring = |ls: &LineString| {
45        let encoded = ls.points().map(|p| encode_coord(p.0)).collect();
46        HilbertGeometry::LineString(encoded)
47    };
48    let make_poly = |poly: &Polygon| {
49        let exterior = poly
50            .exterior()
51            .points()
52            .map(|p| encode_coord(p.0))
53            .collect::<Vec<HilbertPoint>>();
54        let interiors = poly
55            .interiors()
56            .iter()
57            .map(|ring| {
58                ring.points()
59                    .map(|p| encode_coord(p.0))
60                    .collect::<Vec<HilbertPoint>>()
61            })
62            .collect::<Vec<Vec<HilbertPoint>>>();
63        HilbertGeometry::Polygon(vec![vec![exterior], interiors].concat())
64    };
65
66    match geom {
67        Geometry::Point(pt) => make_point(pt),
68        Geometry::LineString(ls) => make_linestring(ls),
69        Geometry::Polygon(poly) => make_poly(poly),
70        Geometry::MultiPoint(geoms) => HilbertGeometry::MultiPoint(
71            geoms
72                .iter()
73                .map(make_point)
74                .filter_map(|hg| {
75                    if let HilbertGeometry::Point(hp) = hg {
76                        Some(hp)
77                    } else {
78                        None
79                    }
80                })
81                .collect(),
82        ),
83        Geometry::MultiLineString(geoms) => HilbertGeometry::MultiLineString(
84            geoms
85                .iter()
86                .map(make_linestring)
87                .filter_map(|hg| {
88                    if let HilbertGeometry::LineString(hp) = hg {
89                        Some(hp)
90                    } else {
91                        None
92                    }
93                })
94                .collect(),
95        ),
96        Geometry::MultiPolygon(geoms) => HilbertGeometry::MultiPolygon(
97            geoms
98                .iter()
99                .map(make_poly)
100                .filter_map(|hg| {
101                    if let HilbertGeometry::Polygon(hp) = hg {
102                        Some(hp)
103                    } else {
104                        None
105                    }
106                })
107                .collect(),
108        ),
109        _ => unimplemented!("Geometry type not supported"),
110    }
111}
112
113/// Decodes a Hilbert-encoded geometry back into a `geo-types` geometry.
114pub fn decode_geometry(hgeom: &HilbertGeometry) -> Geometry<f64> {
115    match hgeom {
116        HilbertGeometry::Point(hp) => {
117            let coord = decode_coord(*hp);
118            Geometry::Point(Point(coord))
119        }
120        HilbertGeometry::LineString(hps) => {
121            let coords = hps.iter().map(|hp| decode_coord(*hp)).collect();
122            Geometry::LineString(LineString(coords))
123        }
124        HilbertGeometry::Polygon(rings) => {
125            if rings.is_empty() {
126                return Geometry::Polygon(Polygon::new(LineString::new(vec![]), vec![]));
127            }
128            let exterior = LineString(rings[0].iter().map(|hp| decode_coord(*hp)).collect());
129            let interiors = rings[1..]
130                .iter()
131                .map(|ring| LineString(ring.iter().map(|hp| decode_coord(*hp)).collect()))
132                .collect();
133            Geometry::Polygon(Polygon::new(exterior, interiors))
134        }
135        HilbertGeometry::MultiPoint(hps) => {
136            let coords = hps.iter().map(|hp| decode_coord(*hp).into()).collect();
137            Geometry::MultiPoint(MultiPoint(coords))
138        }
139        HilbertGeometry::MultiLineString(hps) => {
140            let linestrings = hps
141                .iter()
142                .map(|ls| decode_geometry(&HilbertGeometry::LineString(ls.clone())))
143                .map(|g| g.try_into().unwrap())
144                .collect();
145            Geometry::MultiLineString(MultiLineString(linestrings))
146        }
147        HilbertGeometry::MultiPolygon(hps) => {
148            let polygons = hps
149                .iter()
150                .map(|poly| decode_geometry(&HilbertGeometry::Polygon(poly.clone())))
151                .map(|g| g.try_into().unwrap())
152                .collect();
153            Geometry::MultiPolygon(MultiPolygon(polygons))
154        }
155    }
156}
157
158impl From<&Geometry> for HilbertGeometry {
159    fn from(geom: &Geometry) -> Self {
160        encode_geometry(&geom)
161    }
162}
163
164impl Into<Geometry> for HilbertGeometry {
165    fn into(self) -> Geometry {
166        decode_geometry(&self)
167    }
168}
169
170impl HilbertGeometry {
171    pub fn encode_bincode(self, config: &Configuration) -> Result<Vec<u8>, EncodeError> {
172        bincode::encode_to_vec(self, *config)
173    }
174
175    pub fn decode_bincode(
176        data: &[u8],
177        config: &Configuration,
178    ) -> Result<HilbertGeometry, DecodeError> {
179        let (decoded, _) = bincode::decode_from_slice(data, *config)?;
180        Ok(decoded)
181    }
182}
183
184// Geometry <-> HWKB
185pub struct HilbertSerializer {
186    config: Configuration,
187}
188
189impl HilbertSerializer {
190    pub fn new() -> Self {
191        Self {
192            config: config::standard(),
193        }
194    }
195
196    pub fn encode(&self, geom: &Geometry) -> Result<Vec<u8>, EncodeError> {
197        let hg = HilbertGeometry::from(geom);
198        hg.encode_bincode(&self.config)
199    }
200
201    pub fn decode(&self, data: &[u8]) -> Result<Geometry, DecodeError> {
202        let hg = HilbertGeometry::decode_bincode(data, &self.config)?;
203        Ok(hg.into())
204    }
205}
hilbert_geometry/lib.rs

hilbert_geometry/
lib.rs
