K-d tree: Difference between revisions
Content deleted Content added
Updated output first D entry |
Updated first D entry |
||
Line 217:
import std.typecons, std.math, std.algorithm, std.random, std.range,
std.traits, core.memory;
/// k-dimensional point.
struct Point(size_t k, F) if (isFloatingPoint!F) {
F[k] data;
// alias data this; // kills DMD std.algorithm.swap inlining
F opIndex(in size_t i) const pure nothrow { return data[i]; }
void opIndexAssign(in F x, in size_t i) pure nothrow {
data[i] = x;
}
enum size_t length = k;
/// Square of the euclidean distance.
double sqd(in ref Point!(k, F) q) const pure nothrow {
double sum = 0;
foreach (immutable dim, immutable pCoord; data)
sum += (pCoord - q[dim]) ^^ 2;
return sum;
Line 244 ⟶ 247:
Point!(k, F) domElt;
immutable int split;
}
Line 262 ⟶ 265:
static KdNode!(k, F)* nk2(size_t split)(Point!(k, F)[] exset)
pure {
if (exset.empty)
return null;
if (exset.length == 1)
return new KdNode!(k, F)(exset[0], split, null, null);
// Pivot choosing procedure. We find median, then find
// largest index of points with median value. This
Line 280 ⟶ 285:
nk2!nextSplit(exset[m + 1 .. $]));
}
this.n = nk2!0(pts);
this.bounds = bounds_;
Line 296 ⟶ 302:
// counting the number nodes visited.
static Tuple!(Point!(k, F), "nearest",
int, "nodesVisited")
nn(KdNode!(k, F)* kd, in Point!(k, F) target,
Orthotope!(k, F) hr,
if (kd == null)
return typeof(return)(Point!(k, F)(),
int nodesVisited = 1;
Line 314 ⟶ 320:
Orthotope!(k, F) nearerHr, furtherHr;
if (target[s] <= pivot[s]) {
//nearerKd, nearerHr = kd.left, leftHr;
//furtherKd, furtherHr = kd.right, rightHr;
nearerKd = kd.left;
nearerHr = leftHr;
Line 321 ⟶ 327:
furtherHr = rightHr;
} else {
//nearerKd, nearerHr = kd.right, rightHr;
//furtherKd, furtherHr = kd.left, leftHr;
nearerKd = kd.right;
nearerHr = rightHr;
Line 356 ⟶ 362:
}
return nn(t.n, p, t.bounds,
}
void showNearest(size_t k, F)(in string heading, KdTree!(k, F) kd,
in Point!(k, F) p) {
import std.stdio: writeln;
writeln(heading, ":");
writeln("Point: ", p);
Line 373 ⟶ 379:
static Point!(k, F) randomPoint(size_t k, F)() {
typeof(return) result;
foreach (immutable i; 0 .. k)
result[i] = uniform(cast(F)0, cast(F)1);
return result;
}
static Point!(k, F)[] randomPoints(size_t k, F)(in
return
}
Line 385 ⟶ 391:
rndGen.seed(1); // For repeatable outputs.
alias D2 = TypeTuple!(2, double)
alias P = Point!D2
auto kd1 = KdTree!D2([P([2, 3]), P([5, 4]), P([9, 6]),
P([4, 7]), P([8, 1]), P([7, 2])],
Line 393 ⟶ 399:
enum int N = 400_000;
alias F3 = TypeTuple!(3, float)
alias Q = Point!F3
StopWatch sw;
sw.start;
auto kd2 = KdTree!F3(randomPoints!F3(N),
Orthotope!F3(Q([0, 0, 0]), Q([1, 1, 1])));
sw.stop
GC.enable;
showNearest(text("k-d tree with ", N,
" random 3D ", F3[1].stringof,
" points (construction time: ",
sw.peek
sw.reset
sw.start
enum int M = 10_000;
size_t visited = 0;
foreach (immutable _; 0 .. M) {
immutable n = kd2.findNearest(randomPoint!F3
visited += n.nodesVisited;
}
sw.stop
writefln("Visited an average of %0.2f nodes on %d searches " ~
"in %
}</lang>
{{out|Output, using the ldc2 compiler}}
<pre>Wikipedia example data:
Line 439 ⟶ 433:
Nodes visited: 3
k-d tree with 400000 random 3D float points (construction time:
Point: const(Point!(3, float))([0.22012, 0.984514, 0.698782])
Nearest neighbor: immutable(Point!(3, float))([0.225766, 0.978981, 0.69885])
Line 445 ⟶ 439:
Nodes visited: 54
Visited an average of 43.10 nodes on 10000 searches in
===Faster Alternative Version===
|