Experiments around clustering of intersections

[polarkernel]

Intersections of common streets may be constructed using intersection points of their boundaries. A simple algorithm can be used to construct the polygon area of such intersections Here are some examples:

There are two exceptions, however, where several such intersections must be combined into a larger area, an intersection cluster. These are way bundles and dense intersections groups. A classic example for the former is the intersection of the Straße der Pariser Kommune and the Karl-Marx-Allee in Berlin:

Here, the ends of bundled (parallel) ways intersect and require a larger intersection area than the individual intersections of their lanes. The latter reason may be dense groups of (sometimes overlapping) intersections, as here on Moscow's Leningradski Prospekt:

In earlier experiments, I found that Density-Based Spatial Clustering (DBSCAN) algorithms, which group points that are densely packed together (points with many nearby neighbors), are the best approach to finding such clusters. Some discussions, mainly about categorizing the intersections based on their road types, have already been done in issue #80, starting here

In the following posts, I will take a look at the process of creating intersection areas from these point clusters.

[polarkernel]

Large intersections that need to be clustered from smaller ones are very individual. Intersections are often grouped into types, such as T-, Y-, X-, #-intersections. But in reality, these types are more mental constructs and almost always differ in details from these theoretical types. Therefore, the collection of intersections I have used can only give some basic ideas of what can happen, when trying to find a clustered intersection area.

As a first experiment, I used the intersections of type major and main see here. I used intersections on scene files we already have since some time (stored in the repository osm_extracts). The middle column shows the individual areas that are constructed from the original ways. The right column displays the area of a convex hull around the major and main intersections.

Satellite image of intersection.

Every intersection of OSM-ways has become an intersection area, which depends on the widths of the ways.

Convex hull around the intersections of type "major" (red dot) and "main" (white dot).

Karl-Marx-Allee, Berlin

Middellandstraat - Henegouwerlaan, Rotterdam

Via Giovanni Battista Pergolesi - Via Saverio Mercadante, Milano

Shibuya Crossing, Tokyo

Špitálska - Námestie SNP, Bratislava

[polarkernel]

If you use only the locations of the intersections, as we did in the previous examples, the resulting areas will be quite small. To get more realistic areas, I used the simple intersection areas of the major and main type intersections and created different hulls around them. A convex hull is well known and its code (ConvexHull) was already available in the blosm repository. To make the hull better adapt to the given areas, two types on concave hulls have been coded and applied: ConcaveHull and AlphaShaper. Unlike the convex hull, a concave hull is not unique for a general set of points.

In the class ConcaveHull I implemented the algorithm described by Adriano Moreira and Maribel Yasmina Santos: CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS. GRAPP 2007 - International Conference on Computer Graphics Theory and Applications; pp 61-68. It is a very aggressive algorithm, sometimes reducing parts of the region to a single point.

With the class AlphaShaper I implemented a classic alpha shape algorithm. Its aggressiveness is controlled by a parameter alpha, the larger alpha is, the more aggressively concave parts are cut out. I implemented a solution with an automatically computed alpha, similar to the algorithm proposed by Edelsbrunner, Kirkpatrick & Seidel (1983), which tries to maximize the concave cutouts. This is subject to the following conditions: The hull has no holes, all points to be enveloped must be in the hull polygon and finally, the hull must not have duplicate vertices.

Satellite image

Convex hull

Concave hull

Alpha shape

Karl-Marx-Allee, Berlin

Middellandstraat - Henegouwerlaan, Rotterdam

Via Giovanni Battista Pergolesi - Via Saverio Mercadante, Milano

Shibuya Crossing, Tokyo

Špitálska - Námestie SNP, Bratislava

[vvoovv]

A classic example for the former is the intersection of Andreasstraße and Karl-Marx-Allee in Berlin

Isn't this the intersection of Straße der Pariser Kommune and Karl-Marx-Allee?

[polarkernel]

Isn't this the intersection of Straße der Pariser Kommune and Karl-Marx-Allee?

You are right. I corrected it in the post. Sorry about that.

[vvoovv]

Typically a crosswalk is not part of an intersection as shown on the screenshots above. Crosswalks can be safely omitted for the generation of clustered intersections.

Cycleways can be also omitted for now for the generation of clustered intersections. In general, cycleways are more tricky. There can be a cycle lane right on the roadway as shown on the photo below.

The OSM tagging for the above case is described in the article cycleway=lane. If the tag cycleway=lane or a similar tag is present, the width of the roadway should be enlarged by the width of the cycleway lane(s). Even in this case the clustered intersection is formed by the enlarged roadways only.

Rendering of a cycleway lane on a clustered intersection with a texture is hardly possible. Instead a mesh-based lane marking can be used to render the cycleway lane on the intersection.

Finally, I suggest considering only major ways for the generation of the clustered intersections.