[streets] Detection of large polyline objects

[polarkernel]

Object polygons may be larger than the graph-cycle they have to be subtracted from and then fail to be detected. The image below shows such a situation

The detection works as follows: The blue line is the graph-cycle polygon and the red dots are the vertices of the object polygon (green area). The vertices of the object polygon are inserted into a KD-tree and also in a dictionary, that matches the vertices to the polygon. The blue area is a circle, circumscribed to the graph-cycle polygon. All vertices of the object polygon within this circle are detected, their object identified by the dictionary and then this object is subtracted from the graph-cycle. But when the object polygon is too large, as in the depicted example, it is not detected and therefore not subtracted.

We have to find a method to make sure that all object polygons that intersect or cover the graph-cycle are detected.

[polarkernel]

A possible solution: For every large object polygon (size to be determined experimentally), add a grid of vertices, for instance within its bounding box, to the KD-tree and to the dictionary. When one of these vertices is within the circumscribed circle of the graph-cycle, it gets detected and the object polygon is matched using the dictionary. The mesh width of the grid is also to be defined experimentally.

[vvoovv]

If an object polygon is entirely within a graph-cycle, it must be detected.

But what if we divide the large object polygon into parts by the way-section that crosses it?

[polarkernel]

If an object polygon is entirely within a graph-cycle, it must be detected.

This is already always the case, as then the vertices of the object polygon are in the circumscribed circle.

But what if we divide the large object polygon into parts by the way-section that crosses it?

I think this would be ways more complicated. We would have to find the ways that cross the object polygon and construct all the subpolygons. Look for instance at an extreme example, the landuse=cemetery region in the north-east of the scene of _berlin_karl_marxallee.osm (dark green region). Adding a few vertices to the KD-tree for this region would be easily detected within their circumscribed circle for all the graph-cycles in this region. Even finding all the ways within the object-polygon would cost more, I think.

!

[vvoovv]

I think this would be ways more complicated.

Ok.

[polarkernel]

I introduced the solution using detection vertices, as described above, in the last commit. Large polyline objects get additional detection vertices inserted in the KD-tree, so that they get detected even when the object surrounds the graph-cycle on a large scale. The size of "large objects" and the mesh width of the grid are parameters in the new definition file _/defs/roadpolygons.py. As an example, here the landuse=cemetery region in the north-east of the scene of _berlin_karl_marxallee.osm, mentioned in my last comment:

The additional effort for generating these vertices and for creating the larger KD-tree seems to be almost compensated by fewer tests for the graph cycles that are hidden by these large objects. Below the result for _berlin_karl_marxallee.osm, left without and right with this feature.

[vvoovv]

What about graph cycles within the cemetery? Are they skipped?

[polarkernel]

What about graph cycles within the cemetery? Are they skipped?

The polyline object "cemetery" is subtracted from these cycles and from then on, they are empty and excluded fron the triangulation.

[vvoovv]

Those ways inside objects should be treated somehow later.

[polarkernel]

During process time measurements I found that it takes far too long to determine these detection vertices. Since the polygon is already a pyGEOS polygon I used its method polygon.inside(p). For a vertex grid inside its bounding box, a point-in-polygon test must be used to determine which vertices are inside the polygon. After replacing the pyGEOS method by the classical method (ray-casting: a point is in a polygon if a line from the point to infinity crosses the polygon an odd number of times) this task runs much faster. For interest I also tried a method using Cauchy's theorem, because it looked so nice and simple. But it takes longer than the classical method. This fix is updated in the latest commit. As an example, here are the measured times for processing all large polygon objects in the file _krasnayapolyana.osm:

pyGEOS:      32.34 sec
ray-casting:  0.47 sec
Cauchy:       1.86 sec

[vvoovv]

Since the polygon is already a pyGEOS polygon I used its method polygon.inside(p).

I wonder which method is used by polygon.inside(p) that is so slow.

[polarkernel]

I wonder which method is used by polygon.inside(p) that is so slow.

pyGEOS does first a bounding-box check. Then, the complete DE-9IM Intersection Model is computed. Finally, the resulting pattern is compared to the pattern that corresponds to point in polygon. The implementation is ways to general for this application. Once we have finished the complete process of triangulation and relating the triangles to the ways, we will need a longer optimizing phase to see, which operations can be simplified, as I did it for the described task.