[mlpack] Range search with periodic boundary conditions

[Ryan Curtin]

On Sun, May 10, 2015 at 10:30:43AM +0800, Li Dong wrote:
> Dear all,
> 
> I would like to know how to use RangeSearch class to search neighbors of points in a Cartesian domain with periodic boundary conditions. The boundary conditions along X and Y axis are periodic, but rigid along Z axis.
> 
> Previously I used RangeSearch<EuclideanDistance, BinarySpaceTree<HRectBound<2>, RangeSearchStat> > for points in the spherical domain.

Hi Li,

There used to be (a long time ago) a PeriodicHRectBound class, but it
was unmaintained and was later removed.  It should be possible to
reimplement that, if you want; here is the old version:

https://github.com/mlpack/mlpack/blob/mlpack-1.0.8/src/mlpack/core/tree/periodichrectbound.hpp
https://github.com/mlpack/mlpack/blob/mlpack-1.0.8/src/mlpack/core/tree/periodichrectbound_impl.hpp

You might be able to adapt that (although you'll need some way of
setting which dimensions aren't periodic), and, if you did do that and
add a few tests, we could incorporate it back into the master branch.  I
seem to remember another person some time back who wanted periodic
constraints too.

The other, "easier" solution would be to do some preprocessing:

 * Map all of your query points to one particular X/Y periodic region.
 * Make a copy of your reference set in each adjacent region.
 * Run range search on the mapped query set and all reference sets.
 * Unmap results from reference set.

So it might look something like this:

 +-------+-------+-------+
 | ref.  | ref.  | ref.  |
 | copy  | copy  | copy  |
 |       |       |       |
 |       |       |       |
 +-------+-------+-------+
 | ref.  | ref.  | ref.  |
 | copy  | copy, | copy  |
 |       | mapped|       |
 |       | query |       |
 +-------+-------+-------+
 | ref.  | ref.  | ref.  |
 | copy  | copy  | copy  |
 |       |       |       |
 |       |       |       |
 +-------+-------+-------+

It would be less efficient for large sets than reimplementing
PeriodicHRectBound, though.

I hope this is helpful...

Thanks,

Ryan

-- 
Ryan Curtin    | "More like a nonja."
ryan at ratml.org |   - Pops