# binarysunrise-io/kdtree

Switch branches/tags
Nothing to show
Commits on Sep 29, 2017
1. jessekempf committed Sep 29, 2017
2. jessekempf committed Sep 29, 2017
3. jessekempf committed Sep 29, 2017
4. jessekempf committed Sep 29, 2017
5. jessekempf committed Sep 29, 2017
6. ericahn authored and jessekempf committed Sep 29, 2017
```----------------------
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

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.```
7. mlitchard authored and jessekempf committed Jul 3, 2016
8. jessekempf committed Sep 29, 2017
Commits on Jan 16, 2012
1. ijt committed Jan 16, 2012
2. ijt committed Jan 16, 2012
`Added small feature to KdTree...`
Commits on Jan 12, 2012
1. Michal J. Gajda committed Jan 12, 2012
Commits on Jan 11, 2012
1. Michal J. Gajda committed Jan 11, 2012
Commits on Jul 1, 2011
1. ijt committed Jul 1, 2011
Commits on Jun 27, 2011
1. ijt committed Jun 27, 2011
2. ijt committed Jun 27, 2011
3. ijt committed Jun 27, 2011
4. ijt committed Jun 27, 2011
5. ijt committed Jun 27, 2011
6. ijt committed Jun 27, 2011
7. ijt committed Jun 27, 2011
8. ijt committed Jun 27, 2011
Commits on Jun 26, 2011
1. ijt committed Jun 26, 2011
2. ijt committed Jun 26, 2011
3. ijt committed Jun 26, 2011
4. ijt committed Jun 26, 2011
5. ijt committed Jun 26, 2011
6. ijt committed Jun 26, 2011
7. ijt committed Jun 26, 2011
8. ijt committed Jun 26, 2011
9. ijt committed Jun 26, 2011
10. ijt committed Jun 26, 2011
Commits on Jun 25, 2011
1. ijt committed Jun 25, 2011
2. ijt committed Jun 25, 2011