Rosetta Code

K-d tree: Difference between revisions

Page Discussion

K-d tree (view source)

Revision as of 08:17, 14 March 2024

80 bytes removed ,  2 months ago
→‎{{header|jq}}: simplify
(→‎{{header|jq}}: simplify)
Line 3,487:
# Input: a KdTree
def nearest($p):
# Input: a KdTree
 
def nn_($kd; $target; $hr; $maxDistSqd):
if ($kd | not) then NearestNeighbor(null; infinite; 0)
else {.split nodesVisited:as 1,$s
| .domElt leftHr:as $hr,pivot
| .left rightHr:as $hr }left
| $kd.splitright as $sright
| ($kd.domElttarget[$s] as<= $pivot[$s]) as $targetInLeft
| { nodesVisited: 1,
leftHr: $hr,
rightHr: $hr }
| .leftHr.max[$s] = $pivot[$s]
| .rightHr.min[$s] = $pivot[$s]
| (if $target[targetInLeft then $s]left <=else $pivot[$s]right end) as $targetInLeftnearerKd
| (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; | nn_($target; $nearerHr; $maxDistSqd)) as $res
| .nearest = $res.nearest
| .distSqd = $res.distSqd
Line 3,516 ⟶ 3,518:
else .
end
| nn_($furtherKd; | nn_($target; $furtherHr; .maxDistSqd2)) as $temp
| .nodesVisited += $temp.nodesVisited
| if $temp.distSqd < .distSqd
Line 3,527 ⟶ 3,529:
end ;
nn_(.n; | nn_($p; .bounds; infinite);
 
def showNearestexample($heading; $kdhr; $points; $p):
KdTree($points; .hr) as $kd▼
($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
Peak
2,464

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/361881"