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>
- Interpoint distances