développer une matrice de distance en utilisant les coordonnées

Question

hey, on m'a donné un problème, j'ai essentiellement reçu un morceau de papier quadrillé de taille arbitraire et je dois développer une matrice de distance en utilisant seulement les coordonnées pour chacun des points de la grille sur la page . Je pense que la meilleure approche serait quelque chose comme les algorithmes Floyd-Warshall ou Djikstra pour la paire de chemins la plus courte, mais je ne sais pas comment l'adapter aux distances de coordonnées, car toute la documentation utilise une distance prédéterminée matrice. donc toute aide serait grand

Answer 1

la matrice de distance contient simplement les distances à tous les autres points.

Fondamentalement, il suffit de calculer les distances en utilisant une métrique appropriée. Si vous voulez la distance "normale", c'est sqrt ((x1-x2)^2 + (y1-y2)^2) où (x/y) sont les coordonnées d'un point en mm/pouces. Si vous voulez la distance sur le papier en suivant les lignes, | x1-x2 | + | y1-y2 |. Les algorithmes de graphes seraient excessifs, sauf si vous avez des murs sur le papier.