gistools/geometry/
tile.rs

1use alloc::collections::{BTreeMap, BTreeSet};
2use alloc::string::String;
3use alloc::string::ToString;
4use alloc::vec;
5use alloc::vec::Vec;
6
7use libm::round;
8
9use crate::{
10    convert, CellId, Face, JSONCollection, Projection, TileChildren, VectorFeature, VectorGeometry,
11    VectorPoint,
12};
13
14/// If a user creates metadata for a VectorFeature, it needs to define a get_layer function
15pub trait HasLayer {
16    /// Get the layer from metadata if it exists
17    fn get_layer(&self) -> Option<String>;
18}
19impl HasLayer for () {
20    fn get_layer(&self) -> Option<String> {
21        None
22    }
23}
24
25/// Tile Class to contain the tile information for splitting or simplifying
26pub struct Tile<M> {
27    /// the tile id
28    pub id: CellId,
29    /// the tile's layers
30    pub layers: BTreeMap<String, Layer<M>>,
31    /// whether the tile feature geometry has been transformed
32    pub transformed: bool,
33}
34impl<M: HasLayer + Clone> Tile<M> {
35    /// Create a new Tile
36    pub fn new(id: CellId) -> Self {
37        Self { id, layers: BTreeMap::new(), transformed: false }
38    }
39
40    /// Returns true if the tile is empty of features
41    pub fn is_empty(&self) -> bool {
42        for layer in self.layers.values() {
43            if !layer.features.is_empty() {
44                return false;
45            }
46        }
47
48        true
49    }
50
51    /// Add a feature to the tile
52    pub fn add_feature(&mut self, feature: VectorFeature<M>, layer: Option<String>) {
53        let layer_name = feature
54            .metadata
55            .as_ref()
56            .and_then(|meta| meta.get_layer()) // Get the layer from metadata if it exists
57            .or(layer) // Fall back to the provided layer
58            .unwrap_or_else(|| "default".to_string()); // Fall back to "default" if none found
59
60        if !self.layers.contains_key(&layer_name) {
61            self.layers.insert(layer_name.clone(), Layer::new(layer_name.clone()));
62        }
63        self.layers.get_mut(&layer_name).unwrap().features.push(feature);
64    }
65
66    /// Simplify the geometry to have a tolerance which will be relative to the tile's zoom level.
67    /// NOTE: This should be called after the tile has been split into children if that functionality
68    /// is needed.
69    pub fn transform(&mut self, tolerance: f64, maxzoom: Option<u8>) {
70        if self.transformed {
71            return;
72        }
73        let (zoom, i, j) = self.id.to_zoom_ij(None);
74
75        for layer in self.layers.values_mut() {
76            for feature in layer.features.iter_mut() {
77                feature.geometry.simplify(tolerance, zoom, maxzoom);
78                feature.geometry.transform(zoom, i as f64, j as f64)
79            }
80        }
81
82        self.transformed = true;
83    }
84}
85
86/// Layer Class to contain the layer information for splitting or simplifying
87pub struct Layer<M> {
88    /// the layer name
89    pub name: String,
90    /// the layer's features
91    pub features: Vec<VectorFeature<M>>,
92}
93impl<M> Layer<M> {
94    /// Create a new Layer
95    pub fn new(name: String) -> Self {
96        Self { name, features: vec![] }
97    }
98}
99
100/// Options for creating a TileStore
101pub struct TileStoreOptions {
102    /// manually set the projection, otherwise it defaults to whatever the data type is
103    pub projection: Option<Projection>,
104    /// min zoom to generate data on
105    pub minzoom: Option<u8>,
106    /// max zoom level to cluster the points on
107    pub maxzoom: Option<u8>,
108    /// tile buffer on each side in pixels
109    pub index_maxzoom: Option<u8>,
110    /// simplification tolerance (higher means simpler)
111    pub tolerance: Option<f64>,
112    /// tile buffer on each side so lines and polygons don't get clipped
113    pub buffer: Option<f64>,
114}
115
116/// TileStore Class is a tile-lookup system that splits and simplifies as needed for each tile request */
117pub struct TileStore<M: HasLayer + Clone> {
118    minzoom: u8,                      // min zoom to preserve detail on
119    maxzoom: u8,                      // max zoom to preserve detail on
120    faces: BTreeSet<Face>, // store which faces are active. 0 face could be entire WM projection
121    index_maxzoom: u8,     // max zoom in the tile index
122    tolerance: f64,        // simplification tolerance (higher means simpler)
123    buffer: f64,           // tile buffer for lines and polygons
124    tiles: BTreeMap<CellId, Tile<M>>, // stores both WM and S2 tiles
125    projection: Projection, // projection to build tiles for
126}
127impl<M: HasLayer + Clone> Default for TileStore<M> {
128    fn default() -> Self {
129        Self {
130            minzoom: 0,
131            maxzoom: 18,
132            faces: BTreeSet::<Face>::new(),
133            index_maxzoom: 4,
134            tolerance: 3.,
135            buffer: 0.0625,
136            tiles: BTreeMap::<CellId, Tile<M>>::new(),
137            projection: Projection::S2,
138        }
139    }
140}
141impl<M: HasLayer + Clone> TileStore<M> {
142    /// Create a new TileStore
143    pub fn new(data: JSONCollection<M>, options: TileStoreOptions) -> Self {
144        let mut tile_store = Self {
145            minzoom: options.minzoom.unwrap_or(0),
146            maxzoom: options.maxzoom.unwrap_or(20),
147            faces: BTreeSet::<Face>::new(),
148            index_maxzoom: options.index_maxzoom.unwrap_or(4),
149            tolerance: options.tolerance.unwrap_or(3.),
150            buffer: options.buffer.unwrap_or(64.),
151            tiles: BTreeMap::<CellId, Tile<M>>::new(),
152            projection: options.projection.unwrap_or(Projection::S2),
153        };
154        // sanity check
155        debug_assert!(
156            tile_store.minzoom <= tile_store.maxzoom
157                && tile_store.maxzoom > 0
158                && tile_store.maxzoom <= 20,
159            "maxzoom should be in the 0-20 range"
160        );
161        // convert features
162        let features: Vec<VectorFeature<M>> = convert(
163            tile_store.projection,
164            &data,
165            Some(tile_store.tolerance),
166            Some(tile_store.maxzoom),
167            None,
168        );
169        features.into_iter().for_each(|feature| tile_store.add_feature(feature));
170        for i in 0..6 {
171            tile_store.split_tile(CellId::from_face(i), None, None);
172        }
173
174        tile_store
175    }
176
177    /// Add a feature to the tile store
178    pub fn add_feature(&mut self, feature: VectorFeature<M>) {
179        let face: u8 = feature.face.into();
180        let tile = self.tiles.entry(CellId::from_face(face)).or_insert_with(|| {
181            self.faces.insert(feature.face);
182            Tile::new(CellId::from_face(face))
183        });
184
185        tile.add_feature(feature, None);
186    }
187
188    /// Split tiles given a range
189    fn split_tile(&mut self, start_id: CellId, end_id: Option<CellId>, end_zoom: Option<u8>) {
190        let TileStore { buffer, tiles, tolerance, maxzoom, index_maxzoom, .. } = self;
191        let end_zoom = end_zoom.unwrap_or(*maxzoom);
192        let mut stack: Vec<CellId> = vec![start_id];
193        // avoid recursion by using a processing queue
194        while !stack.is_empty() {
195            // find our next tile to split
196            let stack_id = stack.pop();
197            if stack_id.is_none() {
198                break;
199            }
200            let tile = tiles.get_mut(&stack_id.unwrap());
201            // if the tile we need does not exist, is empty, or already transformed, skip it
202            if tile.is_none() {
203                continue;
204            }
205            let tile = tile.unwrap();
206            if tile.is_empty() || tile.transformed {
207                continue;
208            }
209            let tile_zoom = tile.id.level();
210            // 1: stop tiling if we reached a defined end
211            // 2: stop tiling if it's the first-pass tiling, and we reached max zoom for indexing
212            // 3: stop at currently needed maxzoom OR current tile does not include child
213            if tile_zoom >= *maxzoom || // 1
214                (end_id.is_none() && tile_zoom >= *index_maxzoom) || // 2
215                (end_id.is_some() && (tile_zoom > end_zoom || !tile.id.contains(&end_id.unwrap())))
216            {
217                continue;
218            }
219
220            // split the tile
221            let TileChildren {
222                bottom_left: bl_id,
223                bottom_right: br_id,
224                top_left: tl_id,
225                top_right: tr_id,
226            } = tile.split(Some(*buffer));
227            // now that the tile has been split, we can transform it
228            tile.transform(*tolerance, Some(*maxzoom));
229            // push the new features to the stack
230            stack.extend(vec![bl_id.id, br_id.id, tl_id.id, tr_id.id]);
231            // store the children
232            tiles.insert(bl_id.id, bl_id);
233            tiles.insert(br_id.id, br_id);
234            tiles.insert(tl_id.id, tl_id);
235            tiles.insert(tr_id.id, tr_id);
236        }
237    }
238
239    /// Get a tile
240    pub fn get_tile(&mut self, id: CellId) -> Option<&Tile<M>> {
241        let zoom = id.level();
242        let face = id.face();
243        // If the zoom is out of bounds, return nothing
244        if !(0..=20).contains(&zoom) || !self.faces.contains(&face.into()) {
245            return None;
246        }
247
248        // we want to find the closest tile to the data.
249        let mut p_id = id;
250        while !self.tiles.contains_key(&p_id) && !p_id.is_face() {
251            p_id = p_id.parent(None);
252        }
253        // split as necessary, the algorithm will know if the tile is already split
254        self.split_tile(p_id, Some(id), Some(zoom));
255
256        // grab the tile and split it if necessary
257        self.tiles.get(&id)
258    }
259}
260
261impl VectorGeometry {
262    /// Transform the geometry from the 0->1 coordinate system to a tile coordinate system
263    pub fn transform(&mut self, zoom: u8, ti: f64, tj: f64) {
264        let zoom = (1 << (zoom as u64)) as f64;
265        match self {
266            VectorGeometry::Point(p) => p.coordinates.transform(zoom, ti, tj),
267            VectorGeometry::LineString(l) | VectorGeometry::MultiPoint(l) => {
268                l.coordinates.iter_mut().for_each(|p| p.transform(zoom, ti, tj))
269            }
270            VectorGeometry::MultiLineString(l) | VectorGeometry::Polygon(l) => l
271                .coordinates
272                .iter_mut()
273                .for_each(|l| l.iter_mut().for_each(|p| p.transform(zoom, ti, tj))),
274            VectorGeometry::MultiPolygon(l) => l.coordinates.iter_mut().for_each(|p| {
275                p.iter_mut().for_each(|l| l.iter_mut().for_each(|p| p.transform(zoom, ti, tj)))
276            }),
277        }
278    }
279}
280
281impl VectorPoint {
282    /// Transform the point from the 0->1 coordinate system to a tile coordinate system
283    pub fn transform(&mut self, zoom: f64, ti: f64, tj: f64) {
284        self.x = round(self.x * zoom - ti);
285        self.y = round(self.y * zoom - tj);
286    }
287}
gistools/geometry/tile.rs

gistools/geometry/
tile.rs
