wip: implement a periodic tree that maps points to "mirrors"

KristofferC / NearestNeighbors.jl

High performance nearest neighbor data structures (KDTree and BallTree) and algorithms for Julia.

Other

413 stars 65 forks source link

wip: implement a periodic tree that maps points to "mirrors" #193

Open KristofferC opened 2 months ago

KristofferC commented 2 months ago

Similar to what is described in https://namdanalyzer.readthedocs.io/en/latest/kdTree/periodic_kdtree.html.

then querying this kd-tree multiple times, if necessary, with all the relevant periodic images of the query point.

I don't understand why this is needed..

TODO:

[ ] Check query point is inside periodic box?
[ ] Docs
[ ] Tests

Fixes https://github.com/KristofferC/NearestNeighbors.jl/issues/133

dkarrasch commented 2 months ago

I don't understand why this is needed..

I think this is because some points may be far from the query point, represented by some point in the canonical image, but close to a shifted one version of the query point. So you may need to query for the canonical version and the shifted one, and out of those find the nearest neighbors.

KristofferC commented 2 months ago

Aha, I misunderstood the link I think. What I thought they did was to duplicate the input points to all the mirrors (which is what this implementation does) but instead they map the input points to a single "canonical image". In the first case you only need to query once but in the latter you might need to query multiple times (for example if the ball around the query point is outside the image).

That is probably a better idea than what I did here.