K-d tree: Difference between revisions
Content deleted Content added
m →{{header|Sidef}}: try to reindex |
→{{header|Tcl}}: added zkl |
||
Line 1,982: | Line 1,982: | ||
Nodes visited: 22 |
Nodes visited: 22 |
||
Search time: 289.894755 microseconds per iteration |
Search time: 289.894755 microseconds per iteration |
||
</pre> |
|||
=={{header|zkl}}== |
|||
{{trans|Python}} |
|||
<lang zkl>class KdTree{ |
|||
const NEAREST=0, DIST_SQD=1, NODES_VISITED=2; |
|||
class KdNode{ |
|||
fcn init(_dom_elt,_split,_left,_right){ |
|||
var dom_elt=_dom_elt.apply("toFloat"), |
|||
split=_split, left=_left, right=_right; |
|||
} |
|||
} |
|||
fcn init(pts,_bounds){ // pts is points is ( (x,y,..),..) |
|||
var n=fcn(split, exset){ |
|||
if(not exset) return(Void); |
|||
exset=exset.copy() // mutable lists sort much quicker than read only |
|||
.sort('wrap(abc,xyz){ abc[split]<xyz[split] }); |
|||
m,d:=exset.len()/2, exset[m]; |
|||
while(m+1<exset.len() and exset[m + 1][split]==d[split]){ m+=1 } |
|||
s2:=(split+1)%d.len(); # cycle coordinates |
|||
KdNode(d,split,self.fcn(s2,exset[0,m]), |
|||
self.fcn(s2,exset[m+1,*])) |
|||
}(0,pts); |
|||
var bounds=_bounds; |
|||
} |
|||
fcn findNearest(k,p){ |
|||
fcn(node,target,hr,max_dist_sqd,k){ |
|||
if(not node) return(k.pump(List,0.0), (0.0).MAX, 0); // fake node far away |
|||
nodes_visited,s,pivot:=1, node.split, node.dom_elt; |
|||
left_hr,right_hr:=hr.copy(True), hr.copy(True); // deep-ish copy |
|||
left_hr.max[s]=right_hr.min[s]=pivot[s]; |
|||
reg nearer_node, nearer_hr, further_node, further_hr; |
|||
if(target[s]<=pivot[s]){ |
|||
nearer_node, nearer_hr = node.left, left_hr; |
|||
further_node, further_hr = node.right, right_hr; |
|||
}else{ |
|||
nearer_node, nearer_hr = node.right, right_hr; |
|||
further_node, further_hr = node.left, left_hr; |
|||
} |
|||
n1:=self.fcn(nearer_node, target, nearer_hr, max_dist_sqd, k); |
|||
nearest,dist_sqd:=n1; // n1 is ( (a,b),distance,#visited ) |
|||
nodes_visited+=n1[NODES_VISITED]; |
|||
if(dist_sqd<max_dist_sqd) max_dist_sqd=dist_sqd; |
|||
d:=(pivot[s] - target[s]).pow(2); |
|||
if(d>max_dist_sqd) return(nearest, dist_sqd, nodes_visited); |
|||
d:=sqd(pivot,target); |
|||
if(d<dist_sqd) nearest,dist_sqd,max_dist_sqd=pivot,d,dist_sqd; |
|||
n2:=self.fcn(further_node, target, further_hr, max_dist_sqd,k); |
|||
nodes_visited+=n2[NODES_VISITED]; |
|||
if(n2[DIST_SQD]<dist_sqd) nearest,dist_sqd=n2; |
|||
return(nearest, dist_sqd, nodes_visited) |
|||
}(n, p, bounds, (0.0).MAX,k) |
|||
} |
|||
fcn [private] sqd(p1,p2){ // point deltas squared and summed |
|||
p1.zipWith(fcn(a,b){ (a-b).pow(2) }, p2).sum(0.0) |
|||
} |
|||
fcn show_nearest(k, heading, p){ |
|||
println(heading,":"); |
|||
println("Point: ",p); |
|||
n:=findNearest(k,p); |
|||
println("Nearest neighbor:", n[NEAREST]); |
|||
println("Distance: ", n[DIST_SQD].sqrt()); |
|||
println("Nodes visited: ", n[NODES_VISITED], "\n"); |
|||
} |
|||
}</lang> |
|||
<lang zkl>class Orthotope{ fcn init(mi,ma){ var min=mi,max=ma; } } |
|||
kd1:=KdTree(T(T(2,3), T(5,4), T(9,6), T(4,7), T(8,1), T(7,2)), |
|||
Orthotope(List(0,0), List(10,10))); |
|||
kd1.show_nearest(2, "Wikipedia example data", T(9,2));</lang> |
|||
{{out}} |
|||
<pre> |
|||
Wikipedia example data: |
|||
Point: L(9,2) |
|||
Nearest neighbor:L(8,1) |
|||
Distance: 1.41421 |
|||
Nodes visited: 3 |
|||
</pre> |
|||
<lang zkl>fcn randomPoint(k){ k.pump(List,(0.0).random(1)) } // ( (p1,p2,,pk), ... n of them), p in [0..1] |
|||
fcn randomPoints(k,n){ // ( (p1,p2,,pk), ... n of them), p in [0..1] |
|||
n.pump(List,randomPoint.fp(k)) |
|||
} |
|||
N:=40000; |
|||
kd2:=KdTree(randomPoints(3,N), Orthotope(L(0,0,0), L(1,1,1))); |
|||
kd2.show_nearest(2, String("k-d tree with ", N," random 3D points"), |
|||
randomPoint(3));</lang> |
|||
{{out}} |
|||
<pre> |
|||
k-d tree with 40000 random 3D points: |
|||
Point: L(0.186009,0.186009,0.186009) |
|||
Nearest neighbor:L(0.186012,0.186012,0.186012) |
|||
Distance: 3.91942e-06 |
|||
Nodes visited: 16 |
|||
</pre> |
</pre> |