K-d tree: Difference between revisions

Content added Content deleted
m (Explicit string concat in second D entry)
(Updated D entry)
Line 227: Line 227:


/// Square of the euclidean distance.
/// Square of the euclidean distance.
double sqd(in ref Point!(k, F) q) const pure nothrow {
double sqd(in ref Point!(k, F) q) const pure nothrow @nogc {
double sum = 0;
double sum = 0;
foreach (immutable dim, immutable pCoord; data)
foreach (immutable dim, immutable pCoord; data)
Line 292: Line 292:
*/
*/
auto findNearest(size_t k, F)(KdTree!(k, F) t, in Point!(k, F) p)
auto findNearest(size_t k, F)(KdTree!(k, F) t, in Point!(k, F) p)
pure nothrow {
pure nothrow @nogc {
// Algorithm is table 6.4 from the paper, with the addition of
// Algorithm is table 6.4 from the paper, with the addition of
// counting the number nodes visited.
// counting the number nodes visited.
Line 299: Line 299:
int, "nodesVisited")
int, "nodesVisited")
nn(KdNode!(k, F)* kd, in Point!(k, F) target,
nn(KdNode!(k, F)* kd, in Point!(k, F) target,
Orthotope!(k, F) hr, F maxDistSqd) pure nothrow {
Orthotope!(k, F) hr, F maxDistSqd) pure nothrow @nogc {
if (kd == null)
if (kd == null)
return typeof(return)(Point!(k, F)(), F.infinity, 0);
return typeof(return)(Point!(k, F)(), F.infinity, 0);
Line 455: Line 455:


// See QuickSelect method.
// See QuickSelect method.
KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow {
KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow @nogc {
auto start = nodes.ptr;
auto start = nodes.ptr;
auto end = &nodes[$ - 1] + 1;
auto end = &nodes[$ - 1] + 1;
Line 491: Line 491:
}
}


KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes) pure nothrow {
KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes)
pure nothrow @nogc {
if (!nodes.length)
if (!nodes.length)
return null;
return null;
Line 511: Line 512:
ref const(KdNode)* best,
ref const(KdNode)* best,
ref double bestDist,
ref double bestDist,
ref size_t nVisited) pure nothrow {
ref size_t nVisited) pure nothrow @nogc {
static double dist(in ref KdNode a, in ref KdNode b) pure nothrow {
static double dist(in ref KdNode a, in ref KdNode b)
pure nothrow @nogc {
typeof(KdNode.x[0]) result = 0;
typeof(KdNode.x[0]) result = 0;
foreach (i; Iota!dim)
foreach (i; Iota!dim)
Line 546: Line 548:
}
}


void randPt(size_t dim=3)(ref KdNode v, ref Xorshift rng) nothrow {
void randPt(size_t dim=3)(ref KdNode v, ref Xorshift rng)
nothrow @nogc {
foreach (immutable i; Iota!dim)
foreach (immutable i; Iota!dim)
v.x[i] = rng.uniform01;
v.x[i] = rng.uniform01;
Line 604: Line 607:


void main() {
void main() {
smallTest();
smallTest;
bigTest();
bigTest;
}</lang>
}</lang>
{{out}}
{{out}}
Retrieved from "https://rosettacode.org/wiki/K-d_tree"