I am looking for an efficient algorithm to update a $N*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a 2D Cartesian plane.
Here an example: There are 3 points in a Cartesian plane:
$a=(1,3)$ $b=(3,3)$ $c=(4,1)$
to calculate the distance between $a$ and $b$ I would simply apply:
$d_{ab} = \sqrt{(x_b-x_a)^2 + (y_b-y_a)^2}$
the distance matrix would be a $3*3$ diagonal matrix where the coefficients represent the distances between each point:
$\begin{bmatrix}0 & d_{ab} & d_{ac} \\ d_{ba} & 0 & d_{bc} \\ d_{ca} & d_{cb} & 0 \end{bmatrix}$
My algorithm is pretty straight forward: I nest 2 for loops to calculate the distance between each point that are inside the points array every time a coordinate change. Here an example in python, but I am not interested in a language specific solution:
import math def distance(a,b): x = pow(b[0]-a[0], 2) y = pow(b[1]-a[1], 2) return math.sqrt(x+y) points = [[1,3],[3,3],[4,1]]; # cartesian points distanceMatr = []; matrixLen = len(points); for i in range(matrixLen): point = points[i] row = [] for j in range(matrixLen): d = distance(point, points[j]) row.append(d) distanceMatr.append(row) print(distanceMatr) If now $a$ moves to $(2,3)$ points becomes [[2,3],[3,3],[4,1]] and I apply the same algorithm again.
The main problems that I would like to optimise of this algorithm are:
- if the coordinates of $a$ change the distance between $b$ and $c$ doesn't
- the distance $d_{ab}$ is equal to $d_{ba}$
- the distance between $a$ and itself is always $0$
Do you have any advice? thank you very much!
