[doc][streets] From Way-Sections to Triangles

[polarkernel]

This will become a rough description of the process pipeline from way-sections to triangles, including the most important data model charts. I will edit this post several times until the pipeline description is complete. Please do not yet post here until I have finished this text.

• Definitions

Edits: 24.03.2022: the link to definitions

[polarkernel]

WayNetwork

Starting point of the process is the section-network, implemented by the class WayNetwork. This class holds all way-sections of the scene. It is implemented as a undirected multigraph, which means that every way-section is stored in both directions, once from source to destination and once inverse. The key of the first dictionary is a mathutils.Vector (called Vectorfrom now on) of the source vertex of the section, its value is again a dictionary. The key of this next dictionary is the target Vectorof the section, while its value is a listof way-sections that fit to these vectors. Source and target vertices of way-sections are intersections, end-points of dead-end ways or vertices, where the category tag changes. Different way-sections may have the same start- end endpoints, but different paths, therefore the list.

The class WaySectionholds the attributes of a way-section. The category is the string of the category tag of the way. path is a list that holds the vertices of all original OSM way-segments that form the way-section, including sourceand target.

The class WayNetwork has a lot of methods to support its construction and maintenance, not mentioned here. To continue in the process pipeline, only the method getCycles() is important. It tries to follow the way-segments in counter-clockwise order and, depending on the result, delivers three types of objects, cycles, islands and solitaires.

                   Cycle                                 Island                                Solitaire

• A cycle is a list of way-sections (class WaySection), that form a base cycle of the network in counter-clockwise order. It is the main object searched for to continue.
• An island is again a list of way-sections (class WaySection), but this time formed by a cycle, that is not connected to the rest of the network. Its order is clockwise.
• A solitaire consists of way-sections (class WaySection), also collected in a list, that are not connected to the rest of the network, but do not form a cycle.

Note that cycles and islands are not yet polygons, they are just lists of way-segments. The method getCycles() delivers three lists, cycleSegs, islandSegs, and solitaireSegs, which collect all the above objects.

[polarkernel]

GraphCycle

The next step in the processing pipeline is the construction of graph-cycles, which are stored in the class GraphCycle. Let me first describe how the results of the method getCycles() of the class WayNetwork is processed to become a graph-cycle.

                   Cycle                               Polygon                                Spurs

From the list cycleSegs, all shared way-segments are removed, because they would form a degenerated polygon. The left image above shows that dead-end ways form equal segments that run in opposite direction. These segments, called spurs, consist currently only of a start- and end-vertex of the class Vector, because in the current version they remain unused. The red lines in the right image shows these spurs. In most cases, the cycles do not have spurs, so that only the surrounding polygon is available. The polygon itself (middle image) without the spurs is converted to a pyGEOS polygon of the class Polygon.

However, for some cycles, the situation is more complicated:

                   Cycle                          Polygon with Holes                            Spurs

Believe it or not, the cycle in the left image is one single loop in counter-clockwise order. After removing the shared segments as spurs, several cycles remain, as depicted in the middle image. Because they are ordered, one can just pick up a segment and follow its order until the start-vertex is reached again. The inner cycles now are ordered clockwise. The outer border becomes the exteriorof a Polygoninstance, while the inner cycles are collected as interiors(holes) of the same Polygoninstance. Note that the inside of these holes is detected as a different cycle by getCycles() of the class WayNetwork and stored in the list cycleSegs.

The class GraphCycle holds the required data. The removal of spurs and the parsing for holes is done by the method cleanCycle(). segListholds the way-sections delivered by the WayNetwork. The polygon with its holes created by cleanCycle() is stored as first element in the list tiles. The usage of spursis not yet clear, it will be replaced maybe later. The role of the other attributes and methods will be explained below.

[polarkernel]

Islands

One of the results of parsing the section-network by the method getCycles() of the class WayNetworkis a list of island segments islandSegs. Graph-cycles, that are not connected to the rest of the network create two types of cycles, one for the inner cycle (green in the image below) in counter-clockwise order, which is a standard cycle delivered in cycleSegs, and one for the outer cycle (red in the image below) in clockwise order, which can be found in islandSegs.

The inner cycle (that may also have streets inside) is later triangulated like all standard cycles. To get triangles for the outer cycle (the other side of the streets) this cycle has to become a hole in its smallest enclosing cycle. To find the latter, all standard cycles have to be found that include all vertices of the island cycle and the smallest of them has to be selected. This computation is not very effective, its complexity is O(n*m), where n is the number of standard graph-cycles in the whole scene and m is the number of island cycles. Fortunately, island cycles are very rare, so that m is small or even zero in most scenes.

Once the smallest enclosing cycle is found (as an instance of the class GraphCycle), it is integrated as a hole by its method createIslandCycles(). Its spurs, if any, are removed from the island and added to the attribute spursof this class

         Island in enclosing cycle                 Polygon with hole                          Spurs

[polarkernel]

Tiles

Large graph-cycles slow down the process pipeline twofold. They define a very large enclosing circle, used in the KD-tree to search for polyline objects, which leads to a great number of polyline objects found to be tested for subtraction, while many of them are outside of the cycle. Additionally, because of their size, they include a great number of polyline objects, that have to be subtracted. The latter produces a large number of holes in the graph-cycle polygon which increases the processing time.

It has been shown that subdividing the large polygons into smaller tiles reduces the computation load drastically. This subdivision is done by the method tileLargeCycles() of the class GraphCycle. Large graph-cycles with at least one dimension of their bounding box larger than a given value MaxCycleSize(defined in _defs/roadpolygons.py) are splitted into two parts across their shorter dimension (either left to right or top to bottom). If these parts are still larger than this value, they are split again similarly. This is repeated until all of these tiles have the desired size:

     GraphCycle instance with holes                     Tiles                              New vertices

Note that this tiling removes many holes of the large graph-cycle, which additionally reduces the computation time later. The tiles created here are instances of the pyGEOS class Polygonand are collected in the list tilesof the GraphCycle instance.

But there is a disadvantage. While until here all segments and vertices of the original way-sections have been preserved, this subdivision creates new vertices on the way-segments and modifies them, shown as red dots in the right image. These new vertices will also be part of the triangles computed by the triangulation of these tiles. It will be required to mark somehow these vertices (only those that lie on a segment) as associated with the way-segments.

[polarkernel]

Object Subtraction

For objects like buildings, forest, grassland etc., mapping issues are corrected in a complicated process, connected objects are combined common blocks and then, pyGEOS polygons of class Polygonare constructed. This process is not described here, although it could lead to a side product as mapping checker of OSM-operators. It is not important for the discussion about finding the relation between way-vertices and triangle vertices.

The instances of graph-cycles (class GraphCycle) containing their tiles as pyGEOS polygons (class Polygon) are collected in a list for the whole scene. Then, the objects described above that are inside or near them are subtracted from every tile, leading to holes or or tiles with cut out snippets. These new tiles replace the tiles stored in GraphCycle. Here two examples of the results (blue: graph-cycle, black: tiles, red: holes, green: area to be triangulated):

The subtracted objects are in most cases completely inside the graph-cycle, so that no new vertices are built by intersections. However, in rare cases, this can happen anyway. In the left image an example, where an area, tagged as landuse=construction (dark green at bottom) and another, tagged as natural=wood (dark green to the left) split the tile into two parts. The right image shows the result after subtraction. The tile has been split in two parts (numbered 1 and 2), while three new vertices (red dots) were constructed as intersections. So the same issue as for the intersections due to tiling arises some times.

Splitting the tiles into parts happens however quite often at the border of the scene, as depicted in the next two images (left before and right after the subtraction). However, then the intersections are at the ways tagged as category=scene_border, which are not a real ways. These vertices (red dots) do not disturb the results.

[polarkernel]

Triangulation

The triangulation of polygons with holes is done by the class PolygonTriangulation. It accepts currently the vertices of the polygon and its eventual holes in an internal class Vertex, which inherits from the class Vector. This class includes additional attributes used internally for the triangulation. Once it is clear what the required data structure for the triangles will be, the input and output of the class PolygonTriangulation will be adapted.

For every graph-cycle instance of the class GraphCycle, the tile polygons in the attribute tiles are first preprocessed by the method cleaningForTriangulation(), which mainly solves the issues of shared vertices between the polygon and its holes. Its output is a list of vertices of the class Vertex for the tile polygon's border and a list of lists of the vertices of its holes. The triangulation is then done by the method triangulate() of the class PolygonTriangulation, which delivers a list of three vertices of the class Vectorfor every triangle. These triangles are then stored in the attribute trianglesof the GraphCycle instance. Once all tiles are processed, all triangles for the GraphCycle instance are in this list.

The basic idea for this structure was to enable an efficient search for the triangles that belong to a way-section. Starting with a way-section, its two graph-cycles left and right of it could be referenced (not yet realized) and only the triangles within these cycles have to be searched and not all triangles of the scene. But this idea has to be discussed.

Here examples of the result of the triangulation of graph-cycles:

[polarkernel]

Here is a flowchart to give an overview of the processes in the method do() of the class RoadPolygons:

[vvoovv]

segList holds the net-sections delivered by the WayNetwork.

I think that point isn't clear.

The class WayNetwork delivers the lists cycleSegs, islandSegs, and solitaireSeg. Doesn't it? When does the class NetSection come on the scene?

[polarkernel]

I think that point isn't clear. The class WayNetwork delivers the lists cycleSegs, islandSegs, and solitaireSeg. Doesn't it? When does the class NetSection come on the scene?

This is an error that occurred during my renaming actions, sorry. There is no class NetSection, I meant the class WaySection. So, the segList attribute in the GraphCycle class is a list of instances of the WaySection class. It contains the list cycleSegs previously supplied by WayNetwork. I have corrected the error in my above comment.

[vvoovv]

Is segList equal to cycleList without spurs?

[polarkernel]

Is segList equal to cycleList without spurs?

No, segList includes all sections delivered in cycleSegs, inlcuding spurs and holes, these are all sections depicted in the leftmost image of the second image row in the post about GraphCycle. As a first idea, I wanted to have them kept all together, because all triangle vertices of this cycle are in this list, so that a search for the way section belonging to a triangle vertex has to be made only within these sections. But this was the idea I had at the time when I designed this class and it may no more be valid today.

[vvoovv]

What is the difference between segList and cycleList? Do they refer to the same Python list?

[polarkernel]

What is the difference between segList and cycleList? Do they refer to the same Python list?

None. cycleList is one of the return values of the method getCycles() of WayNetwork and is stored in segList.