Nicht euklidische Entfernungen von verbundenen Elementen in binärer Matrix (Matlab)

Question

Ich habe (3x4) M-Matrix von verbundenem "1" (Konnektivität 4 "Norden, Süden, Osten, Westen"), sagt:

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

mit Indexelementen: idx = 2 4 5 6 7 10 11 12; (8 Elemente). M kann als eine Matrix von schwarzen und weißen Pixeln angesehen werden.

Irgendeine Idee, um seine (8x8) D-Matrix der weißen Pixeltrennung zu lösen? (Expl: Elemente mit idx = 2 und 12 6 Stufen auseinander = von 5 weißen Pixeln getrennt)

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

einen Graphen machen, wo Knoten von Null verschiedenen Elemente sind, und Kanten Nachbarelemente verbinden. Adjazenzliste (Liste der Verbindungskanten) für Ihr Beispiel:

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

Dann jeden Algorithmus verwenden, um alle kürzesten Wege zwischen allen Knoten zu finden.

Breadth-first search ermöglicht es, alle kürzesten Pfade vom ersten Knoten, dann vom zweiten Knoten und so weiter zu finden. Komplexität O (V * E). Hier ist E ~ V, also O (V^2)

Floyd-Warshall algorithm ist ziemlich einfach - 3-4 Codezeilen. O (V^3) - es ist für gewichtete Graphen gedacht.