Examples of street polygons for graph-cycles

[vvoovv]

I'd like to consider different graph-cycles and describe how the polygons can be generated for them. That's needed to derive a general algorithm. After the polygons are generated for each graph-cycles, they can by joined. The widths of the resulting roads can be unified.

---

Example 1

The graph-cycle contains a grass polygon. We need to triangulate the sequence of edges:

Now join the triangles for each way-section. The triangles that are to be joined must have a common edge with a way-section:

The blue triangles weren't joined since they didn't have a common edge with a way-segment. However each blue triangle has a common vertex with two adjacent way-segments. We can find the projection of the triangle on those way-segments. The triangle can be attached to the way-segment with a larger triangle projection. That leads to:

Finally, the shape of the pedestrian crossings (green) should be corrected:

[polarkernel]

I'd like to consider different graph-cycles and describe how the polygons can be generated for them.

I like the proposed idea of binding triangles or eventually polygons to the ways. This could perhaps solve the problem to find the correct neigborhood. The algorithm I am currently developing to decompose polygons with holes delivers convex polygons and triangles. Experiments will show whether these polygons can be controlled to be useful. Shouldn't they then it will be quite simple to decompose convex polygons to triangles.

What is your plan to place the final road's texture? Will the ways be subtracted from the polygons proposed here or will they just cover them? I the current experimental version, the road-polygons with their assigned width get subtracted from the graph-cycles even before the polyline features get subtracted. The reason for to do that me was the fact, that in this stage the relation between the way segments and the cycles is still available. One one hand, during subtraction of the polyline objects, the graph-cycles get sometimes split into pieces and on the other hand, the usage of PyGEOS allows only to have lists of vertices as polygons, which makes it quite difficult to keep a relation between the way-segments and the polygon parts.

[vvoovv]

I suggest not to subtract the way polygons from the road polygons.

For the example 1 a check can be made if the width of the road is mostly the same along the way-segment. If the width is the same, then a single road texture can be applied to the road polygon.

The road width is not uniform in the example 1. The road polygon can be further split into a number of parts. The different road textures can be applied to the road parts with different width.

[polarkernel]

A first version of polygon decomposition is committed. The implementation was more difficult than I first thought and consumed much more time. The following problems had to be painfully discovered and solved:

• Like any decomposition algorithm, also this one connects holes using bridges. However, vertices of bridges are not unique and therefore cannot be used as keys. The algorithm had to be refactored to indices of the polygon vertices.
• Segment intersections and the point in polygon check proved to be sensitive to floating point accuracy. For this purpose, finally functions of PyGEOS were used, which apply a more robust computation than the classical algorithms.
• In rare cases, the algorithm builds bridges to holes that cross the polygon. There should be a test and a more robust method available to prevent this. However, the authors of the paper didn't provide that. This solution is currently not yet available.

Even if the last point is not solved yet, in the new version you can already see results for almost all polygons (the polygons that produced faulty bridges are simply omitted). It is difficult to visualize the decomposed parts. I tried to use alternating colors, like this (to see the decomposition better you best run the code and magnify the image):

I am not yet really happy with the result. I didn't find a solution to construct the correct bridges within the algorithm. Perhaps it is easier to first construct these bridges with the already existing algorithm and only then apply part of the new method. The distribution of polygons and triangles looks very random. Maybe we should do a full triangulation after all, perhaps with a different algorithm. But first look yourself.