ijt/kdtree — pull request #2 by ericahn (2014-05-07 13:16:03+00:00)
Title: Stricter fromListWithDepth and faster nearestNeighbor

# Faster nearestNeighbor

Originally the function nearestNeighbor did not correctly detect
when the hypersphere intersected the plane. It compared

1) the squared difference in coordinate between the probe and pivot

to

2) the squared distance between the probe point and the pivot.

(As an aside, I renamed 'p' to 'pivot' to aid discussion and
readability.)

However, 1) is always less than or equal to 2) by definition. Thus
the algorithm will always check tree2, even when the hypersphere does
not actually intersect the plane.

The squared distance to the pivot plane is indeed 1), but 2) refers
to the wrong hypersphere. In this case it is a hypersphere centered
at the probe point with the pivot at its surface. In fact it is not
necessarily the pivot but the nearest neighbor in tree1 that must lie
at its surface.

Now the nearestNeighbor algorithm will prune the kd-tree accordingly.

# Stricter fromListWithDepth

Before, fromListWidthDepth constructed a kd-tree by sorting the given
list of points and splitting it along the median. For more consistent
comparison I implemented a stricter split, such that all points in the
left kd-tree have (axis)-coordinate strictly less than that of the
median, i.e. are strictly to its left, while all points in the right
kd-tree have (axis)-coordinate greater than or equal to that of the
median.

Now no longer is there any ambiguity as to which side of the pivot
plane 1) the probe point of a nearest neighbor search, or 2) a point
newly added to the kd-tree, must lie.