Euclidian distance matrix

[in06khattab]

Is it possible for there to be a function (in 50g or prime) to calculate the euclidean distance or the euclidean cumulative distance matrix?

e.g. From:


To

[Didier Lachieze]

On the Prime, for the euclidean distance matrix :

Let say that you use M1 and M2 to store your sets of points

Code:

M1:=[[1.1,3.1],[2.1,4.1],[3.4,3.2]]
M2:=[[0.7,2.1],[1.6,3.6],[3.2,1.6],[3.5,2.1],[3.1,4]]

Then you can get the distance matrix with:

Code:

MAKEMAT(√((M1(I,1)-M2(J,1))^2+(M1(I,2)-M2(J,2))^2),rowDim(M1),rowDim(M2))

With the fixed 2 number format setting the result is :
   

You can easily create a program for this function.

For the cumulative distance matrix do you have a reference explaining how it is calculated ?

[in06khattab]

Thank you very much for your help in the distance matrix, it was really useful!

I think the cumulative distance must be done by hand, as there are a lot of changing external variables, as it is an example of dynamic programming and looking at the shortest path. So it is cumulative and adding the smallest value.

[Didier Lachieze]

If you know how to do by hand then you can write a program that will do it for you

I think I have understood how to build the cumulative distance matrix. If I apply the following program:

Code:

EXPORT CDM(DM)
BEGIN
  LOCAL CM,j,k;
  CM:=MAKEMAT(0,rowDim(DM),colDim(DM));
  FOR j FROM 1 TO rowDim(DM) DO
    FOR k FROM 1 TO colDim(DM) DO
      IF (j==1) AND (k==1) THEN 
        CM(j,k):=DM(j,k); 
      END;
      IF (j==1) AND (k>1) THEN
        CM(j,k):=DM(j,k)+CM(j,k-1);
      END;
      IF (j>1) AND (k==1) THEN
        CM(j,k):=DM(j,k)+CM(j-1,k);
      END;
      IF (j>1) AND (k>1) THEN
        CM(j,k):=DM(j,k)+MIN(CM(j-1,k-1),CM(j-1,k),CM(j,k-1)); 
      END;
    END;
  END;
  RETURN CM;
END;

to the euclidean distance matrix in your example I get the same result for the cumulative distance matrix :
   

[in06khattab]

Wow, thanks a lot, that was really useful as I was doing it by hand.

[DrD]

That's very good work, Didier! I envy your skill at the details.

You might also like to include the example data for making a "default" distance matrix in Didier's CDM program, (for future reference), as Didier initially described:

Code:


EXPORT CDM(DM)
BEGIN
  LOCAL CM,j,k;

  IF DM==0 then 
    M1:=[[1.1,3.1],[2.1,4.1],[3.4,3.2]];
    M2:=[[0.7,2.1],[1.6,3.6],[3.2,1.6],[3.5,2.1],[3.1,4]];
    DM:=MAKEMAT(√((M1(I,1)-M2(J,1))^2+(M1(I,2)-M2(J,2))^2),rowDim(M1),rowDim(M2));
  END;
  
  CM:=MAKEMAT(0,rowDim(DM),colDim(DM));
  FOR j FROM 1 TO rowDim(DM) DO
    FOR k FROM 1 TO colDim(DM) DO
      IF (j==1) AND (k==1) THEN 
        CM(j,k):=DM(j,k); 
      END;
      IF (j==1) AND (k>1) THEN
        CM(j,k):=DM(j,k)+CM(j,k-1);
      END;
      IF (j>1) AND (k==1) THEN
        CM(j,k):=DM(j,k)+CM(j-1,k);
      END;
      IF (j>1) AND (k>1) THEN
        CM(j,k):=DM(j,k)+MIN(CM(j-1,k-1),CM(j-1,k),CM(j,k-1)); 
      END;
    END;
  END;
  RETURN CM;
END;
[code]