allnearpairs.cc is a program to take a set of points in {$E^3$} and a fixed radius {$R$}, and report all the point pairs within {$R$} .
allnearpairs is very fast. E.g., processing 20K points to find 688K pairs took 20msec, excluding I/O times, on a 2.8GHz machine. For a fixed number of points per point within the radius, the time is linear in the number of points. {$ 10^6 $} points is easy.
Author
W. Randolph Franklin, Professor ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, 110 8th St, Troy NY, 12180 USA wrf@ecse.rpi.edu +1 (518) 276-6077 http://wrfranklin.org/
Terms of use and acknowledgement
allnearpairs is free for nonprofit research and education. I would appreciate a credit, and the following acknowledgement:
- This research was partially supported by NSF grant CMMI-0835762.
Offers of collaboration and co-authorships are always welcome. See my research page for ideas.
Usage
- allnearpairs was written to test the algorithm, not as a packaged
commercial product.
- Parameters are set by editing the code and recompiling.
- There is considerable debugging code.
- Array sizes are set at compile time (for efficiency).
- Algorithm:
- Create a 3D uniform grid, of up to mg*mg*mg cells, with space for up to mpc points per cell.
- Read the 3D points from a file, scale them to the range [0,1)3, and insert each point into the appropriate cell.
- Iterate through the cells, comparing all the points in each cell, pair by pair.
- Write a file with the pairs.
- User parameters to set in the code:
mp Max number of input points r Radius of interest scale Scale factor to multiply the input coordinates by to reduce them to the range [0,1). mg Max allowable grid resolution. mpc Max allowable number of points per cell. mpcc Max allowable number of near pairs. - How to compile: g++ -O3 -o allnearpairs allnearpairs.cc
- The input file is called points and has the format:
x y z
x y z
... - The output file is called pairs. Each line is one point pair,
with these entries, in fixed-width columns for easy post-processing.
- 1st point number in points file, indexed from 0
- 2nd ...
- 1st point coordinates
- 2nd ...
- Square of the distance