sphere-knn 0.1.0

fast nearest-neighbor lookups on a sphere. This is useful if, for example, you have a database of geographic points (latitude, longitude) and want to swiftly look up which of those points are near a given latitude, longitude pair.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::fmt::Debug;

use crate::lla_node::{LLANode, LocationData, NodeOrData};

fn build<T: Clone + Debug>(mut nodes: Vec<LocationData<T>>, mut depth: usize) -> NodeOrData<T> {
    if nodes.len() == 1 {
        return NodeOrData::Data(nodes[0].clone());
    }

    let axis = depth % nodes[0].position.len();
    nodes.sort_by(|a, b| a.position[axis].partial_cmp(&b.position[axis]).unwrap());
    let median = (nodes.len() as f64 * 0.5).floor() as usize;
    depth += 1;
    return NodeOrData::Node(LLANode {
        axis,
        split: nodes[median].position[axis] as f64,
        left: Box::new(build(nodes[0..median].to_vec(), depth)),
        right: Box::new(build(nodes[median..].to_vec(), depth)),
    });
}

pub fn build_tree<T: Clone + Debug>(nodes: Vec<LocationData<T>>) -> NodeOrData<T> {
    build(nodes, 0)
}