utiles_core/
merge.rs

1use crate::traits::TileChildren1;
2use crate::TileParent;
3use std::collections::{HashMap, HashSet};
4use std::fmt::Debug;
5use std::hash::Hash;
6
7/// Merge a set of tiles into a simplified set of tiles
8///
9#[must_use]
10pub fn merge<T: TileParent + Copy + Eq + Hash, S: std::hash::BuildHasher>(
11    merge_set: &HashSet<T, S>,
12    minzoom: Option<u8>,
13) -> (HashSet<T>, bool) {
14    let minzoom = minzoom.unwrap_or(0);
15    let mut upwards_merge: HashMap<T, HashSet<T>> = HashMap::new();
16    let mut current_tileset: HashSet<T> = HashSet::default();
17    let mut changed = false;
18
19    for tile in merge_set {
20        if tile.z() > minzoom {
21            if let Some(tile_parent) = tile.parent(None) {
22                upwards_merge.entry(tile_parent).or_default().insert(*tile);
23            }
24        } else {
25            // Tiles at minzoom or lower are added directly
26            current_tileset.insert(*tile);
27        }
28    }
29
30    for (supertile, children) in upwards_merge {
31        if children.len() == 4 && supertile.z() >= minzoom {
32            current_tileset.insert(supertile);
33            changed = true;
34        } else {
35            current_tileset.extend(children);
36        }
37    }
38
39    (current_tileset, changed)
40}
41
42/// Tiles at or below the `minzoom` level will not be merged into their parents.
43/// Simplify a set of tiles merging children into parents
44///
45/// TODO: Add `minzoom` and `maxzoom` parameters
46#[must_use]
47pub fn simplify_v1<
48    T: TileParent + Copy + Eq + Hash,
49    S: std::hash::BuildHasher + Default,
50>(
51    tiles: &HashSet<T, S>,
52    minzoom: Option<u8>,
53) -> HashSet<T> {
54    let minzoom = minzoom.unwrap_or(0);
55    let mut tilesv: Vec<&T> = tiles.iter().collect();
56    tilesv.sort_by_key(|t| t.z());
57
58    let mut root_set: HashSet<T> = HashSet::with_capacity(tiles.len());
59
60    'outer: for tile in tilesv {
61        // Tiles at minzoom or lower are added directly
62        if tile.z() <= minzoom {
63            root_set.insert(*tile);
64            continue 'outer;
65        }
66
67        // Check if any parent tile at zoom levels from minzoom to tile.z() -1 exists in root_set
68        for i in (minzoom..tile.z()).rev() {
69            if let Some(par) = tile.parent(Some(i)) {
70                if root_set.contains(&par) {
71                    continue 'outer;
72                }
73            }
74        }
75
76        root_set.insert(*tile);
77    }
78
79    let mut is_merging = true;
80    while is_merging {
81        let (new_set, changed) = merge(&root_set, Some(minzoom));
82        root_set = new_set;
83        is_merging = changed;
84    }
85
86    root_set
87}
88
89struct TileMerger<T: TileParent + TileChildren1> {
90    coverage_map: HashSet<T>,
91    minzoom: u8,
92}
93
94impl<T: TileParent + TileChildren1 + Eq + Hash + Copy + Sized + Debug> TileMerger<T> {
95    fn new(minzoom: u8) -> Self {
96        Self {
97            coverage_map: HashSet::new(),
98            minzoom,
99        }
100    }
101
102    fn has_tile_or_parent(&self, tile: &T) -> bool {
103        self.coverage_map.contains(tile)
104            || tile
105                .iter_parents()
106                .any(|el| self.coverage_map.contains(&el))
107    }
108
109    fn put(&mut self, tile: &T) -> bool {
110        if self.has_tile_or_parent(tile) {
111            true
112        } else {
113            self.coverage_map.insert(*tile);
114            self.attempt_merge(*tile);
115            false
116        }
117    }
118    // fn attempt_merge(&mut self, tile: T) {
119    //     tile.iter_parents().find_map(|parent_tile| {
120    //         let siblings = parent_tile.children1();
121    //
122    //         if siblings.iter().all(|sibling| self.coverage_map.contains(sibling)) {
123    //             siblings.iter().for_each(|sibling| {
124    //                 self.coverage_map.remove(sibling);
125    //             });
126    //             self.coverage_map.insert(parent_tile);
127    //             None // Continue merging, return None so the iteration continues
128    //         } else {
129    //             Some(()) // Stop merging, return Some to break the iteration
130    //         }
131    //     });
132    // }
133    /// Attempts to merge the tile upwards, respecting the `minzoom` limit.
134    fn attempt_merge(&mut self, tile: T) {
135        for parent_tile in tile.iter_parents() {
136            // Stop merging if parent tile is at or below minzoom
137            if parent_tile.z() < self.minzoom {
138                break;
139            }
140
141            let siblings = parent_tile.children1();
142
143            if siblings
144                .iter()
145                .all(|sibling| self.coverage_map.contains(sibling))
146            {
147                for sibling in &siblings {
148                    self.coverage_map.remove(sibling);
149                }
150                self.coverage_map.insert(parent_tile);
151            } else {
152                // Cannot merge further upwards
153                break;
154            }
155        }
156    }
157}
158
159#[must_use]
160pub fn simplify<T: TileParent + TileChildren1 + Debug, S: std::hash::BuildHasher>(
161    tiles: &HashSet<T, S>,
162    minzoom: Option<u8>,
163) -> HashSet<T> {
164    let mut tiles_vec: Vec<_> = tiles.iter().collect();
165    tiles_vec.sort_by_key(|a| a.z());
166    let mut merger = TileMerger::new(minzoom.unwrap_or(0));
167    for tile in tiles_vec {
168        merger.put(tile);
169    }
170    merger.coverage_map
171}
utiles_core/merge.rs

utiles_core/
merge.rs
