Find closest 8-connected chessboard distance between multiple pairs of points: shortest m-path

3 views (last 30 days)
Meghana Dinesh
Meghana Dinesh on 19 Jan 2018
Commented: Meghana Dinesh on 22 Jan 2018
I am working on binary images. I have two sets of points: PNodes and FNodes. I want to find the closest PNode to each of the FNodes (shortest m-path); closest in terms of 8-connected chessboard distance.
In the example below, suppose PNodes (donated by *) are: (6,1), (6,5) and (5,8). (indexing starts from 0, first element is row number). FNodes (denoted by #) are: (0,1), (0,9), (1,6), (2,5) and (4,3).
In =
[0, 1#, 0, 0, 0, 0, 0, 0, 0, 1#, 0;
1, 0, 0, 0, 0, 0, 1#, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1#, 0, 0, 1, 0, 0;
0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0;
0, 1, 1, 1#, 0, 1, 0, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, 1*, 0, 0;
0, 1*, 0, 0, 0, 1*, 0, 0, 1, 0, 0;
0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0;
0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
Distance Matrix =
[0, 6#, 0, 0, 0, 0, 0, 0, 0, 5#, 0;
5, 0, 0, 0, 0, 0, 5#, 0, 4, 0, 0;
0, 4, 0, 0, 0, 4#, 0, 0, 3, 0, 0;
0, 0, 3, 0, 0, 0, 3, 0, 0, 2, 0;
0, 2, 2, 3#, 0, 2, 0, 0, 1, 0, 0;
0, 1, 0, 0, 0, 1, 0, 0, **, 0, 0;
0, **, 0, 0, 0, **, 0, 0, 1, 0, 0;
0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0;
0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
I want to find out the distance of closest path from each FNode to reach closest PNode. Something like this: FNode at (0,1) is closest to PNode at (6,1). FNode at (4,3) is closest to PNode at (6,1). All distances are in terms of 8-connected chessboard distance.
Ultimate requirement from this entire process: I just want to make sure all PNodes have atleast 1 FNode which lie within a given distance range (along the path of 1s);
Suppose PNode (PN_1) has a FNode (FN_1) which lies within the required distance range, I also make sure that PN_1 is closest to FN_1, and not any other PNode.
For a better understanding, I have attached an image below; FNodes are rectangular and PNodes are circular.
I don't care about other elements in the matrix, apart from those of PNodes and FNodes, as depicted.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!