maplibre/io/
geometry_index.rs

1//! Geometry index.
2
3use std::collections::{BTreeMap, HashMap};
4
5use cgmath::{num_traits::Signed, Bounded};
6use geo::prelude::*;
7use geo_types::{Coord, CoordFloat, Geometry, LineString, Point, Polygon};
8use geozero::{
9    error::GeozeroError, geo_types::GeoWriter, ColumnValue, FeatureProcessor, GeomProcessor,
10    PropertyProcessor,
11};
12use rstar::{Envelope, PointDistance, RTree, RTreeObject, AABB};
13
14use crate::{
15    coords::{
16        InnerCoords, Quadkey, WorldCoords, WorldTileCoords, Zoom, ZoomLevel, EXTENT, TILE_SIZE,
17    },
18    util::math::bounds_from_points,
19};
20
21/// A quad tree storing the currently loaded tiles.
22pub struct GeometryIndex {
23    index: BTreeMap<Quadkey, TileIndex>,
24}
25
26impl GeometryIndex {
27    pub fn new() -> Self {
28        Self {
29            index: Default::default(),
30        }
31    }
32
33    pub fn index_tile(&mut self, coords: &WorldTileCoords, tile_index: TileIndex) {
34        coords
35            .build_quad_key()
36            .and_then(|key| self.index.insert(key, tile_index));
37    }
38
39    pub fn query_point(
40        &self,
41        world_coords: &WorldCoords,
42        z: ZoomLevel,
43        zoom: Zoom,
44    ) -> Option<Vec<&IndexedGeometry<f64>>> {
45        let world_tile_coords = world_coords.into_world_tile(z, zoom);
46
47        if let Some(index) = world_tile_coords
48            .build_quad_key()
49            .and_then(|key| self.index.get(&key))
50        {
51            let scale = zoom.scale_delta(&Zoom::from(z)); // FIXME: can be wrong, if tiles of different z are visible
52
53            let delta_x = world_coords.x / TILE_SIZE * scale - world_tile_coords.x as f64;
54            let delta_y = world_coords.y / TILE_SIZE * scale - world_tile_coords.y as f64;
55
56            let x = delta_x * EXTENT;
57            let y = delta_y * EXTENT;
58            Some(index.point_query(InnerCoords { x, y }))
59        } else {
60            None
61        }
62    }
63}
64
65impl Default for GeometryIndex {
66    fn default() -> Self {
67        Self::new()
68    }
69}
70
71/// Index of tiles which can be of two types: spatial or linear.
72/// Spatial tiles are stored in a multi-dimentional tree which represents their position in the tile.
73/// Linear tiles are simply stored in a vector.
74///
75/// A spatial tile index can theoretically improve query performance on tiles. Practically it could be slower though. The `Spatial` index is experimental and currently unused.
76pub enum TileIndex {
77    Spatial { tree: RTree<IndexedGeometry<f64>> },
78    Linear { list: Vec<IndexedGeometry<f64>> },
79}
80
81impl TileIndex {
82    pub fn point_query(&self, inner_coords: InnerCoords) -> Vec<&IndexedGeometry<f64>> {
83        let point = Point::new(inner_coords.x, inner_coords.y);
84        let coordinate: Coord<_> = point.into();
85
86        // FIXME: Respect layer order of style
87        match self {
88            TileIndex::Spatial { tree } => tree
89                .nearest_neighbor_iter(&point)
90                .filter(|geometry| match &geometry.exact {
91                    ExactGeometry::Polygon(exact) => exact.contains(&coordinate),
92                    ExactGeometry::LineString(exact) => exact.distance_2(&point) <= 64.0,
93                })
94                .collect::<Vec<_>>(),
95            TileIndex::Linear { list } => list
96                .iter()
97                .filter(|geometry| match &geometry.exact {
98                    ExactGeometry::Polygon(exact) => exact.contains(&coordinate),
99                    ExactGeometry::LineString(exact) => exact.distance_2(&point) <= 64.0,
100                })
101                .collect::<Vec<_>>(),
102        }
103    }
104}
105
106/// An indexed geometry contains an exact vector geometry, computed bounds which
107/// can be helpful when interacting with the geometry and a hashmap of properties.
108#[derive(Debug, Clone)]
109pub struct IndexedGeometry<T>
110where
111    T: CoordFloat + Bounded + Signed,
112{
113    pub bounds: AABB<Point<T>>,
114    pub exact: ExactGeometry<T>,
115    pub properties: HashMap<String, String>,
116}
117
118/// Contains either a polygon or line vector.
119#[derive(Debug, Clone)]
120pub enum ExactGeometry<T>
121where
122    T: CoordFloat + Bounded + Signed,
123{
124    Polygon(Polygon<T>),
125    LineString(LineString<T>),
126}
127
128impl<T> IndexedGeometry<T>
129where
130    T: CoordFloat + Bounded + Signed + PartialOrd,
131{
132    fn from_polygon(polygon: Polygon<T>, properties: HashMap<String, String>) -> Option<Self> {
133        let (min, max) = bounds_from_points(polygon.exterior().points())?;
134
135        Some(Self {
136            exact: ExactGeometry::Polygon(polygon),
137            bounds: AABB::from_corners(Point::from(min), Point::from(max)),
138            properties,
139        })
140    }
141    fn from_linestring(
142        linestring: LineString<T>,
143        properties: HashMap<String, String>,
144    ) -> Option<Self> {
145        let bounds = linestring.envelope();
146
147        Some(Self {
148            exact: ExactGeometry::LineString(linestring),
149            bounds,
150            properties,
151        })
152    }
153}
154
155impl<T> RTreeObject for IndexedGeometry<T>
156where
157    T: CoordFloat + Bounded + Signed + PartialOrd,
158{
159    type Envelope = AABB<Point<T>>;
160
161    fn envelope(&self) -> Self::Envelope {
162        self.bounds
163    }
164}
165
166impl<T> PointDistance for IndexedGeometry<T>
167where
168    T: CoordFloat + Bounded + Signed + PartialOrd,
169{
170    fn distance_2(
171        &self,
172        point: &<Self::Envelope as Envelope>::Point,
173    ) -> <<Self::Envelope as Envelope>::Point as rstar::Point>::Scalar {
174        self.bounds.center().distance_2(point)
175    }
176
177    fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
178        self.bounds.contains_point(point)
179    }
180}
181
182/// A processor able to create geometries using `[geozero::geo_types::GeoWriter]`.
183pub struct IndexProcessor {
184    geo_writer: GeoWriter,
185    geometries: Vec<IndexedGeometry<f64>>,
186    properties: Option<HashMap<String, String>>,
187}
188
189impl IndexProcessor {
190    pub fn new() -> Self {
191        Self {
192            geo_writer: GeoWriter::new(),
193            geometries: Vec::new(),
194            properties: None,
195        }
196    }
197
198    pub fn build_tree(self) -> RTree<IndexedGeometry<f64>> {
199        RTree::bulk_load(self.geometries)
200    }
201
202    pub fn get_geometries(self) -> Vec<IndexedGeometry<f64>> {
203        self.geometries
204    }
205}
206
207impl Default for IndexProcessor {
208    fn default() -> Self {
209        Self::new()
210    }
211}
212
213impl GeomProcessor for IndexProcessor {
214    fn xy(&mut self, x: f64, y: f64, idx: usize) -> Result<(), GeozeroError> {
215        self.geo_writer.xy(x, y, idx)
216    }
217    fn point_begin(&mut self, idx: usize) -> Result<(), GeozeroError> {
218        self.geo_writer.point_begin(idx)
219    }
220    fn point_end(&mut self, idx: usize) -> Result<(), GeozeroError> {
221        self.geo_writer.point_end(idx)
222    }
223    fn multipoint_begin(&mut self, size: usize, idx: usize) -> Result<(), GeozeroError> {
224        self.geo_writer.multipoint_begin(size, idx)
225    }
226    fn linestring_begin(
227        &mut self,
228        tagged: bool,
229        size: usize,
230        idx: usize,
231    ) -> Result<(), GeozeroError> {
232        self.geo_writer.linestring_begin(tagged, size, idx)
233    }
234    fn linestring_end(&mut self, tagged: bool, idx: usize) -> Result<(), GeozeroError> {
235        self.geo_writer.linestring_end(tagged, idx)
236    }
237    fn multilinestring_begin(&mut self, size: usize, idx: usize) -> Result<(), GeozeroError> {
238        self.geo_writer.multilinestring_begin(size, idx)
239    }
240    fn multilinestring_end(&mut self, idx: usize) -> Result<(), GeozeroError> {
241        self.geo_writer.multilinestring_end(idx)
242    }
243    fn polygon_begin(&mut self, tagged: bool, size: usize, idx: usize) -> Result<(), GeozeroError> {
244        self.geo_writer.polygon_begin(tagged, size, idx)
245    }
246    fn polygon_end(&mut self, tagged: bool, idx: usize) -> Result<(), GeozeroError> {
247        self.geo_writer.polygon_end(tagged, idx)
248    }
249    fn multipolygon_begin(&mut self, size: usize, idx: usize) -> Result<(), GeozeroError> {
250        self.geo_writer.multipolygon_begin(size, idx)
251    }
252    fn multipolygon_end(&mut self, idx: usize) -> Result<(), GeozeroError> {
253        self.geo_writer.multipolygon_end(idx)
254    }
255}
256
257impl PropertyProcessor for IndexProcessor {
258    fn property(
259        &mut self,
260        _idx: usize,
261        name: &str,
262        value: &ColumnValue,
263    ) -> Result<bool, GeozeroError> {
264        self.properties
265            .as_mut()
266            .unwrap()
267            .insert(name.to_string(), value.to_string());
268        Ok(true)
269    }
270}
271
272impl FeatureProcessor for IndexProcessor {
273    /// Begin of dataset processing.
274    fn dataset_begin(&mut self, _name: Option<&str>) -> Result<(), GeozeroError> {
275        Ok(())
276    }
277    /// End of dataset processing.
278    fn dataset_end(&mut self) -> Result<(), GeozeroError> {
279        Ok(())
280    }
281    /// Begin of feature processing.
282    fn feature_begin(&mut self, _idx: u64) -> Result<(), GeozeroError> {
283        Ok(())
284    }
285    /// End of feature processing.
286    fn feature_end(&mut self, _idx: u64) -> Result<(), GeozeroError> {
287        Ok(())
288    }
289    /// Begin of feature property processing.
290    fn properties_begin(&mut self) -> Result<(), GeozeroError> {
291        self.properties = Some(HashMap::new());
292        Ok(())
293    }
294    /// End of feature property processing.
295    fn properties_end(&mut self) -> Result<(), GeozeroError> {
296        Ok(())
297    }
298    /// Begin of feature geometry processing.
299    fn geometry_begin(&mut self) -> Result<(), GeozeroError> {
300        Ok(())
301    }
302    /// End of feature geometry processing.
303    fn geometry_end(&mut self) -> Result<(), GeozeroError> {
304        let geometry = self.geo_writer.take_geometry();
305
306        match geometry {
307            Some(Geometry::Polygon(polygon)) => self.geometries.push(
308                IndexedGeometry::from_polygon(polygon, self.properties.take().unwrap()).unwrap(),
309            ),
310            Some(Geometry::LineString(linestring)) => self.geometries.push(
311                IndexedGeometry::from_linestring(linestring, self.properties.take().unwrap())
312                    .unwrap(),
313            ),
314            Some(Geometry::Point(_))
315            | Some(Geometry::Line(_))
316            | Some(Geometry::MultiPoint(_))
317            | Some(Geometry::MultiLineString(_))
318            | Some(Geometry::MultiPolygon(_))
319            | Some(Geometry::GeometryCollection(_))
320            | Some(Geometry::Rect(_))
321            | Some(Geometry::Triangle(_)) => {
322                log::debug!("Unsupported geometry in index")
323            }
324            None => {
325                log::debug!("No geometry in index")
326            }
327        };
328
329        Ok(())
330    }
331}
maplibre/io/geometry_index.rs

maplibre/io/
geometry_index.rs
