Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Speed up calculating the pair correlation function for 2D point data

• To: mathgroup at smc.vnet.net
• Subject: [mg103335] Speed up calculating the pair correlation function for 2D point data
• From: Szabolcs Horvát <szhorvat at gmail.com>
• Date: Wed, 16 Sep 2009 05:46:15 -0400 (EDT)

Hello,

I would like to calculate the pair correlation function normalized to 1 
for some 2D point data.  I.e. I need to find the mean density of points 
at distance r from any point, normalized to 1.

I am looking for advice on speeding this up.

This is the current implementation I have:

The pcfOne function calculates the mean density of 'points' at distance 
r from one single point ('origin'), up to 'rmax' in steps of 'dr'. 
'density' is the average density of all points over the complete region 
(since the shape of the region is unknown to the function, this quantity 
is passed separately):

pcfOne[points_, origin_, dr_, rmax_, density_] :=
  Module[{hist},
   hist = BinCounts[
     With[{v = # - origin}, Sqrt[v.v]] & /@ points,
     {0, rmax, dr}];
   Transpose[
    {Range[0, rmax - dr, dr] + dr/2,
     hist/(Pi (dr^2 + 2 dr Range[0, rmax - dr, dr]) density)}
   ]
  ]

Now we can select a subset of the points, calculate this function for 
all of them and average the results.  For randomly distributed points 
the result will be a constant function of value 1 (at least until we get 
too close to the edge of the region):

data = RandomReal[1, {50000, 2}];

ListPlot[
   Mean[
    pcfOne[data, #, 0.05, 0.5, Length[data]] & /@
      Nearest[data, {.5, .5}, 1000]
   ],

   PlotRange -> {0, 2}, Axes -> False, Frame -> True
]

This runs in 80 seconds on my machine.  I would like to use this 
function on datasets of up to 300,000 points and average over more than 
just 1000 points near the middle, say 10000.  That would take 60 times 
as long, ~80 minutes, which is way too much.

Is it possible to speed this up significantly?

• Follow-Ups:
  • Re: Speed up calculating the pair correlation function
    • From: Daniel Lichtblau <danl@wolfram.com>
  • Re: Speed up calculating the pair correlation function for
    • From: Leonid Shifrin <lshifr@gmail.com>