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

hilbert_geometry/
lib.rs
