From a6e586d3f1368e4ecbe56b6481e8bca2ec8e7bb9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Wed, 27 May 2020 13:55:59 -0400
Subject: kd: Implement k-d trees

---
 benches/benches.rs | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'benches')

diff --git a/benches/benches.rs b/benches/benches.rs
index a8676ba..8464179 100644
--- a/benches/benches.rs
+++ b/benches/benches.rs
@@ -2,6 +2,7 @@
 
 use acap::euclid::Euclidean;
 use acap::exhaustive::ExhaustiveSearch;
+use acap::kd::KdTree;
 use acap::vp::{FlatVpTree, VpTree};
 use acap::NearestNeighbors;
 
@@ -37,6 +38,7 @@ fn bench_from_iter(c: &mut Criterion) {
     group.bench_function("ExhaustiveSearch", |b| b.iter(|| ExhaustiveSearch::from_iter(points.clone())));
     group.bench_function("VpTree", |b| b.iter(|| VpTree::from_iter(points.clone())));
     group.bench_function("FlatVpTree", |b| b.iter(|| FlatVpTree::from_iter(points.clone())));
+    group.bench_function("KdTree", |b| b.iter(|| KdTree::from_iter(points.clone())));
     group.finish();
 }
 
@@ -47,29 +49,34 @@ fn bench_nearest_neighbors(c: &mut Criterion) {
     let exhaustive = ExhaustiveSearch::from_iter(points.clone());
     let vp_tree = VpTree::from_iter(points.clone());
     let flat_vp_tree = FlatVpTree::from_iter(points.clone());
+    let kd_tree = KdTree::from_iter(points.clone());
 
     let mut nearest = c.benchmark_group("NearestNeighbors::nearest");
     nearest.bench_function("ExhaustiveSearch", |b| b.iter(|| exhaustive.nearest(&target)));
     nearest.bench_function("VpTree", |b| b.iter(|| vp_tree.nearest(&target)));
     nearest.bench_function("FlatVpTree", |b| b.iter(|| flat_vp_tree.nearest(&target)));
+    nearest.bench_function("KdTree", |b| b.iter(|| kd_tree.nearest(&target)));
     nearest.finish();
 
     let mut nearest_within = c.benchmark_group("NearestNeighbors::nearest_within");
     nearest_within.bench_function("ExhaustiveSearch", |b| b.iter(|| exhaustive.nearest_within(&target, 0.1)));
     nearest_within.bench_function("VpTree", |b| b.iter(|| vp_tree.nearest_within(&target, 0.1)));
     nearest_within.bench_function("FlatVpTree", |b| b.iter(|| flat_vp_tree.nearest_within(&target, 0.1)));
+    nearest_within.bench_function("KdTree", |b| b.iter(|| kd_tree.nearest_within(&target, 0.1)));
     nearest_within.finish();
 
     let mut k_nearest = c.benchmark_group("NearestNeighbors::k_nearest");
     k_nearest.bench_function("ExhaustiveSearch", |b| b.iter(|| exhaustive.k_nearest(&target, 3)));
     k_nearest.bench_function("VpTree", |b| b.iter(|| vp_tree.k_nearest(&target, 3)));
     k_nearest.bench_function("FlatVpTree", |b| b.iter(|| flat_vp_tree.k_nearest(&target, 3)));
+    k_nearest.bench_function("KdTree", |b| b.iter(|| kd_tree.k_nearest(&target, 3)));
     k_nearest.finish();
 
     let mut k_nearest_within = c.benchmark_group("NearestNeighbors::k_nearest_within");
     k_nearest_within.bench_function("ExhaustiveSearch", |b| b.iter(|| exhaustive.k_nearest_within(&target, 3, 0.1)));
     k_nearest_within.bench_function("VpTree", |b| b.iter(|| vp_tree.k_nearest_within(&target, 3, 0.1)));
     k_nearest_within.bench_function("FlatVpTree", |b| b.iter(|| flat_vp_tree.k_nearest_within(&target, 3, 0.1)));
+    k_nearest_within.bench_function("KdTree", |b| b.iter(|| kd_tree.k_nearest_within(&target, 3, 0.1)));
     k_nearest_within.finish();
 }
 
-- 
cgit v1.2.3