Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
new_road_constructor [2021/07/07 15:35]
argemiro
new_road_constructor [2021/07/07 18:10] (current)
argemiro
Line 47: Line 47:
  
  {{ :a1.png?600 |}}  {{ :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
  
 2. 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. 2. 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 |}}  {{ :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 |}} {{ :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 |}}  {{ :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 |}}  {{ :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 |}}  {{ :a6.png?600 |}}
-(calculation ​of road endpoint angles)+                                                                              Calculation ​of road endpoint angles
 \\ \\
 \\ \\
  
  {{ :a7.png?600 |}}  {{ :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 |}}  {{ :a8.png?600 |}}
-(frictions ​within the “viable” cone-shaped areas)+                                                                      Frictions ​within the “viable” cone-shaped areas
 \\ \\
 \\ \\
Line 100: Line 100:
 \\ \\
  {{ :a9.png?600 |}}  {{ :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 |}}  {{ :​a11.png?​600 |}}
-(valid ​areas from where road destinations can be selected)+                                                                Valid areas from where road destinations can be selected
 \\ \\
 \\ \\
  
  {{ :​a12.png?​600 |}}  {{ :​a12.png?​600 |}}
-(valid ​probabilities to select new road destinations)+                                                                   ​Valid ​probabilities to select new road destinations
 \\ \\
 \\ \\
Line 126: Line 126:
 \\ \\
  {{ :​a13.png?​600 |}}  {{ :​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 141: Line 141:
 \\ \\
 \\ \\
-  ​{{ :b1.png?600 |}} + {{ :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 |}}  {{ :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 |}}  {{ :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 |}}  {{ :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 |}}  {{ :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 |}}  {{ :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 |}}  {{ :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 
 +// 
 +// 
 +====Build Regular Branches==== 
 +// 
 +// 
 +<note tip>The original roads are updated with regular branched roads connecting the newly selected destinations with their corresponding road segments. Unlike irregular branches, regular branch segments only travel through its corresponding segment region, therefore following a straight line. They are also perpendicular to the original road.</​note>​ 
 +// 
 +// 
 +==Algorithm== 
 +\\ 
 +\\ 
 +<note warning>​The pictures shown below may not cover the same area for better visualization</​note>​ 
 + 
 +1. First, the existent roads are split into segments of approximately “Road Branching Lane Width” cells. Segments that are too small or cannot be successfully grouped are discarded. Each segment is assigned a unique id. 
 +\\ 
 +\\ 
 + 
 + {{ :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 
 + 
 +2. Additionally,​ a cost map depicting the costs to reach the “least costly” road segments is also calculated. 
 +\\ 
 +\\ 
 + {{ :c2.png?600 |}} 
 +  
 +                                                                         Costs to reach the “least costly” road segment 
 + 
 +1. 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”. 
 +\\ 
 +\\ 
 + 
 +a. The region boundaries are delimited using the “Maximum Road Travel Cost” and the cost map calculated previously. The result represents a uniform friction map, where all the values in the non-null areas are the same. 
 +\\ 
 +\\ 
 + {{ :c3.png?600 |}} 
 +  
 +                                                                        Uniform friction map delimiting the region boundaries 
 +\\ 
 +\\ 
 + 
 +b. The uniform friction map is used to calculate a direction map showing the directions that must be followed, for each cell, to reach the “closest” road segment. 
 +\\ 
 +\\ 
 + {{ :c4.png?600 |}} 
 +                                              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 
 +\\ 
 +\\ 
 + 
 +c. The direction map is used to calculate the dominance area of each one of the road segments. Each dominance area is assigned the same unique id used by its corresponding road segment. 
 +\\ 
 +\\ 
 + {{ :c6.png?600 |}} 
 +                                                                                  Road segment dominance areas 
 +\\ 
 +\\ 
 + 
 +d. The direction map and the segment dominance map are then used to calculate which areas are “properly” shaped. Areas that do not satisfy the “proper” shape criteria, according to the “Road Branching Irregularity Threshold” value and “Try To Enforce Double Road Branching” flag are discarded. Typically, areas with “proper” shapes are very regular, having cells of only two opposite directions [e.g., N/E (North/East), NW/SE (North-West/​South-East)] in approximately the same numbers. 
 +\\ 
 +\\ 
 + {{ :c7.png?600 |}} 
 +                                                                               ​“Properly”-shaped dominance areas 
 +\\ 
 +\\ 
 + 
 +2. The probabilities covered by “properly”-shaped dominance areas are combined, as their average, and the resulting value is assigned to the cells of the corresponding road segment. This new probability map will be used to select “seeds”. These “seeds” are road segments from where new regular branches can sprout. 
 +\\ 
 +\\ 
 + {{ :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 
 +\\ 
 +\\ 
 + 
 +3. Once the specified “Number Of Road Branching Seeds” are selected, a new friction map covering only the dominance area of the selected “seeds” is produced. 
 +\\ 
 +\\ 
 + {{ :c9.png?600 |}} 
 +                                                           ​Friction map corresponding to dominance areas of the selected “seeds” 
 +\\ 
 +\\ 
 + 
 +4. The resulting friction map is used to calculate a cost and direction maps to reach the road segment in the corresponding dominance area.  
 +\\ 
 +\\ 
 + {{ :​c10.png?​600 |}} 
 +                                                                 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 
 +\\ 
 +\\ 
 + 
 +5. Depending on the state of the flags “Try To Enforce Double Road Branching” and “Use Random Road Branching”,​ the dominance areas where “seeds” were selected previously are also split in one or two probability areas depending whether or not double road branching should be enforced on that area. Basically, the area is split in two when double road branching is not used, but it is kept intact, otherwise. Double road branching occurs when a seed segment sprouts two new road branches, one for each side of the road. Each one of the resulting probability areas is assigned a unique id. 
 +\\ 
 +\\ 
 + {{ :​c12.png?​600 |}} 
 +                                                                               ​Probability regions with unique ids 
 +\\ 
 +\\ 
 + 
 +6. A new probability map is produced filtering the valid probabilities according to the “Minimum/​Maximum Road Travel Cost” and the values of the cost map to reach the “least costly” road segment. This new probability and the map depicting the probability areas calculated in the previous step are then used to select the new road destinations. 
 +\\ 
 +\\ 
 + {{ :​c13.png?​600 |}} 
 +                                                                                       Valid probabilities 
 +\\ 
 +\\ 
 + 
 +7. 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. 
 +\\ 
 +\\ 
 + {{ :​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 
 +\\ 
 +\\ 
 +// 
 +// 
 +====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>​ 
 +\\ 
 +\\ 
 +1. 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 
 +\\ 
 +\\ 
 + 
 +1. 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 
 +\\ 
 +\\ 
 +2. 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 
 +\\ 
 +\\ 
 +3. 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 
 +\\ 
 +\\ 
 +4. 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” 
 +\\ 
 +\\ 
 +5. 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 
 +\\ 
 +\\ 
 +6. 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 
 +\\ 
 +\\ 
 +7. 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. 
 +\\ 
 +\\ 
 +8. 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 
 +\\ 
 +\\ 
 +9. 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 
 +\\ 
 +\\ 
 +10. 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 
 +\\ 
 +\\ 
 +11. 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 
 +\\ 
 +\\ 
 +12. 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. 
 +\\ 
 +\\ 
 +13. 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