a

1 files changed, 131 insertions, 0 deletions

diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..065fa0d
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,131 @@
+use anyhow::Result;
+use glam::DVec3;
+use indicatif::ProgressIterator;
+use log::{debug, info};
+use osm_pbf_reader::{Blobs, data::primitives::Primitive};
+use rayon::iter::{ParallelBridge, ParallelIterator};
+use std::{collections::HashMap, env::args, f64::consts::PI};
+
+fn main() -> Result<()> {
+    env_logger::init_from_env("LOG");
+    let inpath = args().nth(1).unwrap();
+
+    let node_positions = Blobs::from_path(&inpath)?
+        .progress_count(1_500)
+        .par_bridge()
+        .map(|e| {
+            let mut e = e.unwrap();
+            let e = e.decode().unwrap();
+            let mut npos = Vec::new();
+            for p in e.primitives() {
+                if let Primitive::Node(n) = p {
+                    let lat = n.nano_lat as f64 / 1_000_000_000. / 180. * PI;
+                    let lon = n.nano_lon as f64 / 1_000_000_000. / 180. * PI;
+                    let pos = DVec3::new(lat.sin() * lon.cos(), lon.sin(), lat.cos() * lon.cos());
+                    npos.push((n.id, pos));
+                };
+            }
+            npos
+        })
+        .fold(
+            || HashMap::new(),
+            |mut a, b| {
+                a.extend(b);
+                a
+            },
+        )
+        .reduce(
+            || HashMap::new(),
+            |mut a, b| {
+                if !a.is_empty() && !b.is_empty() {
+                    debug!("merge positions {} + {}", a.len(), b.len());
+                }
+                a.extend(b);
+                a
+            },
+        );
+
+    let mut tree = MTree::default();
+    info!("Building M-Tree over node positions...");
+    for (id, pos) in node_positions.into_iter().progress() {
+        tree.insert(pos, id);
+    }
+    info!("Done, depth={}", tree.depth());
+    // Blobs::from_path(&inpath)?
+    //     .progress_count(1_500)
+    //     .par_bridge()
+    //     .map(|e| {
+    //         let mut e = e.unwrap();
+    //         let e = e.decode().unwrap();
+    //         for p in e.primitives() {
+    //             if let Primitive::Node(n) = p {
+
+    //             }
+    //         }
+    //     })
+    //     .for_each(|_| ());
+
+    Ok(())
+}
+
+type NodeID = i64;
+
+struct MTree {
+    center: DVec3,
+    radius: f64,
+    nodes: Vec<(DVec3, NodeID)>,
+    children: Vec<MTree>,
+}
+impl Default for MTree {
+    fn default() -> Self {
+        Self {
+            center: DVec3::ZERO,
+            radius: 0.,
+            nodes: Vec::new(),
+            children: Vec::new(),
+        }
+    }
+}
+impl MTree {
+    pub fn insert(&mut self, pos: DVec3, id: NodeID) {
+        if self.children.is_empty() {
+            self.nodes.push((pos, id));
+            if self.nodes.len() > 16 {
+                for (pos, id) in self.nodes.drain(..) {
+                    self.children.push(MTree {
+                        center: pos,
+                        radius: 0.,
+                        nodes: vec![(pos, id)],
+                        children: Vec::new(),
+                    });
+                }
+            }
+        } else {
+            let mut min_dist = f64::MAX;
+            let mut min_index = 0;
+            for (i, c) in self.children.iter().enumerate() {
+                let d = c.center.distance_squared(pos);
+                if d < min_dist {
+                    min_index = i;
+                    min_dist = d;
+                }
+            }
+            self.radius = self.radius.max(min_dist.sqrt());
+            self.children[min_index].insert(pos, id);
+        }
+    }
+    pub fn depth(&self) -> usize {
+        self.children.iter().map(|c| c.depth()).max().unwrap_or(0) + 1
+    }
+}
+
+enum Elem {
+    Node { pos: DVec3 },
+}
+impl Elem {
+    pub fn center(&self) -> DVec3 {
+        match self {
+            Elem::Node { pos } => *pos,
+        }
+    }
+}