Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Interpoint distances

• To: mathgroup at smc.vnet.net
• Subject: [mg41342] Re: [mg41327] Interpoint distances
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 15 May 2003 04:04:41 -0400 (EDT)
• References: <200305141220.IAA07863@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"DIAMOND Mark R." wrote:
> 
> I am trying to find an efficient method of calculating all the pairwise
> (Euclidean) interpoint distances in a given list of points in R^2. I am sure
> that if my matrix algebra were any good, this would be solvable in a better
> manner than I have done it. Ideally, I would like to count each pair of
> points only once, and not count points paired with themselves.I've searched
> the archive, and tried the obvious combinations of words on Google, but no
> luck.
> 
> My slow method (but the fastest of those I've tried) is
> 
> (* Define a distance function for a pair of points *)
> distance[{{x0_, y0_}, {x1_, y1_}}] := Module[
>     {
>       xd = x0 - x1,
>       yd = y0 - y1
>       },
>     Sqrt[xd^2 + yd^2]
>     ]
> 
> (* Create a list of random points with which to experiment *)
> t=Table[{Random[], Random[]}, {1024}]
> 
> (* Union in the next line is just used to get rid of all the duplicates, and
> to dump all but one of the 0 interpoint distances between a point and itself
> *)
> interpointDistances = Union[Map[distance, Flatten[Outer[List, t, t, 1],
> 1]]];
> 
> I would be very grateful for any suggestions for improvement.
> 
> Cheers,
> 
> Mark
> --
> Mark R. Diamond

len = 1024;
t = Table[{Random[], Random[]}, {len}];

distance[{{x0_, y0_}, {x1_, y1_}}] := Module[
    {
      xd = x0 - x1,
      yd = y0 - y1
      },
    Sqrt[xd^2 + yd^2]
    ]

In[29]:= Timing[distances2 = Union[Map[distance,
  Flatten[Outer[List, t, t, 1],1]]];]
Out[29]= {47.79 Second, Null}


Slightly faster:

In[60]:= Timing[distances3 = Table[With[{tt=t[[i]]-t[[j]]},
Sqrt[tt.tt]],
  {i,2,len}, {j,i-1}];]
Out[60]= {17.06 Second, Null}


Much faster but requires alot of space:

In[85]:= Timing[
  ll1 = NestList[{Rest[#[[1]]], First[#[[1]]]}&, {Rest[t],First[t]},
len-2];
  ll2 = Map[(tmp=#[[2]]; Map[Subtract[#,tmp]&, #[[1]]])&, ll1];
  ll3 = Flatten[ll2,1];
  distances5 = Sqrt[Map[#.#&, ll3]];
  ]
                                             
Out[85]= {2.71 Second, Null}

There are probably variations as fast or faster but more conservative of
memory.


Daniel Lichtblau
Wolfram Research

• References:
  • Interpoint distances
    • From: "DIAMOND Mark R." <dot@dot.dot>