breadth-first search in coordinate based system

Question

I am not an experienced programmer (programming language MATLAB) and hence have barely any knowledge of advanced algorithms. One of these is the breadth-first search. The concept I understand but implementing it into my problem is difficult for me.

My problem: I place disks, of equal sizes, randomly in a square and will place the coordinates of the disks into separate matrices when they are one connected network. I colorized them for clarity (see image). Now, I have to find the shortest path from left to right of the network which spans from left to right and want to do this based on the coordinates. The disks have to touch in order to be connected to each other. They cannot form a path if they are not touching.

So this is what I currently have: I have a matrix with coordinates x and coordinates y in columns 1 and 2, every row representing one of the disks (for ease, let's just take the coordinates of all the connecting disks, excluding those which are not spanning from left to right when connected). The diameter of the disks is known (0.2). We can easily identify which disks are on the left boundary of the square and which disks are on the right boundary of the square. These represent the possible starting coordinates and the possible goal coordinates.

% Coordinates of group of disks, where the group connects from left to right.
 0.0159    0.1385
 0.0172    0.2194
 0.0179    0.4246
 0.0231    0.0486
 0.0488    0.1392
 0.0709    0.2109
 0.0813    0.0595
 0.0856    0.3530
 0.1119    0.3756
 0.1275    0.2530
 0.1585    0.4751
 0.1702    0.2926
 0.1908    0.3828
 0.1961    0.3277
 0.2427    0.4001
 0.2492    0.4799
 0.2734    0.4788
 0.3232    0.3547
 0.3399    0.3275
 0.3789    0.3716
 0.4117    0.3474
 0.4579    0.3961
 0.4670    0.3394
 0.4797    0.3279
 0.4853    0.4786
 0.3495    0.4455
 0.4796    0.2736
 0.0693    0.0746
 0.1288    0.4204
 0.1271    0.4071
 0.1218    0.4646
 0.1255    0.3080
 0.4154    0.2926

Positions of disks and colored the connecting disks. Image is very schematic and many more disks should be expected in a much larger area (keeping same size disks).

My strategy was to set up a breadth-first search, taking the starting coordinates as one of the disks (can be any) on the left side of the square. The goal will be to find the shortest path to the right side of the square.

To my understanding, I want to pick a starting coordinate and check all disks if they are within a diameter distance (middle point to middle point of the disks) of my starting coordinate. If they are within range of my starting coordinate I want to place them in a 'queue' (natively not supported by MATLAB? but let's set one up ourselves). Then, the next step is to take the first disk which was close enough and do the same for this one. I can do this but once I have to do the second disk which was within my first disk, I am lost in how and/or what data structure I should take and how to save the 'path' which it is finding. This means I can find a path but not all paths and hence also not the shortest path.

I appreciate any help! Maybe some documentation which I have not seen yet or maybe an example which is very comparable.

Best regards,

Answer 1

This question has now been solved!

The way I have solved this was close to what was already suggested in my question but also with help from some of the comments.

The distance between coordinates can be put into a matrix. Let us look at coordinate (disk) 1 and coordinate (disk 3). This means that we will be at elements (1,3) and (3,1). If the disks are within touching distance, these two elements will indicate a 1 and otherwise a 0. This is done for all disks and this creates the adjacency matrix.

I created a 'graph' with the built-in function G = Graph(adjacency matrix) we can create an undirected graph. Then with the built in function [path, distance of path] = shortestpath(G,s,t) where G is the graph and s and t are the starting disks (in this case, indicated by integers), the shortest path can be found from disk s to t.

There is however one thing that we must pay attention to and that is representing the actual distance between disks. If we look at G, we can actually see that it contains two objects. One representing the nodes and the other representing the edges. The edges is crucial for the coordinate based distances as we can set the 'weight' of the edge as the distance between two disks. This can simply be done by looping over the nodes and calculating the distance between the neighbouring nodes and inserting them into the weight (G.Edges.Weight(i) = distance between the respective nodes).

How do I find the optimal path from left to right? I loop over all starting disks (defined as touching the left side of the square) and find the shortest path to all disks that touch the right side of the square. Saving the distances of the paths the actual shortest path can be found.

To give you an example of what can be achieved, the following video shows what paths from every starting disk can be found and the final frame shows the shortest path. Video of path finding. The shortest path I have also attached here:

Shortest path left to right.

If there are any questions you would like to ask me about specifics, let me know.