utiles_core/
merge.rs

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

utiles_core/
merge.rs
