Streets generation

[vvoovv]

• Process the centerlines of the streets, roads and paths from OSM, eventually other OSM objects (e.g. buildings)

• Generate street geometry and project it on the terrain.

• Place street objects (streetlights, road signs, bus stops, entrances to subway, etc) in accordance with the street PML style and orient them accordingly.

A terrain may require some automatized editing.

[vvoovv]

An example of the generated detailed street geometry. Intersections form separate objects. The street geometry fits the neighbor building exactly, that's way it's considered to be the detailed one. The example is located in Rotterdam.

[vvoovv]

An example of a less detailed street geometry. The geometry of streets (without intersections) is created by extruding the street centerline. The width of a street can be estimate by finding the front facades of the buildings the street is bounded by.

[vvoovv]

The easiest alternative would be to use the fixed widths for different street types. I suggest to start from this task. And then proceed to the more detailed street width estimations described above.

[vvoovv]

The problem is how to position the street geometry on a terrain to avoid polygon fighting. An obvious solution is to use the Blender Boolean modifier to cut the gaps for the streets. However it isn't always reliable.

I created an imaginable street geometry in Blender and tried to use it as the difference operand for the Boolean modifier. Surprisingly it worked quite well but only for the Fast solver. The sample file is attached.

The imaginable street geometry:

The gap cut in the terrain using the street geometry:

[polarkernel]

The easiest alternative would be to use the fixed widths for different street types. I suggest to start from this task. And then proceed to the more detailed street width estimations described above.

I agree with your proposition. However, I think it will be required to divide the ways into road sections and road intersections. While a simple template using fixed widths for different street types may be fine for road sections, intersections may require a more sophisticated approach to make them look realistic. Eventually, some thoughts and ideas from OSM-Based Automatic Road Network Geometries Generation on Unity by Xingjiang Yu may be applied.

[vvoovv]

However, I think it will be required to divide the ways into road sections and road intersections.

Yes, I implied that but I didn't mention that explicitly.

[vvoovv]

An older paper, also a student work (semester thesis): Procedural Construction of Streets.

[vvoovv]

Eventually, some thoughts and ideas from OSM-Based Automatic Road Network Geometries Generation on Unity by Xingjiang Yu may be applied.

I reviewed his thesis. His approach may be used as a starting point. However some clusterization of the OSM ways will be required to get meaningful results. The cluster of the OSM way are bounded by the magenta lines on the image below:

[polarkernel]

I agree, building such clusters should be the first task. May I suggest a few definitions of terms so that we are each talking about the same thing during the discussion? Here they are:

• Way: OSM way, as represented by the class Way.
• Way-Segment: OSM part of a Way, represented by the class WaySegment.
• Way-Crossing: A node where three or more Way-Segments meet each other. *1)
• Way-Section: A sequence of Way-Segments between two limiting nodes that do not contain any other limiting nodes. Limiting nodes are Way-Crossings, end-nodes and inter-category nodes. The Way-Segments may belong to different Ways.
• Way-Network: Graph with Way-Crossings as nodes and Way-Sections as edges. Maybe useful to identify Road-Crossings.
• Way-Cluster: Ordered collection (from left to right for example) of Way-Sections that are more or less parallel. May include multiple lanes and also cycleways, sidewalks, railway=tram and similar. But may also contain only one single Way-Section. It corresponds to the sections in magenta in your image. This cluster will be important to define the rendering template.
• Way-Junction: The section around corresponding Way-Crossings. Or maybe better, The region, where three or more Way-Clusters meet each other.

*1): Not really clear. For instance in your image, there is a Way-Crossing near the left-bottom corner that will finally not result in a Way-Junction.

I am sure that this dictionary will not be final as it also includes first ideas of implementation. But at least, it's a starting point.

EDIT: 23.09.2021: Definition of Way-Section corrected. 27.09.2021: Definition of Way-Section extended by end-nodes and inter-category nodes. 29.09.2021: Road-Cluster and Road-Crossing were renamed to Way-Cluster and Way-Junction respectively.

[polarkernel]

An older paper, also a student work (semester thesis): Procedural Construction of Streets.

Very interesting paper too! I will study it in more detail.

[vvoovv]

May I suggest a few definitions of terms so that we are each talking about the same thing during the discussion?

Thank you for the very useful dictionary. We certainly need it to speak in one language.

*1): Not really clear. For instance in your image, there is a Way-Crossing near the left-bottom corner that will finally not result in a Road-Crossing.

Yes, not every Way-Crossing leads to the Road-Crossing.

[polarkernel]

I did an extensive literature search. The result is very thin. Road networks are described mainly for routing tasks, for rendering one finds almost nothing. So, as in previous projects, we will have to look for our own "simple solution" again. Therefore here some first thoughts and ideas.

To find way-crossings is quite easy, just by counting the number of way-segments per node of the polylines. If this number is 1, its an endpoint, if it is 2, it is a connection between two way-segments, for 3 it's some kind of T-junction and for 4 or more, we have a more or less complicated crossing. The following is an example result using the dataset from _berlin_karl_marxallee.osm:

T-junctions and more complex crossings form the way-crossings, as defined in my dictionary. I think it would be preferrable to transform the data at this point by some preprocessing into way-sections between way-crossings. Two operations are required for that:

• Some way-sections may consist of several ways and have to be merged at connection nodes (number=2), when both way-segments end at this node.
• Ways have to be split at way-crossings into two way-segments, when the crossing node is somewhere between the end nodes of the way.

The easiest alternative would be to use the fixed widths for different street types.

The result of the preprocessing described above could be used as starting point for this idea.

However some clusterization of the OSM ways will be required to get meaningful results.

This part will be more diffcult. I will collect ideas on how how to tackle this.

[polarkernel]

Some interesting proposals for rendering of crossings at OSM-Wiki.

[polarkernel]

How can we find road-clusters? Some first thoughts and findings.

The goal is to find more or less parallel ways that can be clustered to broad roads, which will allow to use one template for rendering. Let me use the example of _berlin_karl_marxallee.osm to discuss some points:

Let us assume that some kind of graph has been constructed that contains way-crossings and way-sections, as I mentioned in my last post. The goal would be to find the road-clusters of the Karl-Marx-Allee (orange), the Friedenstraße (white in the East) and the Lichtenberger Straße (yellow). Some constraints should be observed:

• There are more streets in this example, that are parallel, however separated by buildings. But they cannot form road-clusters.
• We should not require to test every way-section against all other way-sections for efficiency reasons. We should be able to find candidates for parallel ways.
• Although these road-clusters have a lot of crossings along their path, they form finally one road to be rendered using the same template. It would be helpful to think about the requirements (evtl. data structures) required for rendering such objects.
• The parallelity may end sonewhere in the middle of a way-section. An example ist the West end of the Karl-Marx-Allee, where the two roads separate to the roundabout. How to describe this situation for the renderer?

I found that typically, such road-clusters have oneway tags, at least, when they are separated by walls or barriers. Additionally, their name and eventually ref tags are identical. This may help to identify candidates.

To find whether they are really parallel, some ideas I found on the net may be helpful:

• A rather simple and interesting solution is described in this answer of sanser at OpenStreetMap questions. He seems to be a map-maker and has the same problem, when the map's scale does no more allow to draw two separate streets.
• An interesting approach may be the usage of so called basic geometric buffers. They are implemented in the shapely library of Python (not available in Blender) and seem to be often used for similar problems. A good description can be found here. I have converted the postscript file there to PDF and may send it to you.
• Yongyang Xu et al. describe a method where the polygons that are built by the ways are checked. They use shape descriptors to find small long polygons that may be parallel roads.
• Xiang Zhang et al. present a method based on so called natural roads. However, I didn't yet study this method in detail.

[vvoovv]

Note that Karl-Marx-Allee also has cycleways and footways. They should be also parts of the street cluster.

[polarkernel]

Note that Karl-Marx-Allee also has cycleways and footways. They should be also parts of the street cluster.

Sure. Once a cluster candidate is found, all parallel way-sections of any type have to be considered.

[vvoovv]

An idea.

A road-cluster connects two road-crossings.

If two way-sections are located between the same road-crossings, it is very likely that the way belong to the same road-cluster.

The problem is to detect road-crossings.

[polarkernel]

The problem is to detect road-crossings.

This is a task I am studying too, as sooner or later, we're going to need that anyway. Clustering crossings to complex junctions is implemented in large libraries like OSMnx, SUMO (netconvert) and ArcGIS. But I wasn't yet ablle to find descriptions of algorithms on how to do that. Well, I avoided to dive in their code (where available) untl now.

However, for the task to find way-sections to be merged to road-clusters, they are of limited help. for instance in my example of the Karl-Marx-Allee, the Lichtenberger Straße ends to the South at the scene's border without any crossing. To declare the roundabout as one single crossing, only for the detection of parallel ways, makes few sense.

[polarkernel]

Here just some illustrations for future discussions. First the result of crossing detection, but now for all kind of way-segments:

The orange ellipses show some examples of the range to be bundled as road cluster, eventually even the green range, which includes a foot-way along the Karl-Marx-Allee behind some trees (see the following image taken from Google StreetMaps, looking to West ). Note that the parking lane on the right and the (foot-?)way on the left are not included in OSM.

Here some details on the larger crossings along the Karl-Marx-Allee from West to East (click on the images to see them larger):

[vvoovv]

Here is a simple way to detect road-crossings.

• Pickup a way-crossing that wasn't added to any road crossing yet. Let's denote it WC0. A new road-crossing RC is created. The way-crossing WC0 is added to the road-crossing RC.
• Consider all unvisited way-sections attached to the way-crossing WC0. Let's denote one of those way-sections as WS. If the distance from the other way-crossing WC of the way-section WS to WC0 is less than the threshold, than the way-crossing WC is added to the road-crossing RC. The way-sections attached to the way-crossing WC0 are marked as visited.
• The same process is performed recursively for the way-crossings that were newly added to the road-crossing RC until no unvisited way-sections is left.

[vvoovv]

Lichtenberger Straße ends to the South at the scene's border without any crossing.

Way-sections attached only to a single way-crossing require a special processing. For example, if unconnected ends of a pair of those way-sections are located close enough, then the way-sections are the candidates to form a road-section.

[polarkernel]

Here is a simple way to detect road-crossings.

This was one of my first ideas. But looking at the required distances for the main crossings of the Karl-Marx-Allee (not for the roundabout, which will require a special processing), wouldn't then the places marked by a red circle also get road-crossings?

[vvoovv]

• Way-Section: Part of a Way between two Way-Crossings.

I suggest to redefine it in the following way:

Way-Section: A sequence of Way-Segments between two Way-Crossings that doesn't contain any other Way-Crossing between the Way-Crossings. The Way-Segments may belong to different Ways.

This definition includes the case when two Ways are connected with a common node and each of the Ways contain a Way-Crossing.

[polarkernel]

I suggest to redefine it in the following way:

I updated this definition in my post.

[vvoovv]

This was one of my first ideas. But looking at the required distances for the main crossings of the Karl-Marx-Allee (not for the roundabout, which will require a special processing), wouldn't then the places marked by a red circle also get road-crossings?

The crossings you marked on the map are mostly formed by footways and service ways. They can be omitted for the first pass. In the second pass the footways can be attached to the road crossings found in the first pass. Also the road crossings formed by footways are processed during the second pass. A smaller threshold distance should be used for the road crossings formed by footways.

[vvoovv]

(1) highway=footway Footways aren't considered in the first pass. A smaller threshold should be used for the footways to form road crossings.

(2) highway=residential A road cluster can be formed for the ways to the right from the road crossing.

(3) highway=footway and highway=service + _service=parkingaisle Footways and highway=service aren't considered in the first pass. A smaller threshold should be used for the footways to form road crossings. Parking aisles should be treated separately.

(4) highway=footway and highway=service + _service=parkingaisle Footways and highway=service aren't considered in the first pass. A smaller threshold should be used for the footways to form road crossings. Parking aisles should be treated separately.

(5) highway=service highway=service aren't considered in the first pass. The highway=service running parallel to highway=residential may be added to a road cluster along with the highway=residential.

(6) highway=footway Footways aren't considered in the first pass. The footway running parallel to highway=residential may be added to a road cluster along with the highway=residential.

(7) highway=service highway=service aren't considered in the first pass. The highway=service running parallel to each other may form a road cluster.

(8) and (9) highway=footway and highway=service Footways and highway=service aren't considered in the first pass. Footways and highway=service running parallel to each other may form a road cluster.

(10) highway=service and highway=service + _service=parkingaisle highway=service aren't considered in the first pass. Parking aisles should be treated separately.

(11) highway=service + _service=parkingaisle highway=service aren't considered in the first pass. Parking aisles should be treated separately.

(12) highway=footway Footways aren't considered in the first pass. A smaller threshold should be used for the footways to form road crossings.

(13) and (14) highway=footway in a cemetery Footways aren't considered in the first pass. A smaller threshold should be used for the footways to form road crossings. Some parallel footways may form a road crossing.

[vvoovv]

An algorithm will be required to detect footways located within an area (a park, a cemetery, etc).

[polarkernel]

OK, now I get your idea, I think. I propose that I start to write some experimental code based on the existing classes Way and WaySegment. I like to see some results for different scenes for a better understanding.

In a first step I would like to create a Way-Network graph with Way-Crossings (the blue and red dots in my example image) as nodes and Way-Sections as edges.

Then, based on this network, Road-Crossings can be extracted with different specifications of the way categories to be merged and the threshold distance.

[vvoovv]

OK, now I get your idea, I think. I propose that I start to write some experimental code based on the existing classes Way and WaySegment.

Ok. I created the branch streets for the experiments.

[polarkernel]

In a first step I would like to create a Way-Network graph with Way-Crossings (the blue and red dots in my example image) as nodes and Way-Sections as edges.

I just commited the first version of this experimental code. It can be executed using --roadClustering, but has not yet a renderer, the result gets displayed directly by matplotlib commands. The result is the topology of nodes, with Way-Sections plotted as straight edges. Here is an example for _berlin_karl_marxallee.osm:

T-junctions and other junctions of three Way-Sections have blue dots, more complicated crossings are depicted by red dots. I had to introduce two more type of nodes: Gray dots for End-Nodes and green dots for nodes between sections of different way categories. I assume, the last nodes will be required to limit way-sections with different render template. Therefore I propose to adapt the definition of a Way-Section to

Way-Section: A sequence of Way-Segments between two limiting nodes that do not contain any other limiting nodes. Limiting nodes are Way-Crossings, end-nodes and inter-category nodes. The Way-Segments may belong to different Ways.

I will now continue towards Road-Crossings.

[vvoovv]

Way-Section: A sequence of Way-Segments between two limiting nodes that do not contain any other limiting nodes. Limiting nodes are Way-Crossings, end-nodes and inter-category nodes. The Way-Segments may belong to different Ways.

Yes, that's a more precise definition.

[polarkernel]

I have some intermediate results. It seems that the algorithm to find road-crossing, as you proposed it here, will work. Here some first outcomes. The left image shows road-crossings, where at least one of the ways of the categories primary, secondary or tertiary takes part of the crossings and a minimal distance of 20m was used. On the right the results for the categories residential, service or cycleway and a distance of 15m.

The algorithm is not yet complete, I have to do further work on filtering the ways involved or on taking into account the results of a first pass. The next step will be the search for road-clusters that connect these road-crossings. However, it seems that common graph algorithms are the way to this result. Once I know the logic of all these steps, I will refactor the whole part to make it more streamlined and efficient.

We should start to think about how the resulting structures of all these steps should look like, so that we have the required components to render the streets finally by the addon. If for we have instance road-cluster between two road-crossings and somewhere in the middle of the it, there is a t-junction to one of the streets in the bundle, should then the road-cluster be interrupted there? I think there are many details like this to diskuss.

[vvoovv]

The crossing (3) is the intersection of Lebuser Strasse (tertiary) and Palisadenstrasse (residential). Why isn't it marked with the red cycle?

[vvoovv]

Added the test file _osm_extracts/streets/milano01.osm.

It contains a number of complex crossings.

[polarkernel]

The crossing (3) is the intersection of Lebuser Strasse (tertiary) and Palisadenstrasse (residential). Why isn't it marked with the red cycle?

As far as I can see, there is no other crossing in a range of 20m around this single crossing. I painted only the road-crossings.

[polarkernel]

Added the test file _osm_extracts/streets/milano01.osm.

Using the command line parameters

--highways --buildings --osmFilepath D:/BLOSM/osm_extracts/streets/milano_01.osm --roadClustering --setupScript D:/BLOSM/_streets/blosm/setup/mpl_facade_visibility.py

I get the error message

Downloading data for incomplete OSM relations
Downloading the file from http://overpass-api.de/api/interpreter...
HTTP Error 504: Gateway Timeout

But I don't get it for _osm_extracts/streets/rotterdam01.osm, which is also new there.

[vvoovv]

Added the test file _osm_extracts/streets/milano01.osm. It contains complex road clusters that includes cycleways, footways and tram ways:

[vvoovv]

Downloading data for incomplete OSM relations Downloading the file from http://overpass-api.de/api/interpreter... HTTP Error 504: Gateway Timeout

This happens from time to time. The solution is try it again later. However I've just committed the required file milano_01_extra.osm. This problem won't happen anymore since no download will be required anymore

[vvoovv]

Tram tracks (railway=tram) can be also the part of a road cluster.

[polarkernel]

This happens from time to time. The solution is try it again later.

I just wondered, because I expected to load it from the file with

--osmFilepath D:/BLOSM/osm_extracts/streets/milano_01.osm

I tried now again, and this time I got

Downloading data for incomplete OSM relations
Downloading the file from http://overpass-api.de/api/interpreter...
Saving the file to D:\BLOSM\osm_extracts\streets\milano_01_extra.osm...
Parsing and processing data from the file D:\BLOSM\osm_extracts\streets\milano_01_extra.osm for incomplete OSM relations

and the file _milano_01extra.osm you just added was created additionally. So I assume the first time, it was not complete.

However, here the result for _milano01.osm using an extended approach. I created the clusters for the categories primary, secondary or tertiary (with 20m distance) and expanded them in a second pass by the crossings for residential, service or cycleway (with 15m distance), see red clusters. Then the clusters for residential, service or cycleway for 15m have been created for the remaining crossings (see green clusters): You can see this, starting at line 80 of the current "code salad" in _roadclustering.py.

[polarkernel]

Tram tracks (railway=tram) can be also the part of a road cluster.

Currently, I used self.app.managersById["ways"].getAllWays() to access the way segments, where railway=tram is not included. Is there a more flexible method to access way data?

And another question: Shouldn't bridges and tunnels not be included in this process, as they may also have parallel ways?

[vvoovv]

I need a couple of days to arrange the code to process OSM ways.

[vvoovv]

And another question: Shouldn't bridges and tunnels not be included in this process, as they may also have parallel ways?

Bridges should probably form a separate cluster. All OSM ways going through the same bridge get the tag bridge=yes. Example: Deutzer Brücke in Cologne: 2 roads, 2 tram tracks and 2 paths for pedestrians and cyclists. In this case it's easier to identify that all of them belong to the same bridge: there is an area marked with _manmade=bridge which all of those OSM ways cross twice. However the area _manmade=bridge isn't always available. We can assume that all members of a bridge cluster belong to the same bridge if the area _manmade=bridge isn't available.

Tunnels. Roads typically run in the same tunnel even if they are physically separated. Parallel rail tracks typically run in the separate tunnels.

[vvoovv]

I suggest to rename road clusters to way clusters since the same approach can be applied to railway tracks.

Not sure how to rename the road crossings. Perhaps Way-Hubs?

[vvoovv]

I need a couple of days to arrange the code to process OSM ways.

I suggest to freeze the code for Tuesday and Wednesday. I'll use this time to arrange the code.

[polarkernel]

Not sure how to rename the road crossings. Perhaps Way-Hubs?

I agree, or Way-Junctions?

[vvoovv]

I agree, or Way-Junctions?

Ok, let's call Way-Junction. I'll update the definitions here.

[vvoovv]

I rearranged the code.

I still need to add tram tracks. I also want to add buildings to understand the context easier.

• networkGraph, waySectionGraph and junctions are also stored in way.manager.WayManager.
• Rendering is done in the module _mpl.renderer.waycluster.
• The main script is renamed to _setup/mplblosm.py as the main entry point.
• It's possible to have several renderers for an instance of the class way.manager.WayManager.
• The command is now (--buildings isn't needed):

  python -m script.command_line --highways --wayClustering --setupScript setup/mpl_blosm.py --osmFilepath /path/to/file.osm

• I applied the style to the rendered OSM ways similar to the map at https://www.openstreetmap.org

[polarkernel]

I rearranged the code.

How beautiful !!!!!!! Such a wonderful map, how am I supposed to calm down? This will make the task much clearer and will be of great help! Together with the buildings, it will win once again.

In the meantime I refactored the graph code and the contraction to the section-graph completely. It is now much more efficient and lean. I will introduce it in near future.

[polarkernel]

Purely by chance I found that in _milano01.osm there exist two ways that use the same way segment (in opposite directions). Is this possible or is there maybe a bug? If you like to find the segments, you may use

        wayManager.networkGraph = WayNetwork()
        for w,way in enumerate(wayManager.getAllWays()):
            for s,segment in enumerate(way.segments):

One segment is w==956 and s==1 and the other is w==955 and s==2.