non distances euclidiennes d'éléments connectés à matrice binaire (Matlab)

Question

Je (3x4) matrice M connectée "1" (connectivité 4 "Nord, Sud, Est, Ouest"), disent:

M=[0 1 1 1; 
    1 1 0 1; 
    0 1 0 1]; 

avec des éléments d'indice: idx = 2 4 5 6 7 10 11 12; (8 éléments) M peut être vu comme une matrice de pixels noirs et blancs.

Une idée pour résoudre sa matrice (8x8) D de séparation des pixels blancs? (expl: éléments avec idx = 2 et 12 6 étapes d'intervalle = 5 séparés par des pixels blancs)

D=[0 2 1 2 3 4 5 6; 
    2 0 1 2 3 4 5 6; 
    1 1 0 1 2 3 4 5; 
    2 2 1 0 1 2 3 4; 
    3 3 2 1 0 1 2 3; 
    4 4 3 2 1 0 1 2; 
    5 5 4 3 2 1 0 1; 
    6 6 5 4 3 2 1 0] 

Answer 1

faire un graphique où les noeuds sont des éléments non nuls, et les bords raccorder des éléments voisins. Liste des contiguïté (liste des arêtes de connexion) pour votre exemple:

2-5 
4-7, 4-5 
5-2, 5-4, 5-6 
6-5 
and so on 

Vous pouvez alors utiliser l'algorithme pour trouver tous les chemins les plus courts entre tous les nœuds.

Breadth-first search permet de trouver tous les chemins les plus courts à partir du premier nœud, puis du second nœud et ainsi de suite. Complexité O (V * E). Ici E ~ V, donc O (V^2)

Floyd-Warshall algorithm est assez simple - 3-4 lignes de code. O (V^3) - il est destiné aux graphes pondérés.