Shortest path computation description

This section gives the shortest path computation on a conceptual level. It is accompanied by a separate document (Shortest path computation execution) with program execution description (console parameters, created files or folders, etc). For sample results, see the Example folder (the Expected results from -spd subfolder represents the shortest paths computation). Scripts to interpret the resulting tiffs can be found in the corresponding folder.

Table of contents:

1. Algorithm
2. Selection of the starting pixel

1. Algorithm

I calculate the shortest distances for each void pixel in the monolith (except for pixels some unreachable cavities) from a certain single starting pixel. The result looks like this (white—solid):

This is the reproduction of Fig. 8 from Hormann et al., 2015.

The program operates as follows:

1. The starting pixel is selected. It is a void pixel closest to the center of the monolith
2. The monolith is represented as a graph. Each void pixel is a node of the graph. Pixels are connected to 26 neighboring void pixels. Distances to neighbors (weights on the graph edges) are real Euclidean distances between pixels
3. Dijkstra’s shortest path algorithm is run over the monolith to determine shortest paths to every accessible void pixel. We terminate the run of the Dijkstra’s algorithm when there are no more void pixels accessible from the current initial pixel (though there may be inaccessible void pixels)
4. If we could not reach all the six walls of the monolith, we select the next unprocessed void pixel as close to the center as possible and run the Dijkstra’s algorithm again, until we find a starting pixel that is in the cavity that contacts all the six monolith walls
5. If there are no unprocessed void pixels and we have not reached all the six monolith walls in a single propagation, the algorithm terminates

This algorithm may leave some cavities unprocessed. This happens when we encounter a cavity that reaches all the walls and terminate the program before processing all the cavities. This logic can easily be changed in the code (to processing all the cavities, until no void pixels are left), but i did not do it to make processing slightly faster.

2. Selection of the starting pixel

1. We determine the center pixel of the monolith
2. If this pixel is void, we start the shortest path algorithm from this pixel
3. Otherwise, we expand step-by-step a cubic box with the center at this pixel. At each step, we
4. increase the size of the box by 1 pixel
5. iterate over pixels at the boundary of the box until we meet a void pixel
6. We use this pixel as a starting one

Actually, this method may miss void pixels closest to the center of the monolith, because we do not search pixels in spherical shells. But expanding a cubic box instead of a spherical shell is much faster and for our task is sufficiently precise.

If the shortest path propagation could not reach all the six boundary walls and void pixels remain in the monolith, we need to select the next starting pixel. We do this by the same algorithm. We start box expansion from the box size value from the previous expansion. We also do not use already processed pixels as starting pixels for new cavities.