[streets] Sparsely populated areas

[vvoovv]

Sparsely populated areas (rural areas) require a special processing.

In your example on Piirissaar, there are almost no more graph cycles (only the red lines in the image below). In all our data sets, the density of roads was so large that the idea of graph cycles worked well. For such sparsely populated areas however, we will have to come up with something else, I assume.

Another problem is the large graph-cycle painted in red like in the image below. The circumscribed circle around this cycle is very large and includes most of the polyline objects in the scene. Their subtraction therefore takes a lot of processing time in PyGeos. The result is a large polygon with a large number of holes, which again takes a large execution time for the decomposition.

[vvoovv]

An idea. Use a grid subdivision for those cases.

[polarkernel]

The border of the graph-cycle polygons is formed by the enclosing ways, there are no ways inside the cycle. For large graph-cycles, almost all polyline objects are found in the KD-tree, also those far outside the polygon. We use these polygons to finally create the triangles along the ways. But I think there is a distance limit from these ways after which this is no longer important. Only the triangles in proximity of the ways should be used.

For small graph-cycles, the method of the circumscribed circle works fine. What if, above a certain circle radius, we only examine smaller circles in the KD-tree along the edge of the polygon and simply omit the objects in its center?

Do you know an algorithm that delivers equidistant positions along a polyline, which is given by a sequence of vertices, so that these positions could be used as centers of such circles?

[vvoovv]

I can only propose the following simple solution.

All polyline vertices are the centers of those circles and also the points defined as follows.

Suppose D is a desired distance between the centers of two neighbor circles located on the polyline. If the length L of a polyline edge is larger than D than we add additionally the points equally spaced with the distance L / ceil(L/D) on that edge.

[vvoovv]

Another problem is dead-end way-sections. Buildings can be located along those way-sections.

[polarkernel]

What I've suggested so far doesn't really solve the problem. The slow and inaccurate search for objects to be examined is only one part of the problem. Let's assume 50 objects are already integrated as holes in the large polygon. For each additional object to be subtracted, these 50 holes must be examined, which costs an enormous amount of time. We must avoid to have too many objects within a single polygon. But we also need to find all objects in the polygon to avoid issues with dead-end way-sections, as you already mentioned.

Currently, I would prioritize a subdivision of the large polygon into smaller parts, that can then be quickly examined. This was your first proposal. This could be done for instance using a regular grid. A disadvantage could be that additional vertices would be created at the border of the original polygon. Should this lead to issues, we would have to think about some kind of grid that uses the existing vertices of the polygon.

An additional advantage could arise if holes, generated by way-islands, would be connected to the original polygon by these dummy "grid-ways" and no more appear as hole (see cases b) and c) here).

[polarkernel]

Currently, I would prioritize a subdivision of the large polygon into smaller parts, that can then be quickly examined.

I made a first attempt to realize this idea. 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 the parts have the desired size.

The effect is exciting. For the scene _krasnayapolyana.osm (picture above, already mentioned in the first comment), using my laptop, the process of the subtraction of the polyline-objects consumed 90.7 seconds using the previous method. With the new method, only 12.1 seconds are required. For the region marked in red in the image above, the subdivided cycles become visible in the triangulation image:

A disadvantage could be that additional vertices would be created at the border of the original polygon.

The additional vertices created by the splitting are currently not yet integrated into the way-sections. For this problem and several general problems on how way-vertices should be structured and stored, I will open an new issue on this subject once next week.

An additional advantage could arise if holes, generated by way-islands, would be connected to the original polygon by these dummy "grid-ways" and no more appear as hole.

Note that this is not realized. Creating dummy "grid-ways" would require to know large graph-cycles already when the section network gets built. This is not possible because graph-cycles have to be created from the network and are not yet known then.

[vvoovv]

Really encouraging results!

I noticed the building marked on the screenshot below doesn't participate in the triangulation. Also there is a forest (natural=wood) to the right from that building. However the forest is missing in the final output.

[polarkernel]

I noticed the building marked on the screenshot below doesn't participate in the triangulation. Also there is a forest (natural=wood) to the right from that building. However the forest is missing in the final output.

Thanks to report that. There have been some bugs that are fixed now with the last commit.

[vvoovv]

Thanks to report that. There have been some bugs that are fixed now with the last commit.

The building now participates in the triangulation. But there is a wood (natural=wood) to the right from the building. The wood isn't there. What's wrong with it?

[polarkernel]

But there is a wood (natural=wood) to the right from the building. The wood isn't there. What's wrong with it?

manager.polylines does not provide it. It provides only these objects that have a tag natural:

[vvoovv]

Sorry for the confusion. I'll check it out.

[polarkernel]

Sorry for the confusion. I'll check it out.

No sorry required, your checks are very important for me!

[vvoovv]

Sorry for the confusion. I'll check it out.

This forest was mapped as OSM relation. Not sure what to do with relation. A relation can be used to map any combination of

• simple polygons
• polygons with one or more holes

[vvoovv]

This forest was mapped as OSM relation. Not sure what to do with relation.

Created a separate issue #38 to discuss this problem.