Re: Interpoint distances
- To: mathgroup at smc.vnet.net
- Subject: [mg41349] Re: [mg41327] Interpoint distances
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 15 May 2003 04:06:50 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Here is my attempt, although I am not sure whether you really want to
count distances in the way you do, that is: when you have two pairs of
points with the same distance between them you count the distance only
once? That's what your code seems to do, and as it seems to me
undesirable I decided not to apply Union to mine.
Anyway, first of all I define distance in a somewhat different way and
Compile it. That adds quite a lot of efficiency (and can be applied in
your case also).
distance2=Compile[{{p,_Real,1},{q,_Real,1}},Sqrt[(p-q).(p-q)]];
Now the function which tries to avoid "double counting".
intD[l_]:=Flatten[With[{f=Function[
a,distance2[a,#]&]},MapIndexed[Map[f[#1],Drop[l,First[#2]]]&,l]]]
My intD does not include the distance between any point and itself,
which is of ocurse 0. It does not use Sort or Union so the order in
which the answers are given is different form yours. Let us now compare
this with your code:
t = Table[{Random[], Random[]}, {4}];
using your code
interpointDistances
{0.,0.267831,0.435389,0.605678,0.68124,0.70141,0.756965}
with mine:
intD[t]
{0.68124,0.605678,0.435389,0.756965,0.267831,0.70141}
so the difference is the order and the absence of zero. Now let's
compare speeds:
t = Table[{Random[], Random[]}, {500}];
Union[Map[distance, Flatten[Outer[List, t, t, 1],
1]]];//Timing
{55.42 Second,Null}
while
intD[t];//Timing
{4.78 Second,Null}
so we gained about a factor of 10.
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/
On Wednesday, May 14, 2003, at 09:20 pm, 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
>
>
>
>
>
>
>
>