Message Boards Message Boards

0
|
6616 Views
|
5 Replies
|
6 Total Likes
View groups...
Share
Share this post:

Generalize a function that finds distance between 2 pairs of coordinates?

Posted 8 years ago

In my last post I received some help in creating a function that would find the distance between 2 pairs of coordinates:

Clear[distance, x1, x2, y1, y2];
distance[{{x1_, y1_}, {x2_, y2_}}] := Abs[(x2 - x1)] + Abs[(y2 - y1)];
distance[{{0, 0}, {1, 1}}]
2

Now I am trying to generalize this function so that I could input any amount of coordinates (locations), and in the very end, return back to the origin (0,0). Here is an example. distance[{{1,1},{2,2}} = 8. So we would started at the origin (0,0) and travel to (1,1) which is the legs of a right triangle and equals 2. From (1,1) we travel to (2,2) which is another distance of 2, so now the total is 4..Now we go back to the origin (which is a distance of 4), thus the total distance is 8. This idea is very straight forward conceptually. I thought about creating a function that would iterate from location (0,0) and go to any list of coordinates, then back to (0,0), maybe by using something like the Length[{list of coordinates}]. I don't know if that would be possible.

I have just a little bit of code that finds the distance from the origin to some other point, I just don't understand how to implement something that will get me back to the origin, while going to any amount of coordinates I give it. I cant just go in a straight line because in real life one couldn't drive through a building.

Clear[totaldistance, x1, x2, y1, y2];
totaldistance[{{x2_, y2_}}] := Abs[(x2 - 0)] + Abs[(y2 - 0)];
totaldistance[{{2, 2}}]
4

Thanks for any tips. Like I said, this problem is easy and makes sense conceptually, but putting my ideas into Mathematica is always the hard part.

POSTED BY: Brandon Davis
5 Replies

One comment though,

A recursive solution is "not so nice" only because Mathematica is not a true functional language (in spite of the fact that it supports functional programming style). In functional languages (e.g., Erlang, Clojure, F# etc.) recursion is the only way to implement iterations (well, almost the only way, there is list comprehension) . This is especially true if that language supports pattern matching (e.g., Erlang, but certainly far from the level of Mathematica) and tail recursion optimization. However, in Mathematica this is not the case. I have tackled many cases were the adoption of tail recursion is unsuccessful or very inefficient, and Sander'c comments are certainly right for large problems.

yehuda

Though the solution of both are working, there are also other methods. The method of Yehuda is recursive which is not that nice, and can therefore not be parallelised easily. I see wo other ways of doing it:

ClearAll[distance];
distance[{{x1_,y1_},{x2_,y2_}}]:=Abs[(x2-x1)]+Abs[(y2-y1)];
totaldistance[x:{{_,_}..}]:=Total[distance/@Partition[x,2,1,{-1,1},{{0,0}}]]

similar to the above 2 replies. But one can also do it like this:

ClearAll[distance];
ClearAll[distance];
distance[{\[CapitalDelta]x_,\[CapitalDelta]y_}]:=Abs[\[CapitalDelta]x]+Abs[\[CapitalDelta]y];
totaldistance[x:{{_,_}..}]:=Total[distance/@Differences[Join[{{0,0}},x,{{0,0}}]]]

or even:

ClearAll[totaldistance];
totaldistance[x:{{_,_}..}]:=Total[Abs[Differences[Join[{{0.0,0.0}},x,{{0.0,0.0}}]]],\[Infinity]]

Note that prepending/appending 0.0 instead of 0 can make a big difference depending on the input data. Especially if it is a packed array of a certain type. The last one will be the fastest as it does not use Map, and everything is vectorized (assuming real numbers, not symbolic calculation, and 'large' number of points).

POSTED BY: Sander Huisman

This does not implement the distance from the origin {0,0} as the OP asked for... You need {0,0} and {0,0} at the beginning and the end of the list before partitioning it. So, use

Partition[{pts__List},2,1,{-1,1},{{0,0}}]

yehuda

You can use Partition to divide your path into couples of successive points, and then map distance on the couples:

Clear[distance];
distance[{{x1_, y1_}, {x2_, y2_}}] := Abs[x2 - x1] + Abs[y2 - y1];
distance[{pts__List}] := 
 Total[Map[distance, Partition[{pts}, 2, 1, 1]]]

The parameters 2, 1, 1 given to Partition mean that the sublists will be of length 2, with overhang 1, and the last point will appear as the first element in the last couple, with the second element taken from the beginning of the path. It's complicated. I hope I didn't mix it up.

POSTED BY: Gianluca Gorni

Well, using pattern matching you can do it quite easily. You just define two distance function of different arities (e.g., the number of arguments). You call the first distance function and it calls the second one. This is a form of tail recursion. In each step the first element of the list is removed and the distance to the next point is computed and stored in the second argument (which is called an accumulator) and the function is called again. In the last step only one coordinate remains and then the final distance is computed and returned (with no recursion).

Clear[distance, x1, x2, y1, y2];
distance[pts_List] := distance[pts, 0];
distance[{{x1_, y1_}, {x2_, y2_}, rest___}, tot_] := 
  distance[{{x2, y2}, rest}, Abs[x1 - x2] + Abs[y1 - y2]];
distance[{{x_, y_}}, len_] := len + Abs[x] + Abs[y];

Now, notice that your definition of a distance is the ManhattanDistance that is already defined in Mathematica, so I change the program to use it

Clear[distance, x1, x2, y1, y2];
distance[pts_List] := distance[pts, 0];
distance[{{x1_, y1_}, {x2_, y2_}, rest___}, tot_] := 
  distance[{{x2, y2}, rest}, ManhattanDistance[{x1, y1}, {x2, y2}]];
distance[{{x_, y_}}, len_] := len + ManhattanDistance[{x, y}, {0, 0}];

As a last step, if you want to compute also the distance from the origin to the first point (coordinate) then all you need is to change the initial distance as follows

Clear[distance, x1, x2, y1, y2];
distance[pts_List] := 
  distance[pts, ManhattanDistance[First[pts], {0, 0}]];
distance[{{x1_, y1_}, {x2_, y2_}, rest___}, tot_] := 
  distance[{{x2, y2}, rest}, ManhattanDistance[{x1, y1}, {x2, y2}]];
distance[{{x_, y_}}, len_] := len + ManhattanDistance[{x, y}, {0, 0}];

yehuda

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract