search

Bersaelor / KDTree

Swift implementation of a k-dimensional binary space partitioning tree.
MIT License
156 stars 27 forks source link

Update KDTree+NearestNeighbour.swift #43

Closed hsnetzer closed 5 years ago

hsnetzer commented 5 years ago

We need to take the absolute value of the dimensionDifference to fairly compare it to the radius.

Also, I like checking the node value after we see if the radius intersects the hyperplain.

This build should pass with a small speedup to allPoints(within: of:)

Bersaelor commented 5 years ago

The changes are great!

Do you think you could illustrate the importance of abs(dimensionDifference) with a test example that fails previously and succeeds with the proposed change?

hsnetzer commented 5 years ago

Probably can't make a test case, its more an efficiency thing. You want to search the other subtree if the radius crosses the hyperplane. That is when the distance to the hyperplane is less than r. dimensionDifference represents displacement to the hyperplane, i.e. it can be negative. When we test for r > dimensionDifference we end up searching more than is needed.

the comment should be changed too. “the hyperplane at the other side of this value” doesn’t really make sense because the value is on the hyperplane.

Bersaelor commented 5 years ago

True that, thank you for the explanation.

You can correct the comment as part of the PR if you like, since you pointed it out :)

hsnetzer commented 5 years ago

Yay! I also fixed a typo in the readme.