gistools/data_structures/
tile.rs

1use crate::{
2    geometry::{
3        CellId, ConvertFeature, ConvertVectorFeatureS2, ConvertVectorFeatureWM, S2CellId,
4        SimplifyVectorGeometry, build_sq_dists, clip_features, convert,
5    },
6    parsers::FeatureReader,
7};
8use alloc::{
9    collections::{BTreeMap, BTreeSet},
10    string::{String, ToString},
11    vec,
12    vec::Vec,
13};
14use s2json::{
15    Axis, Face, Feature, JSONCollection, MValue, Projection, Properties, VectorFeature,
16    VectorGeometry, VectorPoint,
17};
18use serde::{Deserialize, Serialize};
19
20/// If a user creates metadata for a VectorFeature, it needs to define a get_layer function
21pub trait HasLayer {
22    /// Get the layer from metadata if it exists
23    fn get_layer(&self) -> Option<String>;
24}
25impl HasLayer for () {
26    fn get_layer(&self) -> Option<String> {
27        None
28    }
29}
30impl HasLayer for MValue {
31    fn get_layer(&self) -> Option<String> {
32        let layer = self.get("layer");
33        match layer {
34            Some(l) => l.to_prim()?.to_string(),
35            _ => None,
36        }
37    }
38}
39
40/// Tile Class to contain the tile information for splitting or simplifying
41#[derive(Debug, Clone, PartialEq)]
42pub struct Tile<M = (), P: Clone + Default = Properties, D: Clone + Default = MValue> {
43    /// the tile id
44    pub id: CellId,
45    /// the tile's layers
46    pub layers: BTreeMap<String, Layer<M, P, D>>,
47    /// whether the tile feature geometry has been transformed
48    pub transformed: bool,
49}
50impl<M: HasLayer + Clone, P: Clone + Default, D: Clone + Default> Tile<M, P, D> {
51    /// Create a new Tile
52    pub fn new(id: CellId) -> Self {
53        Self { id, layers: BTreeMap::new(), transformed: false }
54    }
55
56    /// Returns the number of layers
57    pub fn len(&self) -> usize {
58        self.layers.len()
59    }
60
61    /// Returns true if the tile is empty of features
62    pub fn is_empty(&self) -> bool {
63        for layer in self.layers.values() {
64            if !layer.features.is_empty() {
65                return false;
66            }
67        }
68
69        true
70    }
71
72    /// Add any reader to the tile
73    pub fn add_reader<R>(&mut self, reader: R, layer: Option<String>)
74    where
75        R: FeatureReader<M, P, D>,
76    {
77        for feature in reader.iter() {
78            self.add_feature(feature, layer.clone());
79        }
80    }
81
82    /// Add a feature to the tile
83    pub fn add_feature(&mut self, feature: VectorFeature<M, P, D>, layer: Option<String>) {
84        let layer_name = feature
85            .metadata
86            .as_ref()
87            .and_then(|meta| meta.get_layer()) // Get the layer from metadata if it exists
88            .or(layer) // Fall back to the provided layer
89            .unwrap_or_else(|| "default".to_string()); // Fall back to "default" if none found
90
91        let layer = self.layers.entry(layer_name.clone()).or_insert(Layer::new(layer_name));
92        layer.features.push(feature);
93    }
94
95    /// Simplify the geometry to have a tolerance which will be relative to the tile's zoom level.
96    /// NOTE: This should be called after the tile has been split into children if that functionality
97    /// is needed.
98    pub fn transform(&mut self, tolerance: f64, maxzoom: Option<u8>) {
99        if self.transformed || self.id.is_face() {
100            self.transformed = true;
101            return;
102        }
103
104        let (_, zoom, i, j) = self.id.to_face_ij();
105        for layer in self.layers.values_mut() {
106            for feature in layer.features.iter_mut() {
107                feature.geometry.simplify(tolerance, zoom, maxzoom);
108                feature.geometry.transform(zoom.into(), i as f64, j as f64)
109            }
110        }
111
112        self.transformed = true;
113    }
114
115    /// split tile into 4 children
116    pub fn split(&mut self, buffer: Option<f64>) -> TileChildren<M, P, D> {
117        let buffer = buffer.unwrap_or(0.0625);
118        let (face, zoom, i, j) = self.id.to_face_ij();
119        let [bl_id, br_id, tl_id, tr_id] = S2CellId::children_ij(face, zoom, i, j);
120        let mut children = TileChildren {
121            bottom_left: Tile::new(bl_id),
122            bottom_right: Tile::new(br_id),
123            top_left: Tile::new(tl_id),
124            top_right: Tile::new(tr_id),
125        };
126        let scale = (1 << zoom) as f64;
127        let k1 = 0.;
128        let k2 = 0.5;
129        let k3 = 0.5;
130        let k4 = 1.;
131        let i = i as f64;
132        let j = j as f64;
133
134        let mut tl: Option<Vec<VectorFeature<M, P, D>>>;
135        let mut bl: Option<Vec<VectorFeature<M, P, D>>>;
136        let mut tr: Option<Vec<VectorFeature<M, P, D>>>;
137        let mut br: Option<Vec<VectorFeature<M, P, D>>>;
138
139        for (name, layer) in self.layers.iter_mut() {
140            let features = &layer.features;
141            let left = clip_features(features, scale, i - k1, i + k3, Axis::X, buffer);
142            let right = clip_features(features, scale, i + k2, i + k4, Axis::X, buffer);
143
144            if let Some(left) = left {
145                bl = clip_features(&left, scale, j - k1, j + k3, Axis::Y, buffer);
146                tl = clip_features(&left, scale, j + k2, j + k4, Axis::Y, buffer);
147                if let Some(bl) = bl {
148                    for d in bl {
149                        children.bottom_left.add_feature(d, Some(name.to_string()));
150                    }
151                }
152                if let Some(tl) = tl {
153                    for d in tl {
154                        children.top_left.add_feature(d, Some(name.to_string()));
155                    }
156                }
157            }
158
159            if let Some(right) = right {
160                br = clip_features(&right, scale, j - k1, j + k3, Axis::Y, buffer);
161                tr = clip_features(&right, scale, j + k2, j + k4, Axis::Y, buffer);
162                if let Some(br) = br {
163                    for d in br {
164                        children.bottom_right.add_feature(d, Some(name.to_string()));
165                    }
166                }
167                if let Some(tr) = tr {
168                    for d in tr {
169                        children.top_right.add_feature(d, Some(name.to_string()));
170                    }
171                }
172            }
173        }
174
175        children
176    }
177}
178
179/// The children of a tile
180#[derive(Debug)]
181pub struct TileChildren<M = (), P: Clone + Default = Properties, D: Clone + Default = MValue> {
182    /// The bottom left child tile
183    pub bottom_left: Tile<M, P, D>,
184    /// The bottom right child tile
185    pub bottom_right: Tile<M, P, D>,
186    /// The top left child tile
187    pub top_left: Tile<M, P, D>,
188    /// The top right child tile
189    pub top_right: Tile<M, P, D>,
190}
191
192/// Layer Class to contain the layer information for splitting or simplifying
193#[derive(Debug, Clone, PartialEq)]
194pub struct Layer<M = (), P: Clone + Default = Properties, D: Clone + Default = MValue> {
195    /// the layer name
196    pub name: String,
197    /// the layer's features
198    pub features: Vec<VectorFeature<M, P, D>>,
199}
200impl<M, P: Clone + Default, D: Clone + Default> Layer<M, P, D> {
201    /// Create a new Layer
202    pub fn new(name: String) -> Self {
203        Self { name, features: vec![] }
204    }
205}
206
207/// Options for creating a TileStore
208#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
209pub struct TileStoreOptions {
210    /// manually set the projection, otherwise it defaults to whatever the data type is
211    pub projection: Option<Projection>,
212    /// min zoom to generate data on
213    pub minzoom: Option<u8>,
214    /// max zoom level to cluster the points on
215    pub maxzoom: Option<u8>,
216    /// tile buffer on each side in pixels
217    pub index_maxzoom: Option<u8>,
218    /// simplification tolerance (higher means simpler). Default is 3.
219    /// Note: this tolerance is measured against a 4_096x4_096 unit grid when applying simplification.
220    pub tolerance: Option<f64>,
221    /// tile buffer on each side so lines and polygons don't get clipped
222    pub buffer: Option<f64>,
223}
224
225/// TileStore Class is a tile-lookup system that splits and simplifies as needed for each tile request
226#[derive(Debug, Clone, PartialEq)]
227pub struct TileStore<
228    M: HasLayer + Clone = (),
229    P: Clone + Default = Properties,
230    D: Clone + Default = MValue,
231> {
232    /// min zoom to preserve detail on
233    pub minzoom: u8,
234    /// max zoom to preserve detail on
235    pub maxzoom: u8,
236    /// store which faces are active. 0 face could be entire WM projection
237    pub faces: BTreeSet<Face>,
238    /// max zoom in the tile index
239    pub index_maxzoom: u8,
240    /// simplification tolerance (higher means simpler)
241    pub tolerance: f64,
242    /// tile buffer for lines and polygons
243    pub buffer: f64,
244    /// stores both WM and S2 tiles
245    pub tiles: BTreeMap<CellId, Tile<M, P, D>>,
246    /// projection to build tiles for
247    pub projection: Projection,
248}
249impl<M: HasLayer + Clone, P: Clone + Default, D: Clone + Default> Default for TileStore<M, P, D> {
250    fn default() -> Self {
251        Self {
252            minzoom: 0,
253            maxzoom: 14,
254            faces: BTreeSet::<Face>::new(),
255            index_maxzoom: 4,
256            tolerance: 3. / 4_096.,
257            buffer: 0.0625,
258            tiles: BTreeMap::<CellId, Tile<M, P, D>>::new(),
259            projection: Projection::S2,
260        }
261    }
262}
263impl<M: HasLayer + Clone, P: Clone + Default, D: Clone + Default> TileStore<M, P, D>
264where
265    VectorFeature<M, P, D>: ConvertVectorFeatureWM<M, P, D> + ConvertVectorFeatureS2<M, P, D>,
266    Feature<M, P, D>: ConvertFeature<M, P, D>,
267{
268    /// Create a new TileStore
269    pub fn new(data: JSONCollection<M, P, D>, options: TileStoreOptions) -> Self {
270        let mut tile_store = Self {
271            minzoom: options.minzoom.unwrap_or(0),
272            maxzoom: options.maxzoom.unwrap_or(14),
273            faces: BTreeSet::<Face>::new(),
274            index_maxzoom: options.index_maxzoom.unwrap_or(4),
275            tolerance: options.tolerance.unwrap_or(3.) / 4_096.,
276            buffer: options.buffer.unwrap_or(64.),
277            tiles: BTreeMap::<CellId, Tile<M, P, D>>::new(),
278            projection: options.projection.unwrap_or(Projection::S2),
279        };
280        // sanity check
281        debug_assert!(
282            tile_store.minzoom <= tile_store.maxzoom
283                && tile_store.maxzoom > 0
284                && tile_store.maxzoom <= 20,
285            "maxzoom should be in the 0-20 range"
286        );
287        // convert features
288        let features: Vec<VectorFeature<M, P, D>> =
289            convert(tile_store.projection, &data, Some(true), Some(true));
290        features.into_iter().for_each(|feature| tile_store.add_feature(feature));
291        for i in 0..6 {
292            tile_store.split_tile(CellId::from_face(i), None, None);
293        }
294
295        tile_store
296    }
297
298    /// Add a feature to the tile store
299    fn add_feature(&mut self, mut feature: VectorFeature<M, P, D>) {
300        let face: u8 = feature.face.into();
301        let tile = self.tiles.entry(CellId::from_face(face)).or_insert_with(|| {
302            self.faces.insert(feature.face);
303            Tile::new(CellId::from_face(face))
304        });
305        // Prep Douglas-Peucker simplification by setting t-values.
306        build_sq_dists(&mut feature.geometry, self.tolerance, Some(self.maxzoom));
307
308        tile.add_feature(feature, None);
309    }
310
311    /// Split tiles given a range
312    fn split_tile(&mut self, start_id: CellId, end_id: Option<CellId>, end_zoom: Option<u8>) {
313        let TileStore { buffer, tiles, tolerance, maxzoom, index_maxzoom, .. } = self;
314        let end_zoom = end_zoom.unwrap_or(*maxzoom);
315        let mut stack: Vec<CellId> = vec![start_id];
316        // avoid recursion by using a processing queue
317        while !stack.is_empty() {
318            // find our next tile to split
319            let stack_id = stack.pop();
320            if stack_id.is_none() {
321                break;
322            }
323            let tile = tiles.get_mut(&stack_id.unwrap());
324            // if the tile we need does not exist, is empty, or already transformed, skip it
325            if tile.is_none() {
326                continue;
327            }
328            let tile = tile.unwrap();
329            if tile.is_empty() || tile.transformed {
330                continue;
331            }
332            let tile_zoom = tile.id.level();
333            // 1: stop tiling if we reached a defined end
334            // 2: stop tiling if it's the first-pass tiling, and we reached max zoom for indexing
335            // 3: stop at currently needed maxzoom OR current tile does not include child
336            if tile_zoom >= *maxzoom || // 1
337                (end_id.is_none() && tile_zoom >= *index_maxzoom) || // 2
338                (end_id.is_some() && (tile_zoom > end_zoom || !tile.id.contains(end_id.unwrap())))
339            {
340                continue;
341            }
342
343            // split the tile
344            let TileChildren {
345                bottom_left: bl_id,
346                bottom_right: br_id,
347                top_left: tl_id,
348                top_right: tr_id,
349            } = tile.split(Some(*buffer));
350            // now that the tile has been split, we can transform it
351            tile.transform(*tolerance, Some(*maxzoom));
352            // push the new features to the stack
353            stack.extend(vec![bl_id.id, br_id.id, tl_id.id, tr_id.id]);
354            // store the children
355            tiles.insert(bl_id.id, bl_id);
356            tiles.insert(br_id.id, br_id);
357            tiles.insert(tl_id.id, tl_id);
358            tiles.insert(tr_id.id, tr_id);
359        }
360    }
361
362    /// Get a tile
363    pub fn get_tile(&mut self, id: CellId) -> Option<&Tile<M, P, D>> {
364        let zoom = id.level();
365        let face = id.face();
366        // If the zoom is out of bounds, return nothing
367        if !(0..=20).contains(&zoom) || !self.faces.contains(&face.into()) {
368            return None;
369        }
370
371        // we want to find the closest tile to the data.
372        let mut p_id = id;
373        while !self.tiles.contains_key(&p_id) && !p_id.is_face() {
374            p_id = p_id.parent(None);
375        }
376        // split as necessary, the algorithm will know if the tile is already split
377        self.split_tile(p_id, Some(id), Some(zoom));
378
379        // grab the tile and split it if necessary
380        self.tiles.get(&id)
381    }
382}
383
384/// A trait for transforming a geometry from the 0->1 coordinate system to a tile coordinate system
385pub trait TransformVectorGeometry<M: Clone + Default = MValue> {
386    /// Transform the geometry from the 0->1 coordinate system to a tile coordinate system
387    fn transform(&mut self, zoom: f64, ti: f64, tj: f64);
388}
389impl<M: Clone + Default> TransformVectorGeometry<M> for VectorGeometry<M> {
390    /// Transform the geometry from the 0->1 coordinate system to a tile coordinate system
391    fn transform(&mut self, zoom: f64, ti: f64, tj: f64) {
392        let zoom = (1 << (zoom as u64)) as f64;
393        match self {
394            VectorGeometry::Point(p) => p.coordinates.transform(zoom, ti, tj),
395            VectorGeometry::LineString(l) | VectorGeometry::MultiPoint(l) => {
396                l.coordinates.iter_mut().for_each(|p| p.transform(zoom, ti, tj))
397            }
398            VectorGeometry::MultiLineString(l) | VectorGeometry::Polygon(l) => l
399                .coordinates
400                .iter_mut()
401                .for_each(|l| l.iter_mut().for_each(|p| p.transform(zoom, ti, tj))),
402            VectorGeometry::MultiPolygon(l) => l.coordinates.iter_mut().for_each(|p| {
403                p.iter_mut().for_each(|l| l.iter_mut().for_each(|p| p.transform(zoom, ti, tj)))
404            }),
405        }
406    }
407}
408impl<M: Clone + Default> TransformVectorGeometry<M> for VectorPoint<M> {
409    /// Transform the point from the 0->1 coordinate system to a tile coordinate system
410    fn transform(&mut self, zoom: f64, ti: f64, tj: f64) {
411        self.x = self.x * zoom - ti;
412        self.y = self.y * zoom - tj;
413    }
414}
gistools/data_structures/tile.rs

gistools/data_structures/
tile.rs
