[mlpack] Range search with periodic boundary conditions

[董理]

Dear Ryan,

Thanks for your reply! I searched out on the internet, and found the following question:

http://stackoverflow.com/questions/6917664/nearest-neighbor-search-with-periodic-boundary-conditions <http://stackoverflow.com/questions/6917664/nearest-neighbor-search-with-periodic-boundary-conditions>

It seems ‘cover tree’ can be used for periodic boundary condition. I see there already is an implementation of cover tree. Could I use it?

Best regards,
Li

> On 2015年5月11日, at 下午11:47, Ryan Curtin <ryan at ratml.org> wrote:
> 
> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cc.gatech.edu/pipermail/mlpack/attachments/20150512/b38e3acf/attachment-0003.html>