Differences

This shows you the differences between two versions of the page.

--- new_road_constructor [2021/07/07 15:45]
argemiro
+++ new_road_constructor [2021/07/07 18:10] (current)
argemiro
@@ Line 47: / Line 47: @@
  {{ :a1.png?600 |}}
-(example of road endpoints -- white cells represent the areas depicting the road endpoints, but ignoring branches that are only one cell long)
+                                      Example of road endpoints -- white cells represent the areas depicting the road endpoints, but ignoring branches that are only one cell long
 .	Then, it calculates the cost and direction map to reach the “least costly” road endpoint. The existent roads are treated as barriers which can make some parts of the map inaccessible to the cost calculation.
@@ Line 53: / Line 53: @@
 \\
  {{ :a2.png?600 |}}
-(costs to reach the “least costly” road endpoints --“blueish” areas represent the vicinities of road endpoints)
+                                        Costs to reach the “least costly” road endpoints --“blueish” areas represent the vicinities of road endpoints
 \\
 \\
 {{ :a3.png?600 |}}
-(directions that must be followed to reach the “least costly” road endpoints)
+                                                         Directions that must be followed to reach the “least costly” road endpoints
 \\
 \\
@@ Line 66: / Line 66: @@
 \\
  {{ :a4.png?600 |}}
-(road endpoint dominance areas -- each color corresponds to the region of dominance of a road endpoint located in that area)
+                                    Road endpoint dominance areas -- each color corresponds to the region of dominance of a road endpoint located in that area
 \\
 \\
  {{ :a5.png?600 |}}
-(road endpoint dominance areas with “fences” around them – “fences” are made of contiguous null value cells)
+                                            Road endpoint dominance areas with “fences” around them – “fences” are made of contiguous null value cells
 \\
 \\
@@ Line 79: / Line 79: @@
 \\
  {{ :a6.png?600 |}}
-(calculation of road endpoint angles)
+                                                                              Calculation of road endpoint angles
 \\
 \\
  {{ :a7.png?600 |}}
-(angle map -- blueish values represent small angles while red values represent large angles)
+                                                  Angle map -- blueish values represent small angles while red values represent large angles
 \\
 \\
@@ Line 92: / Line 92: @@
 \\
  {{ :a8.png?600 |}}
-(frictions within the “viable” cone-shaped areas)
+                                                                      Frictions within the “viable” cone-shaped areas
 \\
 \\
@@ Line 100: / Line 100: @@
 \\
  {{ :a9.png?600 |}}
-(costs to reach the “least costly” road endpoints within the cone-shaped areas --“blueish” areas represent the vicinities of road endpoints)
+                                 Costs to reach the “least costly” road endpoints within the cone-shaped areas --“blueish” areas represent the vicinities of road endpoints
 \\
 \\
@@ Line 113: / Line 113: @@
 \\
  {{ :a11.png?600 |}}
-(valid areas from where road destinations can be selected)
+                                                                Valid areas from where road destinations can be selected
 \\
 \\
  {{ :a12.png?600 |}}
-(valid probabilities to select new road destinations)
+                                                                   Valid probabilities to select new road destinations
 \\
 \\
@@ Line 126: / Line 126: @@
 \\
  {{ :a13.png?600 |}}
-(example showing some of the new road segments [cyan color] with the probabilities in their cone-shaped dominance areas in the background – the example shows only a portion of the previous images for better visualization)
+                                  Example showing some of the new road segments [cyan color] with the probabilities in their cone-shaped dominance areas in the background – the example shows only a portion of the previous images for better visualization
 \\
 \\
@@ Line 142: / Line 142: @@
 \\
  {{ :b1.png?600 |}}
-(example of road endpoints -- white cells represent the areas depicting the road endpoints, but ignoring branches that are only one cell long)
+                              Example of road endpoints -- white cells represent the areas depicting the road endpoints, but ignoring branches that are only one cell long
 \\
 \\
@@ Line 150: / Line 150: @@
 \\
  {{ :b2.png?600 |}}
-(costs to reach the “least costly” road endpoints -- “blueish” areas represent the vicinities of road endpoints)
+                                         Costs to reach the “least costly” road endpoints -- “blueish” areas represent the vicinities of road endpoints
 \\
 \\
@@ Line 158: / Line 158: @@
 \\
  {{ :b3.png?600 |}}
-(fraction map excluding all the areas too close to road endpoints)
+                                                                 Fraction map excluding all the areas too close to road endpoints
 \\
 \\
@@ Line 166: / Line 166: @@
 \\
  {{ :b4.png?600 |}}
-(costs to reach the “least costly” road segment, but excluding the areas too close to the road endpoints)
+                                              Costs to reach the “least costly” road segment, but excluding the areas too close to the road endpoints
 \\
 \\
@@ Line 172: / Line 172: @@
  {{ :b5.png?600 |}}
-(directions that must be followed to reach the “least costly” road segment, but excluding the areas too close to the road endpoints)
+                                  Directions that must be followed to reach the “least costly” road segment, but excluding the areas too close to the road endpoints
 \\
 \\
@@ Line 181: / Line 181: @@
  {{ :b6.png?600 |}}
-(probabilities, but excluding areas too close and too far from existent road segments)
+                                                        Probabilities, but excluding areas too close and too far from existent road segments
 \\
 \\
@@ Line 190: / Line 190: @@
  {{ :b7.png?600 |}}
-(example showing some of the new road segments [cyan color] with the probabilities in the background – the example shows only a portion of the previous images for better visualization)
+                              Example showing some of the new road segments [cyan color] with the probabilities in the background – the example shows only a portion of the previous images for better visualization
 //
 //
@@ Line 209: / Line 209: @@
  {{ :c1.png?600 |}}
-(zoom showing the road split into segments with unique ids – it shows only a portion of the following images for better visualization)
+                                Zoom showing the road split into segments with unique ids – it shows only a portion of the following images for better visualization
 .	Additionally, a cost map depicting the costs to reach the “least costly” road segments is also calculated.
@@ Line 216: / Line 216: @@
  {{ :c2.png?600 |}}
-(costs to reach the “least costly” road segment)
+                                                                         Costs to reach the “least costly” road segment
 .	Next, the regions of influence of each one of the road segments are calculated and the regions that are not “appropriately” shaped are discard. A “properly” shaped region is defined by value “Road Branching Irregularity Threshold” and flag “Try To Enforce Double Road Branching”.
@@ Line 227: / Line 227: @@
  {{ :c3.png?600 |}}
-(uniform friction map delimiting the region boundaries)
+                                                                        Uniform friction map delimiting the region boundaries
 \\
 \\
@@ Line 235: / Line 235: @@
 \\
  {{ :c4.png?600 |}}
-(direction map showing the directions that must be followed to reach the “closest” road segment)
+                                              Direction map showing the directions that must be followed to reach the “closest” road segment
 \\
 \\
  {{ :c5.png?600 |}}
-(zoom showing some details in the direction map above)
+                                                                     Zoom showing some details in the direction map above
 \\
 \\
@@ Line 247: / Line 247: @@
 \\
  {{ :c6.png?600 |}}
-(road segment dominance areas)
+                                                                                  Road segment dominance areas
 \\
 \\
@@ Line 255: / Line 255: @@
 \\
  {{ :c7.png?600 |}}
-(“properly”-shaped dominance areas)
+                                                                               “Properly”-shaped dominance areas
 \\
 \\
@@ Line 263: / Line 263: @@
 \\
  {{ :c8.png?600 |}}
-(zoom showing the average probability of some “properly”-shaped dominance areas – it shows only a portion of the previous images for better visualization)
+                            Zoom showing the average probability of some “properly”-shaped dominance areas – it shows only a portion of the previous images for better visualization
 \\
 \\
@@ Line 271: / Line 271: @@
 \\
  {{ :c9.png?600 |}}
-(friction map corresponding to dominance areas of the selected “seeds”)
+                                                           Friction map corresponding to dominance areas of the selected “seeds”
 \\
 \\
@@ Line 279: / Line 279: @@
 \\
  {{ :c10.png?600 |}}
-(costs to reach the road segment in the dominance area)
+                                                                 Costs to reach the road segment in the dominance area
 \\
 \\
  {{ :c11.png?600 |}}
-(direction map showing the directions that must be followed to reach the road segment in the dominance area)
+                                  Direction map showing the directions that must be followed to reach the road segment in the dominance area
 \\
 \\
@@ Line 291: / Line 291: @@
 \\
  {{ :c12.png?600 |}}
-(probability regions with unique ids)
+                                                                               Probability regions with unique ids
 \\
 \\
@@ Line 299: / Line 299: @@
 \\
  {{ :c13.png?600 |}}
-(valid probabilities)
+                                                                                       Valid probabilities
 \\
 \\
@@ Line 307: / Line 307: @@
 \\
  {{ :c14.png?600 |}}
-(example showing some of the new road segments [cyan color] with the probabilities and all dominance regions [valid and invalid] in the background -- the example shows only a portion of the previous images for better visualization)
+                               Example showing some of the new road segments [cyan color] with the probabilities and all dominance regions [valid and invalid] in the background -- the example shows only a portion of the previous images for better visualization
+\\
+\\
+//
+//
+====Build Road Lattice====
+//
+//
+<note tip>Lattices are built by connecting two or more road branches. Lattice road segments are parallel segments built alongside non-branched roads that connect branches sprouting from that same base road.</note>
+//
+//
+==Algorithm==
+\\
+\\
+<note important>The lattice construction tool, unlike the other road construction algorithms, receives two road network maps: a map that does not include the road segments used as branching points for the lattice (referred as “base roads”) and a map that includes all the roads (referred as “roads with branches”).</note>
+\\
+\\
+.	When the “Allow Lattice Segments Around Base Road Endpoints” is set to false, the algorithm starts by calculating a map depicting only the cells representing the endpoints of the “base roads” (roads not including the lattice branching points). Endpoints are detected using a technique described by in the paper Convolution Approach for Feature Detection in Topological Skeletons Obtained from Vascular Patterns (psu.edu). Each endpoint is assigned a unique id value. Optionally, branches in features that are only one-cell long can be ignored. The feature map must be provided in their canonical representation.
+\\
+\\
+ {{ :d1.png?600 |}}
+                              Example of road endpoints -- white cells represent the areas depicting the road endpoints, but ignoring branches that are only one cell long
+\\
+\\
+.	Then, it calculates the cost and direction map to reach the “closest” road endpoint among those identified in the previous step.
+ \\
+\\
+ {{ :d2.png?600 |}}
+                                                                         Costs to reach the “closest” road endpoint
+ \\
+\\
+ {{ :d3.png?600 |}}
+                                           Direction map showing the directions that must be followed to reach the “closest” road endpoint
+\\
+\\
+.	The direction map is then used to calculate the area of dominance of each one of the road endpoints.
+ \\
+\\
+ {{ :d4.png?600 |}}
+                                                                                   Road endpoint dominance areas
+\\
+\\
+.	Now, for each endpoint dominance area, it calculates the angle (in degrees) between all cells and the corresponding feature endpoint vector. The calculation uses theta = acos(dot(u, v) / (mod(u)*mod(v))), where u is the vector representing the feature endpoint direction (which is also calculated for each of the endpoints, using the same technique described in the paper Convolution Approach for Feature Detection in Topological Skeletons Obtained from Vascular Patterns (psu.edu)) and “v” is the vector representing the direction of the new possible feature segment. The direction of each one of the endpoints is a discrete value and uses one the following eight possible representations: NW=1, N=2, NE=3, E=4, SE=5, S=6, SW=7, W=8 and Undefined=0.
+ \\
+\\
+ {{ :d5.png?600 |}}
+                                                                                  Calculation of road endpoint angles
+\\
+\\
+  {{ :d6.png?600 |}}
+                                           Road endpoint angle map -- blueish values represent small angles while red values represent large angles
+\\
+\\
+.	The next step is the calculation of another cost map. This time, the cost represents the cost, in total distance, to reach the “closest” road segment from “base roads”.
+ \\
+\\
+ {{ :d7.png?600 |}}
+                                                            Costs, in total distance, to reach the “closest” road from “base roads”
+\\
+\\
+.	Then, the cost map calculated in the previous step, the road endpoint angle map, and the parameters “Allow Lattice Segments Around Base Road Endpoints”, “Lattice Lane Width”, and “Maximum Distance From Base Road” are used to construct lanes along the “base roads”. Each lane is assigned a unique id.
+ \\
+\\
+ {{ :d8.png?600 |}}
+                                                                                “Base road” lanes with unique ids
+\\
+\\
+.	Another cost map is calculated. This one shows the cost, in total distance, along the lanes to reach the “closest” segment from the “roads with branches” that intercepts each of the lanes. The resulting map automatically discard all the lanes that do not intercept at least one segment from the “roads with branches”.
+ \\
+\\
+ {{ :d9.png?600 |}}
+                                                                              Costs to reach road segments intercepting the lanes
+\\
+\\
+.	Those costs are also used to discard the sections of the lanes that to not satisfy the “Maximum Lattice Segment Extension” criteria and produce another map of valid-lane sections. Costs greater than that value indicate lane sections that might generate lattice segments longer than expected.
+\\
+\\
+.	With those valid-lane sections, it calculates a cost and direction map to reach the “closest” “road with branches” segments intercepting the lanes. It is worth noting that the resulting cost map can be remarkably similar, or even indistinguishable, from the cost map calculated above. This happens  if the “Maximum Lattice Segment Extension” is
+ \\
+\\
+ {{ :d10.png?600 |}}
+                                                                Costs to reach the “closest” road segments intercepting the valid-lane sections
+\\
+\\
+ {{ :d11.png?600 |}}
+                                                Directions that must be followed to reach the “closest” road segments intercepting the valid-lane sections
+\\
+\\
+.	Then, the direction map is used to calculate the dominance area of each “roads with branches” segments intercepting the valid-lane sections. A unique id is assigned to each one of the areas found.
+ \\
+\\
+ {{ :d12.png?600 |}}
+                                                         Dominance areas of the “road with branches” segments intercepting the valid-lane sections
+\\
+\\
+.	Now, the algorithm selects the “road with branches” segments intercepting the lanes where a new lattice segment should start. For that, it first identifies the segments intercepting the lanes and assigns to them the average probability of all cells contained in the corresponding dominance area. Then, it tries to select one cell from the “road with branches” segments that intercept the lanes for each one of the lane ids.
+ \\
+\\
+ {{ :d13.png?600 |}}
+                                                   Zoom showing the probabilities assigned each “road with branches” segments intercepting lanes
+\\
+\\
+.	The lattice start cells are used to calculate another cost and direction maps showing the costs to reach the lattice cell in the corresponding lane.
+ \\
+\\
+ {{ :d14.png?600 |}}
+                                                                      Costs to reach the lattice start cell in each lane
+ \\
+\\
+ {{ :d15.png?600 |}}
+                                                        Directions that must be followed to reach the lattice start cell in each lane
+\\
+\\
+.	Now, the algorithm selects the “road with branches” segments intercepting the lanes where a new lattice segment should end. Again, it first identifies the segments intercepting the lanes, excluding the segments where the lattice segment should start, and assigns to them the average probability of all cells contained in the corresponding dominance area. Then, it tries to select one cell from the “road with branches” segments that intercept the lanes for each one of the lane ids.
+\\
+\\
+.	As the last step, the selected new road destinations, together with the last direction map, are used to construct segments connected to the existent road network.
+ \\
+\\
+ {{ :d16.png?600 |}}
+                          Example showing some of the new road segments [cyan color] -- the example shows only a portion of the previous images for better visualization
 \\
 \\
+ {{ :d18.png?600 |}}
+                          Example showing some of the new road segments [cyan color] -- the example shows only a portion of the previous images for better visualization