K-d tree: Difference between revisions
Content added Content deleted
m (Explicit string concat in second D entry) |
(Updated D entry) |
||
Line 227:
/// Square of the euclidean distance.
double sqd(in ref Point!(k, F) q) const pure nothrow @nogc {
double sum = 0;
foreach (immutable dim, immutable pCoord; data)
Line 292:
*/
auto findNearest(size_t k, F)(KdTree!(k, F) t, in Point!(k, F) p)
pure nothrow @nogc {
// Algorithm is table 6.4 from the paper, with the addition of
// counting the number nodes visited.
Line 299:
int, "nodesVisited")
nn(KdNode!(k, F)* kd, in Point!(k, F) target,
Orthotope!(k, F) hr, F maxDistSqd) pure nothrow @nogc {
if (kd == null)
return typeof(return)(Point!(k, F)(), F.infinity, 0);
Line 455:
// See QuickSelect method.
KdNode* findMedian(size_t idx)(KdNode[] nodes) pure nothrow @nogc {
auto start = nodes.ptr;
auto end = &nodes[$ - 1] + 1;
Line 491:
}
KdNode* makeTree(size_t dim, size_t i)(KdNode[] nodes)
pure nothrow @nogc {
if (!nodes.length)
return null;
Line 511 ⟶ 512:
ref const(KdNode)* best,
ref double bestDist,
ref size_t nVisited) pure nothrow @nogc {
static double dist(in ref KdNode a, in ref KdNode b)
pure nothrow @nogc {
typeof(KdNode.x[0]) result = 0;
foreach (i; Iota!dim)
Line 546 ⟶ 548:
}
void randPt(size_t dim=3)(ref KdNode v, ref Xorshift rng)
nothrow @nogc {
foreach (immutable i; Iota!dim)
v.x[i] = rng.uniform01;
Line 604 ⟶ 607:
void main() {
smallTest
bigTest
}</lang>
{{out}}
| |||