Closed pklampros closed 3 years ago
After implementing this self-registration system and having to work with it I also started feeling it's not worth it. I'll simplify it to a system similar to the one in the CLI for the moment, and remove all the statics.
Do you have any comments on the overall modularity of the system as it is suggested? i.e. with the folder structure? the identification of the modules in cmake? the general direction?
The algorithm is a bit cryptic for me as well. As I said earlier, I just took the existing depth algorithms and attached a variable here and there to retain the parents so I can backtrack. A few things can be explained by looking at both the metric and topological depths together, as they seem to just be the face of the same algorithm with a few differences.
The whole binning idea seems to come from the topological side where it appears to allow for testing for lines with the same Axial Ref (segments that came from the same axial line) and assigning them the same depth [a], but it does so with only two bins. When examining a connected segment the algorithm puts the segment in the same bin as the origin segment if it has the same Axial Ref and the alternative bin if not. This way segments on the same axial line are examined one after another because the algorithm does not change the current bin until it's empty, and are assigned the same topological depth. In other words the binning method allows for "flooding" connected segments with the current depth value if they have the same axial line ref (there's various other problems with this, like what happens if Axial Line Ref is set to be the same for all lines...).
Now the metric side is different in that the algorithm has 512 bins, and connected segments are placed in a bin depending on their length (0-length segments placed in bin 0 and the longest segments placed in bin 512). The prioritisation process is the same, meaning that a connected segment close in length to the origin segment, then is it more likely it will be examined next, however in this case it is not assigned the same metric depth as is the case with the topological paths. For example: Given segment A of length 5, connected to segments of lengths:
I can't figure out off the top of my head whether this optimisation makes things faster/better, so I'm not sure whether it's better to go for a simpler solution (i.e. classic Dijkstra).
What do you think?
[a] I can't find an exact reference for this, but this technique is mentioned by Alasdair [1]: "One response is to make the segments continuous, by joining lines that continue in the current direction to create threads (Thomson, 2003) or continuity lines (Figueiredo and Amorim, 2005)". From Thomson [2]: "If a road network is viewed as the diagram of a planar graph, with junctions and dead ends representing nodes and the corresponding connective road segments representing arcs, then a stroke is a set of one or more arcs in a non-branching, connected chain. [..] These elements form four intersecting strokes, where each stroke shows a good continuation of direction and of character (width or line-type)." [b] Alasdair [1], in a discussion on why to weight systems using segment length for angular analysis: "We might expect a longer segment to be associated with a higher percentage of origins and destinations of journeys than a shorter segment (at least within an urban area; the same is not true for a motorway)"
[1] Turner, A. (2007). From axial to road-centre lines: A new representation for space syntax and a new model of route choice for transport network analysis. Environment and Planning B: Planning and Design, 34(3), 539–555. https://doi.org/10.1068/b32067 [2] Thomson, R. C. (2003). Smoothly continuous road centre-line segments as a basis for road network analysis. Proceedings ., 10.
Another strange choice is the fact that in metric paths when testing if a node has been seen before, the node is tested for a kind of topological depth (segdepth variable), and not for it's metric distance in the graph. The variable segdepth is increased when we change bins, so if two lines are in the same bin (have similar lengths) then they will not be checked later if found again. In fact, because segdepth only grows and is never reset, it probably invalidates the checking in some cases and in some cases does not show the true shortest path.
The same seems to be true for the segment metric analysis, so should this be replaced with the proper algorithm? Should there be an option to choose the old one?
Here's a suggested way to modularise the applicaiton. The main idea being that code can be added to a folder along with gui, cli and tests to carry out specific analyses, without growing the various files in the main application.
As an example, a module is attached here for carrying out shortest paths on segment maps, from an independent draft branch of mine, which shows off the way this could work. The implementations for the three types (tulip, metric, topological) are just the existing segment depths (tulip, metric, topological), with some additions to keep track of parents as the graph is traversed, which then allows for backtracking and figuring out the shortest path.
The module is split int various components: