knn/
lib.rs

1#![warn(rust_2018_idioms)]
2#![warn(missing_docs)]
3
4//! # KNN
5//!
6//! `knn` provides for fast method of finding exact k nearest neighbours
7//! for higher dimensional data. Also supports custom distance function.
8
9mod heap;
10
11#[derive(Clone)]
12/// The core datastructure of the package.
13/// Stores the points and the distance function.
14pub struct PointCloud<'a, T> {
15    // stores all points
16    points: Vec<&'a T>,
17
18    // return the distance given 2 ponints
19    dist_fn: fn(&T, &T) -> f64,
20}
21
22impl<'a, T> PointCloud<'a, T> {
23    /// Constructs a new `PointCloud<T>`.
24    ///
25    /// It accepts a function to compute distance between any 2 objects.
26    ///
27    /// # Examples
28    /// ```
29    /// extern crate knn;
30    /// use knn::PointCloud;
31    /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()};
32    /// let pc = PointCloud::new(manhattan_dist);
33    /// ```
34    pub fn new(dist_fn: fn(&T, &T) -> f64) -> Self {
35        Self {
36            points: Vec::new(),
37            dist_fn: dist_fn,
38        }
39    }
40
41    /// Adds a point to the PointCloud.
42    ///
43    /// It accepts a reference to an object.
44    ///
45    /// # Examples
46    /// ```
47    /// extern crate knn;
48    /// use knn::PointCloud;
49    /// let dummy_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {0.0};
50    /// let mut pc = PointCloud::new(dummy_dist);
51    /// let p = [1.89, 5.63];
52    /// pc.add_point(&p);
53    /// ```
54    pub fn add_point(&mut self, p: &'a T) {
55        self.points.push(p)
56    }
57
58    /// Gets the k nearest neighbours of an object.
59    ///
60    /// It accepts a reference to the object and how many neighbours to return.
61    ///
62    /// # Example
63    /// ```
64    /// extern crate knn;
65    /// use knn::PointCloud;
66    /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()};
67    /// let mut pc = PointCloud::new(manhattan_dist);
68    /// let points = vec![[1.0, 1.0], [2.0, 2.0], [3.0, 2.0]];
69    /// for p in &points {
70    ///     pc.add_point(&p);
71    /// }
72    /// let q = [0.5, 0.5];
73    /// pc.get_nearest_k(&q, 2);
74    ///
75    /// ```
76    pub fn get_nearest_k(&self, p: &T, k: usize) -> Vec<(f64, &T)> {
77        let mut h = heap::Heap::new(k);
78        for i in 0..self.points.len() {
79            let d = (self.dist_fn)(self.points[i], p);
80            h.insert(d, &self.points[i]);
81        }
82        let mut knn = Vec::new();
83        for i in h.get_elements() {
84            knn.push((i.0, *i.1));
85        }
86        knn
87    }
88
89    /// Get the len / number of objects in PointCloud
90    /// Example:
91    /// ```
92    /// extern crate knn;
93    /// use knn::PointCloud;
94    /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()};
95    /// let mut pc = PointCloud::new(manhattan_dist);
96    /// let points = vec![[1.0, 1.0], [2.0, 2.0], [3.0, 2.0]];
97    /// for p in &points {
98    ///     pc.add_point(&p);
99    /// }
100    /// pc.len();
101    /// ```
102    pub fn len(&self) -> usize {
103        self.points.len()
104    }
105}
knn/lib.rs

knn/
lib.rs
