nearest

Finds the neares neighbor in the kd tree using euclidean distance metric. root must not be empty.

pure nothrow @nogc

const(T[k])

nearest

(

size_t k

)

(

in KDNode!(k, T)* root

in auto ref T[k] point

)

Examples

Test build and nearest

import fluent.asserts : should;
import std.algorithm : minElement;
import std.numeric : euclideanDistance;
import std.random : uniform01;

auto points = new double[3][1000];
foreach (i; 0 .. points.length) {
	foreach (j; 0 .. points[i].length) {
		points[i][j] = uniform01;
	}
}

auto root = kdTree(points);
root.size.should.equal(points.length);

foreach (_; 0 .. 1000) {
	double[3] point = [uniform01, uniform01, uniform01];

	root.nearest(point).should.equal(points.minElement!(a => a[0 .. $].euclideanDistance(point[0 .. $])));
}

Test add and nearest

import fluent.asserts : should;
import std.algorithm : minElement;
import std.numeric : euclideanDistance;
import std.random : uniform01;

auto points = new double[3][1000];
foreach (i; 0 .. points.length) {
	foreach (j; 0 .. points[i].length) {
		points[i][j] = uniform01;
	}
}

auto root = kdTree!(3, double);
foreach (i; 0 .. points.length) {
	root.add(points[i]);
}
root.size.should.equal(points.length);

foreach (_; 0 .. 1000) {
	double[3] point = [uniform01, uniform01, uniform01];

	root.nearest(point).should.equal(points.minElement!(a => a[].euclideanDistance(point[])));
}

Test rebalance

import fluent.asserts : should;
import std.algorithm : minElement;
import std.numeric : euclideanDistance;
import std.random : uniform01;

auto points = new double[3][1000];
foreach (i; 0 .. points.length) {
	foreach (j; 0 .. points[i].length) {
		points[i][j] = uniform01;
	}
}

auto root = kdTree!(3, double);
foreach (i; 0 .. points.length) {
	root.add(points[i]);
}
root.size.should.equal(points.length);

root.rebalance();
root.size.should.equal(points.length);

foreach (_; 0 .. 1000) {
	double[3] point = [uniform01, uniform01, uniform01];

	root.nearest(point).should.equal(points.minElement!(a => a[].euclideanDistance(point[])));
}

Test nearest on empty tree

import fluent.asserts : should;
import core.exception : AssertError;

auto root = kdTree!(3, double);
root.nearest([0.0, 0.0, 0.0]).should.throwException!AssertError.withMessage.equal("tree is empty");

nearest

Examples

Meta

Source