K-d tree: Difference between revisions
Content deleted Content added
m →{{header|Wren}}: Minor tidy |
|||
Line 3,413: | Line 3,413: | ||
distance: 0.004361560347252592 |
distance: 0.004361560347252592 |
||
nodes visited: 34 |
nodes visited: 34 |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{Works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
'''Adapted from [[#Wren|Wren]] and [[#Kotlin]]''' |
|||
Since jq does not include a PRNG, the following assumes that |
|||
an external source of entropy such as /dev/urandom is available. |
|||
See the "Invocation" section below for details. |
|||
In the following, a Point is represented by a numeric JSON array. |
|||
<syntaxhighlight lang="jq"> |
|||
### Generic utilities |
|||
# Output: a PRN in range(0; .) |
|||
def prn: |
|||
if . == 1 then 0 |
|||
else . as $n |
|||
| (($n-1)|tostring|length) as $w |
|||
| [limit($w; inputs)] | join("") | tonumber |
|||
| if . < $n then . else ($n | prn) end |
|||
end; |
|||
def rand: 1000 | prn / 1000; |
|||
def randomPt($dim): |
|||
[ range(0; $dim) | rand ] ; |
|||
def randomPts($dim; $n): |
|||
[ range(0;$n) | randomPt($dim) ]; |
|||
def sq: .*.; |
|||
# $p and $q should be numeric arrays of the same length |
|||
def PtSqd($p; $q): |
|||
[$p, $q] | transpose | map((.[0] - .[1]) | sq) | add; |
|||
### K-d trees |
|||
def HyperRect($min; $max): |
|||
{ $min, $max }; |
|||
def NearestNeighbor($nearest; $distSqd; $nodesVisited): |
|||
{ $nearest, $distSqd, $nodesVisited }; |
|||
def KdNode($domElt; $split; $left; $right): |
|||
{$domElt, $split, $left, $right}; |
|||
def KdTree($pts; $bounds): |
|||
def nk2($exset; $split): |
|||
if ($exset|length == 0) then null |
|||
else { $exset } |
|||
| .exset |= sort_by(.[$split]) |
|||
| .m = ((.exset|length/2)|floor) |
|||
| .exset[.m] as $d |
|||
| until (.m + 1 >= (.exset|length) or .exset[.m + 1][$split] != $d[$split]; |
|||
.m += 1) |
|||
| .s2 = $split + 1 |
|||
| if .s2 == ($d|length) then .s2 = 0 else . end |
|||
| KdNode($d; |
|||
$split; |
|||
nk2(.exset[: .m]; .s2); |
|||
nk2(.exset[.m + 1 :]; .s2) |
|||
) |
|||
end ; |
|||
{ n: nk2($pts; 0), |
|||
$bounds } ; |
|||
# Input: a KdTree |
|||
def nearest($p): |
|||
def nn_($kd; $target; $hr; $maxDistSqd): |
|||
if ($kd | not) then NearestNeighbor(null; infinite; 0) |
|||
else { nodesVisited: 1, |
|||
leftHr: $hr, |
|||
rightHr: $hr } |
|||
| $kd.split as $s |
|||
| $kd.domElt as $pivot |
|||
| .leftHr.max[$s] = $pivot[$s] |
|||
| .rightHr.min[$s] = $pivot[$s] |
|||
| ($target[$s] <= $pivot[$s]) as $targetInLeft |
|||
| (if $targetInLeft then $kd.left else $kd.right end) as $nearerKd |
|||
| (if $targetInLeft then .leftHr else .rightHr end) as $nearerHr |
|||
| (if $targetInLeft then $kd.right else $kd.left end) as $furtherKd |
|||
| (if $targetInLeft then .rightHr else .leftHr end) as $furtherHr |
|||
| nn_($nearerKd; $target; $nearerHr; $maxDistSqd) as $res |
|||
| .nearest = $res.nearest |
|||
| .distSqd = $res.distSqd |
|||
| .nodesVisited += $res.nodesVisited |
|||
| .maxDistSqd2 = ([.distSqd, $maxDistSqd] | min) |
|||
| .d = ($pivot[$s] - $target[$s]) | sq |
|||
| if .d > .maxDistSqd2 then NearestNeighbor(.nearest; .distSqd; .nodesVisited) |
|||
else .d = PtSqd($pivot; $target) |
|||
| if .d < .distSqd |
|||
then .nearest = $pivot |
|||
| .distSqd = .d |
|||
| .maxDistSqd2 = .distSqd |
|||
else . |
|||
end |
|||
| nn_($furtherKd; $target; $furtherHr; .maxDistSqd2) as $temp |
|||
| .nodesVisited += $temp.nodesVisited |
|||
| if $temp.distSqd < .distSqd |
|||
then .nearest = $temp.nearest |
|||
| .distSqd = $temp.distSqd |
|||
else . |
|||
end |
|||
| NearestNeighbor(.nearest; .distSqd; .nodesVisited) |
|||
end |
|||
end ; |
|||
nn_(.n; $p; .bounds; infinite); |
|||
def showNearest($heading; $kd; $p): |
|||
($kd | nearest($p)) as $res |
|||
| "\(heading):", |
|||
"Point : \($p)", |
|||
"Nearest neighbor : \($res.nearest)", |
|||
"Distance : \($res.distSqd | sqrt)", |
|||
"Nodes visited : \($res.nodesVisited)", |
|||
""; |
|||
def example($title; $hr; $points; $point): |
|||
KdTree($points; .hr) as $kd |
|||
| showNearest($title; $kd; $point); |
|||
### Examples |
|||
def points: [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]; |
|||
example("WP example data"; |
|||
HyperRect([0, 0]; [10, 10]); points; [9,2] ), |
|||
example("1,000 random 3D points"; |
|||
HyperRect([0, 0, 0]; [1, 1, 1]); randomPts(3; 1000); randomPt(3)), |
|||
example("400,000 random 3D points"; |
|||
HyperRect([0, 0, 0]; [1, 1, 1]); randomPts(3; 400,000); randomPt(3)) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
WP example data: |
|||
Point : [9,2] |
|||
Nearest neighbor : [8,1] |
|||
Distance : 1.4142135623730951 |
|||
Nodes visited : 3 |
|||
1,000 random 3D points: |
|||
Point : [0.625,0.521,0.996] |
|||
Nearest neighbor : [0.597,0.492,0.997] |
|||
Distance : 0.040323690307311935 |
|||
Nodes visited : 28 |
|||
400,000 random 3D points: |
|||
Point : [0.847,0.237,0.702] |
|||
Nearest neighbor : [0.848,0.237,0.706] |
|||
Distance : 0.004123105625617665 |
|||
Nodes visited : 29 |
|||
</pre> |
</pre> |
||