[streets] Streets and intersections, first experiments

[polarkernel]

In order to create realistic streets and intersections, many of their features have to be invented by the software, as they are not provided by the OSM data. In the following posts, first problems and findings, experienced with experimental code, are discussed.

[polarkernel]

I'd like to mention the approach with the classes Vector and Edge that we discussed in https://github.com/prochitecture/blosm/issues/40 starting from https://github.com/prochitecture/blosm/issues/40#issuecomment-1087782833. I use this approach to find the neighbors of a building or a building part.

This won't work here.

The polygons 1 and 2 don't have shared edges. This is the problem I tried to illustrate with this image. The edges given by vertices AB and CD are collinear, these vertices are on one line, but they are all different. One could search for pairs of collinear edges, but this is an O(n²) process.

[vvoovv]

How does it happen that the polygons don't have shared edges?

[polarkernel]

How does it happen that the polygons don't have shared edges?

From the section-network, graph-cycles are extracted that consist completely of way-sections as edges. These cycles are then split into tiles, as described here. But like this, as already described and illustrated there, new vertices on the way-segments are created and modify them. These new vertices remain in the graph-cycle and are not transferred to the neighbor graph-cycles. I assume, in my above illustration, almost all vertical edges are only tile edges and the vertices marked with letters are such new vertices.

I tried it with different approaches, it is almost impossible to transfer these new vertices to the neighbor graph-cycles, using the current structure of the section-network. Furthermore, I've been thinking about completely revising this graph structure for a while now. Many historical elements have remained in it, which I would build differently from today's perspective. Maybe I should tackle this now, but I don't know how you plan the schedule for this project.

One more thing about the reason I was seeking for neighborhoods: In image processing, we know a method called hysteresis thresholding. A high threshold detects pixels, that belong for sure to the object to be detected (mainly used for edge detection). However, pixels that are above a lower threshold, called candidate pixels, are also accepted to belong to the object, when they are neighbors of already detected pixels. I think, this principle could successfully be applied to the polygons of the bounding rectangle method.

[vvoovv]

I've been thinking about completely revising this graph structure for a while now. Many historical elements have remained in it, which I would build differently from today's perspective. Maybe I should tackle this now, but I don't know how you plan the schedule for this project.

If this big refactoring if the graph structure is needed to solve the problem, I suggest to do it.

[vvoovv]

I think the triangulation of the remaining areas will be still needed to cover the whole area of interest with polygons.

[polarkernel]

If this big refactoring if the graph structure is needed to solve the problem, I suggest to do it.

Before I do that, I will try if it is possible to store the neighborhoods of the tiles during the splitting. Then one could use the neighbors first between the tiles and then between the graph-cycles. The result should then be a group of way-sections forming a way-cluster.

I think the triangulation of the remaining areas will be still needed to cover the whole area of interest with polygons.

Sure, I will keep this feature alive.

[polarkernel]

Before I do that, I will try if it is possible to store the neighborhoods of the tiles during the splitting.

This is not required. I have found a method to generate the complete neighborhood network of all 747 polygons of the file _beijingcenter.osm (which as far as I know is the largest of our data files) within 20 msec. The big refactoring of the way-section network can be postponed until we can put all the parts together, but there is still a long way to go until then.

In order to be able to study the relations a little more deeply, I generated the ground truth for the file _bratislava_oldtown.osm in painful work. I marked all polygons that should, in my opinion, be part of the way-clusters. A first finding was that it is better to use the full graph-cycles, instead of tiling them. Because most of them are quite long and thin, they are easily detected by the bounding rectangle method. The automatic detection shall be based on a minimum elongation factor and a maximum width of the rectangles. Let me discuss this using a plot of all pairs of these values, where the red dots are the polygons of the ground truth and the blue crosses those from the remaining polygons:

As a first observation, one can see that these criteria will produce false positives and possibly false negatives, as the points are mixed. But I also wondered what the three outliers marked by the green arrows are. I found that these are very long but slightly curved way-pairs. To handle them, I added a step for polygons with a high elongation factor but a width below the width threshold. These are split into tiles and then examined again, where then, they are correctly detected as part of a cluster.

With the polygon neighborhood now available, I added as an experiment the idea of a hysteresis threshold. Polygons with an elongation factor larger than a threshold hiThresh (and a width below widthThresh) are immediately detected as part of a way-cluster. Polygons with an elongation factor larger than a lower threshold loThresh are also detected (when they meet also the width criteria), but only when they are neighbors of already detected polygons.

If you like, you may experiment using the recent commit in the branch _streetsintersections. You find the above parameters starting at line 175 of the file _roadintersections.py. The polygons found immediately are drawn in green, and those detected by hysteresis are drawn in cyan. I am interested whether we are already close to what is required or not.

[vvoovv]

The module lib.CompGeom.boundingRectangle is missing

[polarkernel]

The module lib.CompGeom.boundingRectangle is missing

File is added now. Sorry, didn't update .gitignore.

[vvoovv]

I spotted an issue:

Those dead-end ways should be a part of a cluster. The current method doesn't process them.

[vvoovv]

Would it possible to switch off the visualization of intersections? I am expecting to see a more clear picture without the areas for the intersections.

[polarkernel]

Would it possible to switch off the visualization of intersections? I am expecting to see a more clear picture without the areas for the intersections.

To switch off plotting of the intersections, comment out the line 143 in _roadintersections.py, to switch off the transitions, comment out line 139.

[vvoovv]

File _facade_visibility/berlin_karl_marxallee.osm.

The footway should be a part of the cluster.

[vvoovv]

File _facade_visibility/moscow_leningraskiprospekt.osm.

The ways within the marked area should form a single cluster.

[vvoovv]

Those dead-end ways should be a part of a cluster. The current method doesn't process them.

Just think aloud.

A dead-end can be connected to the nearest OSM node belonging to a way. Then a check can be performed if the resulting graph-cycle has an existing cluster as a neighbor or if the graph-cycle forms a new cluster.

[polarkernel]

The footway should be a part of the cluster.

This footway is up to 32 m away from the cycleway. Setting widthThresh = 32.and loThresh = 0.65 (because of the shorter cycles at the left) make it part of the cluster. But using these parameters produces fatal effects in other datasets.

[polarkernel]

Those dead-end ways should be a part of a cluster. The current method doesn't process them.

What is the desired result? Am I right when I assume two clusters like below, although there are no vertices at the split position for the other ways?

[polarkernel]

Found an interesting paper:

Xianyong Gong*, Fang Wu, Ruixing Xing, Jiawei Du, and Chengyi Liu LCBRG: A lane-level road cluster mining algorithm with bidirectional region growing Open Geosciences 2021; 13: 835–850

It would be interesting to get the reference [47] in this article, but I found it only in Chinese. This could be helpful to find parallel ways. I try to translate it.

[vvoovv]

It would be interesting to get the reference [47] in this article, but I found it only in Chinese. This could be helpful to find parallel ways. I try to translate it.

It seems to exist only in Chinese.

[vvoovv]

What is the desired result?

I see it this way:

Similar to the virtual way-section scene_border, a virtual section is created to connect the dead-end with the neighbor way.

[polarkernel]

I still don't fully understand how you intend to finally use these clusters. In my understanding, these are polygons that can be used to render the carriage lanes and their intermediate space using seamless textures. To be able to do this, the way-sections must all be more or less "parallel" and similarly distributed over the whole length. Let me discuss my questions using a part of the Karl-Marx-Allee, that I rotated a bit to save space:

I colored now the carriage lanes of two possible clusters in red and in green:

Now my questions:

• What about the footways in the red cluster, that are more or less vertical? Should the cluster be split there into multiple clusters?
• Below the primary roads, there are two dead-ends (footways too). Should these also be connected by virtual way-sections? I could also detect them without the construction of a cycle.
• On the left, the primary roads are bent a bit to enter the roundabout. Should the cluster end before, as it will not be possible to use seamless textures there?
• The way-sections each end when another way crosses them. The red part of the southern carriageway of the Karl-Marx-Allee therefore consists of four successive sections (one of them because of the change in the number of lanes). However, the intersections between these parts are not in the same place as those of the northern carriageway. Would these become splitting points of the cluster?

However, when I look at your comment here, I have the impression that it would be enough to have the whole cluster polygon and a list of the carriage lane and intersection polygons enveloped by it.

[vvoovv]

Good questions :)

I can't give exact answers for them right now. The problem is quite complex due to uncertainties and mistakes caused by mappers.

I'll post some ideas in the next message.

[vvoovv]

Added the test file _streets/berlinfriedrichstrasse.osm with interesting cases: an island between two carriage ways. The islands are formed by subway entrances and Checkpoint Charlie.

[vvoovv]

Suppose that an elongated graph-cycle forms a stripe of the equal width.

If there are no objects inside the graph-cycle, then the width of the upper and lower ways is defined by the center-line of the graph-cycle provided that those ways have the same type.

If there are some objects inside the graph-cycle (for example, grass), then width of the upper and lower ways is set to a smaller value than in the first case to accommodate the object inside the graph-cycle. The remaining space between the upper and lower ways is filled during rendering (for example with grass or pavement).

The width of the ways can be decreased iteratively to avoid collision with the ways of the neighbor elongated graph-cycles.

[vvoovv]

Now consider the case when an elongated graph-cycle doesn't form a stripe with the equal width.

Each way is offsetted with some width. If the offsetted ways collide, the offset widths are decreased until the offsetted ways don't collide. The remaining space is filled during rendering (for example with grass or pavement).

[polarkernel]

To comment your above propositions, I added two new test files to the branch _osmextracts: /streets/taipei.osm /streets/berlin_frankfurter_allee.osm These will be also helpful for other tests, the former includes an interesting intersection, while the latter combines the streets with railways.

I will comment quite verbose in order to transport some of my numerous experiences I made during my experiments.

Suppose that an elongated graph-cycle forms a stripe of the equal width.

How to measure?

To distinguish this case from the second one, a metric has to be defined on how to measure "equal width". Once known, it could also be used to find elongated graph-cycles. The most precise metric could be a projection distance metric, as described in the paper I linked here. It comes closest to what I would do myself, but it is a costly method. I also studied other similarity metrics like those implemented here (applied to way-sections), but for this task, they are not helpful, and they are even more expensive.

How to find the centerline?

If there are no objects inside the graph-cycle, then the width of the upper and lower ways is defined by the center-line of the graph-cycle provided that those ways have the same type.

To find the centerline of a polygon is not easy. The best way described in literature is to use a straight skeleton, as for instance also described in this paper. As the ways are drawn manually by the operators, they are almost never exactly parallel, while the proposition requires at least to find the smallest distance between the ways. I am not sure whether this width could be found already from the projection distance metric.

Wouldn't we get changes of way widths?

If there are some objects inside the graph-cycle (for example, grass), then width of the upper and lower ways is set to a smaller value than in the first case to accommodate the object inside the graph-cycle.

Here I have my biggest concerns. If we look for instance at the intersections of the ways of the Karl-Marx-Allee with the grass stripes between them, then we see that the distance is different for every graph-cycle. This would lead to a changing way width along these ways. The difference can even reach dramatic proportions if there is no more object in between in a subsequent cycle. Here is an example, I measured in the scene in _berlin_frankfurterallee.osm:

In the left graph-cycle, due to the grass stripe, the width of one way would become 8.8 m, while in the right cycle, it would be 14.6 m, because there is no more grass there. Similar issues would arise along the Friedenstraße in _berlin_karl_marxallee.osm.

The method is non-local

The width of the ways can be decreased iteratively to avoid collision with the ways of the neighbor elongated graph-cycles.

There may be several graph-cycles to be involved in the adaption of way widths, see for instance the following example from taipei.osm:

Starting with one graph-cycle, we may find a width. Its neighbor cycle may require a smaller width, and the next neighbor's neighbor maybe again. The result has then to be transferred through all the involved graph-cycles. Of course, this can be implemented, but it is very complicated.

Offsetting and collision detection

Each way is offsetted with some width. If the offsetted ways collide, the offset widths are decreased until the offsetted ways don't collide.

This is a very expensive algorithm. For each iteration, two lines have to be expanded, and then the two polygons have to be intersected.

My summary

I don't really like to make the width of ways dependent on objects in the intermediate space and on drawing inaccuracies by the operator. I think a varying way width quickly looks unrealistic. Why not cut a piece of grass like I do on my driveway to the house, it would be much less noticeable? Naturally, this is not possible for a way intersecting a building. Then, maybe a warning sign and a repair using an editor would help.

In my experience, almost all collisions of ways with objects are due to inaccuracies of the way-positions, and not by a wrong width of the ways. In most cases, a shift of the way-position would help.

[vvoovv]

/streets/taipei.osm

By the way, the mapping of the marked ways is wrong according to OSM guidelines.

The marked ways should be mapped as a single way since there is no physical separator between them.

[vvoovv]

/streets/berlin_frankfurter_allee.osm

Note that the OSM ways 432427273, 62214794 and 62214796 have the tags:

• cycleway:right = track or cycleway:right = track
• sidewalk = right

It means that there are a cycleway and a footway to the right from the related carriageway.

The OSM way 310172805 also has the tag cycleway:right = separate, however the way forms a graph-cycle with the cycleway 993824357 and this tag should be ignored.

[vvoovv]

Why not cut a piece of grass like I do on my driveway to the house, it would be much less noticeable?

But what if two parallel ways forming a graph-cycle intersect each other?

[vvoovv]

To find the centerline of a polygon is not easy. The best way described in literature is to use a straight skeleton, as for instance also described in this paper.

For the sake of completeness I'd like also to mention the method from here. It's based on the Voronoi diagram.

[polarkernel]

/streets/berlin_frankfurter_allee.osm Note that the OSM ways 432427273, 62214794 and 62214796 have the tags:

It seems that my illustration produced a misunderstanding, the arrows were too short. There is grass in the center strip of the green graph-cycle, which limits the width of the two parallel ways to 8.8 m. The center strip of the blue graph-cycle contains no object, therefore, according to the proposed rule, the parallel ways may each have a width of 14.6 m.

The same happens along the Friedenstraße in _berlin_karl_marxallee.osm. There is grass in the green cycle and no object in the blue one:

[polarkernel]

But what if two parallel ways forming a graph-cycle intersect each other?

I will once try to find all intersection between ways and objects and also between two ways in all our datasets using brute force. Like this, we get some overview of some collision cases. This will ease the discussion about this subject.

[vvoovv]

/streets/berlin_frankfurter_allee.osm Note that the OSM ways 432427273, 62214794 and 62214796 have the tags:

It seems that my illustration produced a misunderstanding, the arrows were too short.

Your point was clear to me. I posted the cited message about the implied cycleways and footways with no relation to your example.

[vvoovv]

I will once try to find all intersection between ways and objects and also between two ways in all our datasets using brute force. Like this, we get some overview of some collision cases. This will ease the discussion about this subject.

A related problem. How to detect if two ways forming an elongated graph-cycle perfectly match. In other words, there is no gap between them and they don't overlap. Perhaps, evaluating the factor: the area of all gaps and overlaps divided by the squared perimeter of the graph-cycle.

[vvoovv]

The following cases are possible for the extruded ways forming an elongated graph-cycle:

(1) There is one or more gaps of significant size between the extruded ways. The polygon representing gaps will be filled in during rendering.

(2) The extruded ways match each other. The size of gaps or overlaps is negligible. If the ways represent carriage ways, the addon may create a barrier between the carriage ways. Otherwise a kerb may be generated between between the ways.

(3) There is a significant overlap between the extruded ways. Adjusting way width is not an option as we found it out. Finding a centerline will be required in this case. The rendering is done in the same way as in (2).

[polarkernel]

The following cases are possible for the extruded ways forming an elongated graph-cycle:

I will analyze how to detect these three cases. The publicly described methods for determining the centerline are usually based on shapely and CGAL. Perhaps this can be done simpler for our cases.

[polarkernel]

I will once try to find all intersection between ways and objects and also between two ways in all our datasets using brute force.

Here are some results. However, not for all datasets, brute force sometimes runs over hours. I used the street widths as configured in the file _/way/wayproperties.py. Way-sections always intersect. To compute intersections between ways, I used the trimmed ways after the construction of the intersection areas. I excluded cemetery, railway and commercial from the polyline objects, as they lead to intersections, similar to landuse:grass.

File _berlin_karl_marxallee.osm

Center-strip collisions

The grass in the center strip of Karl-Marx-Allee is intersected everywhere when using the standard width of 2.7 m for one lane (see red areas in the picture). Reducing the lane widths individually for the three way-sections from left to right, until there are no more overlaps, we get lane widths of 2.0 m, 1.8 m and 2.4 m. These correspond to widths of the carriageways of 6.0 m, 5.4 m and 7.2 m for the three lanes of these ways.

Similar collisions appear along the Friedrichstraße.

Footways crossing grass areas

Many footways cross landuse:grass (or similar) without any gap provided for them. This seems to be the case only for footways, but occurs in all our datasets. We will have to find a solution for this:

In our stored dataset, the service-way 830606233 crosses a landuse:village_green area. But in the newest OSM data, this area has been decreased (3 months ago):

Mapping issues

The footway 317769275 collides with a building:

Way-section intersections

There were no intersections between ways.

File _rotterdam01.osm

There were no intersections with buildings and landuse polyline objects.

Way-section intersections: Tram issues

To the North, the areas of tram lanes and cycle-ways intersect. To the West, the two tram lane areas intersect each other. The usual width of a tram lane is 3.5 m. It seems that the cycle-ways share some area of the tram lane.

File _berlin_highways_withoutintersections.osm

Center-strip collisions

Collisions with grass in the center strip around Bundesplatz 695856766:

Mapping issues

Secondary roads and footways collide with roof 374546988 (see image). Similar with roof 374919446. Don't know if we can avoid this in the way-manager.

Way-section intersections

No way collisions, but the two carriage ways of the motorway could be a candidate for case "(2) The extruded ways match each other.".

File _milano01.osm

Intersection of residential way (2m width) Via Sabaudia with multipolygon 428366345:

Several footpaths intersect buildings. As one example, 962951527:

Tram lanes share secondary ways. Intersections everywhere, when standard widths used. No other way intersections.

File _bratislava_oldtown.osm

Intersections with buildings and polylines

Footways intersect with landuse:construction (see image). 195530805 Footway intersects landuse:recreation_ground. 226522012

There is an issue with the building manager for courtyards. They remain to be filled, and then the inner ways intersect with them. This happens several times in this dataset, as an example the footway 621807220:

The tag indoor:yes must exclude ways (see image) Example: 549935575:

Pedestrian ways 759222203 and 4061687 intersect buildings:

Way-section intersections

Intersections between tram lanes and between tram lanes sharing other ways almost everywhere.

Footway 418979382 is very close to residential way 226832825, therefore intersections between these ways:

Mapping issues

Footway 356658442 intersects a building:

[vvoovv]

Intersection of residential way (2m width) Via Sabaudia with multipolygon 428366345:

It's landuse=residential. They aren't used at all the the moment.

[vvoovv]

The tag indoor:yes must exclude ways (see image)

Ways with the tag indoor are now excluded in the branch _streetsintersection.

[vvoovv]

Could you please give some examples of tram ways sharing other ways?

[vvoovv]

Tram lanes share secondary ways. Intersections everywhere, when standard widths used.

Did you mean intersections of tram ways with secondary ways?

[polarkernel]

It's landuse=residential. They aren't used at all the the moment.

I missed the precise object. It was an intersection with 428366346 that is landuse=industrial. I will filter all landuse tags with cemetery, railway, commercial, and industrial in the branch _streetsintersection to avoid such intersections. The first three were already filtered for the above tests.

Ways with the tag indoor are now excluded in the branch streets_intersection.

Thanks.

[polarkernel]

Could you please give some examples of tram ways sharing other ways?

The upper intersections are with the cycleway, but the lower (green arrow) with a section of the residential way 198187949:

Another example, an intersection with two sections of the unclassified way 244491374 (upper ways) and a bicycleway way (lower):

Finally, the intersection with several segments of the residential way 4642669 (left side). On the right, there are intersections with a pedestrian way that becomes a residential one on its bottom. Both sides could maybe also be issues with the intersection area there, I didn't test that:

Did you mean intersections of tram ways with secondary ways?

No, that was a bad expression. I meant other ways than footways or bicyleways.

[vvoovv]

Significant overlap of a way and a tram way means that vehicles are allowed to drive on tram rails, i.e. trams and vehicles share the same area for moving.

[polarkernel]

The following cases are possible for the extruded ways forming an elongated graph-cycle: ... I will analyze how to detect these three cases.

Here are a few results of my investigations so far. As often stated, the real world is more complicated than the theory.

In a first idea, which I discarded in the meantime, I tried to find the more or less parallel long sections of the paths in an elongated graph cycle. I describe it anyway, maybe it will be useful later.

The way-intersections of an elongated graph-cycle are projected onto the long direction of the minimum bounding rectangle, and the outermost endpoints are used to split the cycle (red and blue dot in the image below). Then the first sections on both sides, that are more or less perpendicular to this direction, are removed. For a classical situation (unfortunately quite rare), we get the parallel ways (red and blue) like this:

The method is quite robust, even when the graph-cycle is more complicated:

To determine the cases proposed here, one could now intersect a number of lines perpendicular to the rectangle direction with these lines and measure the distance between them in every position. But I found out that this quickly becomes quite complicated.

To better visualize the practical problems, in the latest commit I implemented a plot that allows to look in detail at each graph-cycle. With this, I would like to sketch further ideas:

The Map shows the cycle using your way patterns, so that one can see the way categories involved. The Ways & Intersection Areas shows the result of way and intersection polygons, constructed with the default parameters. The Line Pair plot shows the result of the construction described above. Finally, the Position plot shows the position of the graph-cycle in the scene. When closing the figure, the next cycle is displayed.

Further ideas are based on the illustration in Ways & Intersection Areas. Let me first summarize some possible steps (all of them are untested!) and then explain some of them in detail:

1. Construct the correct way-intersection areas. At the moment, this is not yet the case for some of them. Additionally, also clusters of intersections will have to be constructed correctly, currently not yet done.
2. Construct the trimmed way-section polygons (the blue areas in the illustration).
3. These should not intersect each other. Test them for intersections and find corrections, when required.
4. Test for intersections of these polygons with objects like grassland or buildings in the cycle and find corrections, when required.
5. Find the polygon of the inner area of the cycle, subtract eventual objects and triangulate it.

At 1.

The main task to do here is to construct intersection-clusters. I assume, many of them can be found just by computing the union of the primary intersection areas, for example here:

At 3.

Testing for polygon intersections can be done quite fast. I would write my own code, as pyGEOS does too many computations. The most difficult part would be to find appropriate corrections. Note that these corrections could also have an influence on neighbor graph-cycles. Some examples:

At 5.

To find the inner area (green in the images below), an algorithm can just follow the inner edges of the combination of trimmed ways and intersection areas. Using an appropriate data structure, this should be feasible.

Note that all these hold only for elongated graph-cycles. In all cases throughout these considerations, also dead-end ways, as depicted in the right image, would be treated correctly. However, it remains complicated. For instance, in the case of islands, holes will appear in the inner area. Maybe, just click through the real graph-cycles using the newest commit and get your own impression of the real situation. Maybe this may trigger new ideas.

[vvoovv]

streets/rotterdam_01.osm, Cycle 4

There is a gap between the extruded ways (a carriage way and a tram way) and then they overlap.

The width of the elongated graph-cycle decreases at the right.

[vvoovv]

To better visualize the practical problems, in the latest commit I implemented a plot that allows to look in detail at each graph-cycle.

Very useful tool, by the way!

[vvoovv]

streets/rotterdam_01.osm, Cycle 8

An odd intersection geometry:

[vvoovv]

streets/rotterdam_01.osm, Cycle 31.

Another weird geometry of an intersection:

[vvoovv]

streets/rotterdam_01.osm, Cycle 79. Weird geometry.