K-d tree: Difference between revisions

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

| ($target[$s] <= $pivot[$s]) as $targetInLeft

| (if $targetInLeft then $kd.left else $kd.right end) as $nearerKd

| (if $targetInLeft then $kd.right else $kd.left end) as $furtherKd

| nn_($nearerKd; $target; $nearerHr; $maxDistSqd) as $res

| nn_($furtherKd; $target; $furtherHr; .maxDistSqd2) as $temp

nn_(.n; $p; .bounds; infinite);

def showNearest($heading; $kd; $p):

($kd | nearest($p)) as $res

"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);