W Randolph Franklin home page
... (old version)
Research/ home page Login


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

  1. allnearpairs was written to test the algorithm, not as a packaged commercial product.
    1. Parameters are set by editing the code and recompiling.
    2. There is considerable debugging code.
    3. Array sizes are set at compile time (for efficiency).
  2. Algorithm:
    1. Create a 3D uniform grid, of up to mg*mg*mg cells, with space for up to mpc points per cell.
    2. Read the 3D points from a file, scale them to the range [0,1)3, and insert each point into the appropriate cell.
    3. Iterate through the cells, comparing all the points in each cell, pair by pair.
    4. Write a file with the pairs.
  3. User parameters to set in the code:
    mpMax number of input points
    rRadius of interest
    scaleScale factor to multiply the input coordinates by to reduce them to the range [0,1).
    mgMax allowable grid resolution.
    mpcMax allowable number of points per cell.
    mpccMax allowable number of near pairs.
  4. How to compile:
    g++ -O3 -o allnearpairs allnearpairs.cc
  5. The input file is called points and has the format:
    x y z
    x y z
    ...
  6. The output file is called pairs. Each line is one point pair, with these entries, in fixed-width columns for easy post-processing.
    1. 1st point number in points file, indexed from 0
    2. 2nd ...
    3. 1st point coordinates
    4. 2nd ...
    5. Square of the distance