Open polarkernel opened 2 years ago
I refactored way/way_properties.py. However now I am getting an error. I guess that's because some ways are too broad.
The refactoring is OK. It seems that collisions between ways are the reason. The conflict in _manhattan01.osm arises at an intersection on the top left. Here are the situations with the old widths (left image) and with the new ones (right):
I am sorry, I can't solve such issues in a short time. For the moment, I implemented some code that catches such exceptions, removes the intersection area, but does also not trim the ways there. Then it should not disturb too much your development. This change is committed. Preferably, use self.useFillet = False
, this is less error-prone than with fillets (although it does not help in this special case).
Some progress:
In the current version, conflicting intersections, as for example depicted in the left image below, are merged by a boolean union of their polygons. The result, shown in the right image, is not very pleasant, mainly when fillets are used.
I have an idea on how these cases can be detected, before the intersection areas are computed, and then merged as a cluster of intersections properly. I don't yet know for sure if this will work, the tests will still take some time. However, in cases, where also the ways intersect, as shown above, can't be handled this way. We will need a strategy on how to treat these cases. I think it will never really possible to avoid them all. Maybe the ways should also be merged somehow. What happens in Blender, when two ways created by GNs collide?
A version with some minor bugs fixed has been committed.
Using the current street widths from _wayproperties.py, a lot of overlapping ways at intersections is produced. I can't find any way to resolve these. The logic of intersection construction becomes too much corrupted to even detect these.
Maybe the ways should also be merged somehow.
But those ways should be detected first. What if we use the existing code to detect elongated cycles?
If an elongated cycle is detected, I won't generate sidewalks for the inner sides of the elongated cluster.
Also, can we use the existing code to detect intersection clusters?
Using the current street widths from way_properties.py, a lot of overlapping ways at intersections is produced. I can't find any way to resolve these. The logic of intersection construction becomes too much corrupted to even detect these.
Maybe it's helpful when I show some illustrations. Obviously, ways intersect at intersections, and the area, where this happens, is the intersection polygon we are looking for. The algorithm to find this area sorts the outgoing ways in counter-clockwise order. Beside a lot of exceptions and special cases, it then tries for every way to find the intersection point of its left border with the right border of the consecutive way. This delivers the frame for the intersection area, which is then completed by the connectors. But when there is no such intersection point (or when it is far away), because outgoing ways overlap, then this is no more possible. Here some examples of this issue, created by a test version of mine (the darker blue shows the overlapping part):
What if we use the existing code to detect elongated cycles? If an elongated cycle is detected, I won't generate sidewalks for the inner sides of the elongated cluster.
For some cases, this could help. However, it is not possible to find them, when the ways are not closed to a cycle, or when the cycle is bent too much.
Also, can we use the existing code to detect intersection clusters?
Only partly. The current version detects short ways between intersections and overlapping intersection areas and merges them to clustered areas. Not for larger clusters, I have not pursued the idea of using patterns any further.
For some cases, this could help.
What would be the percentage of the cases with detected elongated cycles?
Only partly.
Also, what would be the percentage of detected intersection clusters?
What would be the percentage of the cases with detected elongated cycles?
Difficult question. It heavily depends on the scene. For instance, in _/streets/rotterdam01.osm, 100% of the elongated cycles are detected correctly, while in _/facade_visibility/moscow_leningradskiprospekt.osm, I would estimate that about 20% are not detected. You can experiment yourself using the version in branch _streetsintersections and set evalType = 'elongatedCycles'
in line 30 in _action/roadintersections.py.
Also, what would be the percentage of detected intersection clusters?
I can't tell a percentage. Good results in _/facade_visibility/berlin_karl_marxallee.osm, none found in _/streets/milano01.osm. Similarly, you may experiment by setting evalType = 'detectPatterns'
in branch _streetsintersections.
I like to propose another idea: Computing elongated cycles is a costly operation. It starts with the extraction of the cycle, continues by the computation of the convex hull, using the caliper method, to finally construct an enclosing rectangle, where then the elongation factor is computed from the side lengths. Once an elongated cycle is found, it is not sure that it produces an issue with conflicting ways.
Why not check for the conflicts directly? After the construction of the borders of two consecutive ways in the counter-clockwise order described above, it should be easy to check if vertices of one of these borders are on the wrong side of the other one. There is only the problem to exclude the vertices very near to the intersection, where they cross due to the intersection, which is wanted.
When such a conflict is detected, the widths of the affected ways are reduced by the widths of the sidewalks at the inner sides, as you proposed. Flags could be used in the class TrimmedWaySection
to signal these to your Blender code. Additionally, another flag could be set if the conflict persists, maybe to involve an editor in Blender (all these flags or similar to be defined by you). This method would require partly a second run, because a reduced way width set at one intersection may require to reprocess the area of the intersection at the other end, if it already has been processed before.
How to process complex intersections like the one below? They borders of the parallel ways can intersect.
Flags could be used in the class
TrimmedWaySection
to signal these to your Blender code.
At the moment I am thinking about a Python list, each element of which corresponds to the related node of an instance of the class TrimmedWaySection
. Each element of the list is a Python tuple with two elements: (Value_Left, Value_Right)
.
Value_Left
or Value_Right
can have one of the following values:
None
if there is now interectionTrimmedWaySection
if there is an intersection with that extruded neighbor way-section.A extruded way-section may intersect more than one neighbor way sections.
The whole problem is ways more complicated. Conflicts may arise in many unexpected situations, and the wider ways that include sidewalks now have only increased the visibility of an already existing problem. Just as a simple example, the intersection at the end of a way-section may appear before the intersection of its left border (red) with the right border of the consecutive way (green):
Currently, I try to group this second intersection (and sometimes more of them, if there are further conflicts) to one cluster, in order to compute the intersection area of this cluster. These can get pretty complicated (the red dots are the intersections):
For such clusters, it will also be possible to check for overlapping ways. I hope that I will be able to implement an algorithm that is capable of creating an intersection area from them. However, some of the overlapping cases won't be possible to be solved omitting the sidewalks:
How to process complex intersections like the one below? They borders of the parallel ways can intersect.
My current idea is to check for the short ways between the four way-intersections. Those intersections, that are connected by these short ways, should be grouped to one cluster, as described above, and one intersection area then created from them. Like this, the test for overlap should similarly be possible. A/B-Street tried to do something similar (except the overlap test), as described here.
My current idea is to check for the short ways between the four way-intersections.
These are Hash-intersections. What about H-intersections?
However, some of the overlapping cases won't be possible to be solved omitting the sidewalks:
I think the overlapping segments should be joined. The addon will generate something meaningful for the joined segments.
Some intermediate report about the current state of the development. During the treatment of clusters, I found some issues in the current implementation, that are partly solved (but not yet committed). Let me explain them using an example:
The out-ways of single intersections can easily be ordered by their angles, as shown in the left diagram above. Expanding the ways to their width between consecutive out-ways is then used to construct the intersection area. But when intersections are clustered, as shown on the right, this order is no more obvious. The current implementation was inspired by the solution of Dustin Carlino, one of the developers of A/B Street. He computed the center of mass of the cluster intersections and derived the angles using the endpoints of the ways relative to this point. However, this solution is not reliable, he showed the problem in one of his pictures:
The two ways to the right start out roughly parallel, but curve and are split on the other end at different distances. The purple lines show the angles to the green intersection's center. The ordering of the two roads is switched if these purple lines are used to calculate the angle. Dustin ended finally in manually editing the result.
In the meantime, I found a robust solution that resolves this issue. All ways of the cluster are inserted into a graph network. From this network, the outermost cycle is computed, as shown in red in the left image below. Then, inner bends can be identified between the endpoints of the ways. Two examples of them are shown in the right image. I called them bulges.
These bulges are always computed correctly, and the same method can be applied to single intersections as well as to clusters. Expanding the ways to their widths within these bulges is used to find the area of the intersection, similar to the single intersections process (but what I have not yet implemented until now). Here is an example with seven clustered intersections from the scene in _/facadevisibility/mckinney.osm, from left to right: intersection nodes and their out-ways, identification of bulges, expanded ways:
What is not yet solved at all is the question of conflict detection to build the clusters and the solution to conflicting ways. First, I like to solve the detection of clusters, and there I don't mean Hash- or H-type clusters for example, but clusters required due to geometric conflicts (overlap of intersection areas, short ways completely within other ways, overlapping ways, ...). Also joining of overlapping ways, as you proposed, has to be solved. Mainly, when they don't end at the same intersection, as depicted below.
However, this solution is not reliable, he showed the problem in one of his pictures: The two ways to the right start out roughly parallel, but curve and are split on the other end at different distances.
Aren't only short way-segments considered?
From this network, the outermost cycle is computed, as shown in red in the left image below.
I can't see any cycles in your image. Could you please explain what is meant here.
What would be the area of the intersection in the example above?
Aren't only short way-segments considered?
When Dustin speaks of short ways, he means the short segments in the green area in his image. However, whatever is used, the end of the first segment or the end of the way section, the method is not robust. In the example below, the red dot is the center of mass of the three intersections. Sorting the endpoints by consecutive angles seen from this center results in the order depicted by the numbers, which is wrong:
From this network, the outermost cycle is computed, as shown in red in the left image below. I can't see any cycles in your image. Could you please explain what is meant here.
The term cycle used here comes from graph theory. A cycle in an undirected graph is a path through the nodes, where no edge is used twice and that ends at the node where it started. Undirected means that the edges between the nodes consist of so called half-edges, one in each direction, for example
For the proposed algorithm, the path starts at a node of order one (that means that it has only one out-way), for instance node 5. The outermost cycle is then the path 5 - 4 - 2 - 1 - 2 - 3 - 2 - 4 - 6 - 4 - 5. It always selects the rightmost half-edge to result in a counter-clockwise cycle. This corresponds to the red line in my image mentioned (it is difficult to visualize a cycle that has no hole). An example for a bulge is 3 - 2 - 4 - 6, because the nodes 3 and 6 are of order one.
What would be the area of the intersection in the example above?
I selected a bad example. Let me explain using another one:
1) 2) 3)
4) 5)
1) A cluster with two intersections (example of H-type). 2) Ways expanded into bulges (each same color). 3) Find intersections of way-section borders in the bulges. 4) Project these on centerline of way and use the outermost one to construct the connectors. 5) Resulting intersection area.
The example that you couldn't understand has internal conflicts, as shown in the magnified view below. The detection of intersections that need to be clustered to avoid geometrical conflicts and the detection of overlaps (red arrow) is part of my current development.
That idea with bulges look very promising.
I have problems using OSM-tags to find the position of the centerline of ways relative to the lanes. The current (very simple) implementation was based on observations in _/facade_visibility/berlin_karl_marxallee.osm. For instance, this way segment is tagged as:
lanes=4
oneway=yes
turn:lanes=left|through|none|none
While the centerline remains in the middle of the three main lanes, a turn lane is added at the left, which seemed logical to me. But there are many cases, where this logic does not hold. For instance, this section from _/facade_visibility/bratislava_oldtown.osm is tagged as
lanes=2
oneway=yes
turn:lanes=through|through;right
but here, the centerline remains in the middle of the two lanes. The same holds for this segment (same scene), tagged as
lanes=2
oneway=yes
turn:lanes=slight_left|slight_left
There are also ways, where the number of lanes does not correspond with the number of options in turn:lanes
, for instance, for this way in _/facade_visibility/moscow_leningradskiprospekt.osm, tagged as
lanes=3
oneway=yes
turn:lanes=left;through|through|through|right
When the centerline is not correctly positioned, overlapping ways may result, as I observe currently in different of our scenes. However, generally, OSM seems not to provide such information, at least I was not able to find related knowledge from the net.
I suggest to make it as simple as possible for the first iteration of the code.
turn:lanes
is ignored since only 0.37% of highways have it (proof). And it isn't reliable.lanes
(if available) is always used to estimate the width of a carriageway.I suggest to make it as simple as possible for the first iteration of the code.
I agree. However, for instance in the file _bratislava_oldtown.osm I found 1.98% of highways with this tag. This was also the file that made most of these issues observed.
I had an idea that could work, as far as I already tested it. When the start of the section is of order 2, that means there was only a change in width or category, and when the direction values in the tag turn:lanes
are asymmetric, then an offset is used so that the centerline stays where it should, else the centerline is located always in the middle of the carriageway. If this works for all of our test scenes, then I will implement it, else I will follow your proposition.
If this works for all of our test scenes, then I will implement it, else I will follow your proposition.
I chose something in the middle. I have found and implemented a working solution. But it is currently turned off so that all centerlines run in the middle of the carriageway. Once we get to the point where we like to use turn lanes, I can switch them on in five minutes. This solution is committed.
There area remaining problems with the generation of streets with sidewalk. One of them is related to T-crossings.
I need 3 points (shown on the image above) to fill the area to the right from the crossing. The addon will create a curve out those 3 points and apply a profile to the curve to fill the area to the right from the crossing.
I need 3 points (shown on the image above) to fill the area to the right from the crossing.
OK. For such intersections, the borders on the right of the two ways up and down in your image do poorly or not intersect. The red line is therefore always constructed as a straight line between the upper and lower connectors. Shall the third point be just the center of the outer points? Could you please make a proposition on how these 3 points shall be integrated into the class IntersectionArea
.
I need 3 points (shown on the image above) to fill the area to the right from the crossing.
Shouldn't we try to generalize the problem? For some intersections, like a few shown below, similar difficulties will occur, or am I wrong?
I thought that three points were need for a crossing like the one below:
But I agree with you that the problem must be generalized. The problem of the T-crossing occurs every time when two neighboring expanded carriageways intersect in the infinity or very far away.
A related problem is overlapping sidewalks as on the image above.
I don't know if I have misunderstood something. The widths of the sidewalks have already been taken into account during the construction of the intersection areas (_wayproperties.py, doubleRoadsideWidth
). The connectors of the intersection areas include this width. Are you adding broader sidewalks now?
Sorry for the misunderstanding. I marked the roadsides of a carriageway on the image below:
Sidewalks aren't included in the width calculation.
A high level goal is to fill the space between carriageways, buildings and other objects.
We tried to solve it using the triangulation.
A simple approach is partially fill the space along the carriageways with sidewalks. The width of a sidewalk is set through the GUI manually. This week I will experiment with Geometry-Nodes-setups that control the sidewalks.
A mixture of approaches that fill the area automatically and manually through the GUI is highly desired.
We tried to solve it using the triangulation.
I think this approach is not dead. However, to find the space between carriageways, buildings and other objects, we need to have the shapes of ways and intersections with reasonable precision. That's what I am currently working on.
That's what I am currently working on.
Really looking forward to it!
Really looking forward to it!
Although a lot of work has already been invested, I am not making any progress with the detection and resolution of conflicts. The idea with the bulges is good and works excellent for normal cases. After detection of conflicts and many special cases, which I will not go into here yet, many clusters are resolved correctly. Here are two examples:
The point of no further progress, which drives me to despair, are ways that overlap, like these:
You can easily reproduce numerous of these cases when you process the scene _/facade_visibility/bratislava_oldtown.osm with the current version, using the command line arguments --highways --generateStreets
. I used this file for practicing, as it includes almost all cases of conflicts (194 of 1347 intersection nodes produce conflicts). It is impossible to detect overlapping ways within the framework of bulges, I am sure of that.
Currently, I am searching for ways to detect these cases before the construction of intersection areas, but I can't find any practical method. Let me illustrate two cases of overlapping:
There are two main questions to solve: How to detect these cases and how to resolve the problem?
For the left case, for detection, one could create the way polygons, use an R-tree to find polygons in proximity in O[n*log(n)] and check, whether they intersect (to check only is a fast implemented). But what about the right case? There will always be an intersection (there are several such cases in the scene mentioned above).
Once detected, it remains to resolve the issues. Merging the overlapping parts would require to introduce new intersection nodes in the way-network (difficult and delicate). Otherwise, the widths of the overlapping ways could be reduced proportionally, until they do no more intersect. Possible for the left case, but for the right one?
It makes me want to run away, at this point I just can't get any further. Any idea is welcome.
Where are the ends of a bulge located? Can the case on the right be a special case of a bulge?
Where are the ends of a bulge located?
I found it best when the outgoing ways of an intersection or intersection cluster are pre-trimmed after 30 m. When the ways within a bulge overlap, as for the green bulge below, their nearby intersections are marked as part of a cluster with the current intersection.
Can the case on the right be a special case of a bulge?
No. The image is only symbolic. The length of the overlapping part may sometimes be 1 km or more. In this case, the ends would be cut after 30 m, as described above, but their ends not marked as part of a cluster, because they are too far away. But this does not solve the problem described in my last post.
The option --railways
can now be used to add tram tracks and other railway tracks.
The option --railways can now be used to add tram tracks and other railway tracks.
Worsens the problem again more:
It makes me want to run away, ...
…………………ᘛ⁐̤ᕐᐷ
A raw idea.
I suggest analyzing if the way-segments are parallel, i.e. they build a way-cluster. Or more generally, detecting some patterns in a pair of way-sections.
In the first iteration only carriageways, tram tracks and railways are considered, i.e. footways and cycleways are ignored.
Way-junctions are calculated (using bulges where required).
Next, pairs of way-sections are considered that share the same pair of way-junctions. We start by tracing a pair of way sections.
Part (1): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments Part (2): an increase of the width of the way-cluster: a connector object is created Part (3): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments
Later way-clusters may be joined and/or split if there other parallel way-segments. Then footways and cycleways may be added to the way-clusters.
The render will get three objects: WayCluster, Connector, WayCluster for the example above. It's the task of the renderer to decide how to render them. For example, the render may decide to render a parking lane for the first instance of WayCluster.
Using a bottom-up procedure, starting with micro-conflicts to construct an intersection cluster, cannot work. This is the lesson I learned from the last experiments. Using bulges was a good idea, but it does not provide a solution for this task. It always ends with more conflicts and special cases.
Your suggestion could lead us closer to a top-down approach, where we can possibly construct larger crossing areas directly starting with the proposed way-clusters. I will try to follow this idea.
A main problem at the beginning is the detection of parallel way-sections. I have an idea on how to approach this without the "elongated cycles". I will start with that and see, what can be achieved.
I do not fully understand your suggestion.
Part (2): an increase of the width of the way-cluster: a connector object is created
Could you explain that more in detail? I don't understand what you mean.
Part (1): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments Part (3): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments
What is the difference between these steps?
Part (2): an increase of the width of the way-cluster: a connector object is created
Could you explain that more in detail? I don't understand what you mean.
There area 3 parts in the street in my example. The distance between the lower and the upper way-sections is changed in the middle part with the number 2. The code should identify that pattern, that the distance between the parallel way-sections has changed.
Part (1): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments Part (3): way-segments are parallel: a way-cluster is created with the centerline of the parallel way-segments
What is the difference between these steps?
They aren't steps. I referred to the parts in the street in my example. The way-segments in the parts (1) and (3) are parallel. But the distance between the parallel way-segments in the part (3) is larger than in the part(1).
Please let me know if more explanations are needed.
Please let me know if more explanations are needed. Way-junctions are calculated (using bulges where required).
Now your idea clearer to me, thanks. I see two issues. First, I can't calculate way-junctions, as long as there are overlaps, that is already the current problem. Second, there are often no natural points, where the parts, that you propose, can be divided.
My understanding was completely different. Let me explain it using a detail on top of the scene in _/facade_visibility/bratislava_oldtown.osm. It is only meant to be symbolic, I have not looked at the categories of each path. Let's assume that there are overlapping oneway roads and some railway lines (tram) in the wide parts of the image at top. My idea is now to simplify these to single ways, being clusters of all these ways. Then the network becomes much simpler, as depicted in the middle image. When the width of these cluster ways is large, the intersection areas can be computed simply, as we did until now (maybe even bulges are not required). The result is shown at the bottom image.
These intersection areas would look much more realistic than the tinkering with small combined intersections. The cluster ways itself should then keep the information about the order (from left to right, for instance) and the categories of the original ways. I am sure that reality will not be that simple, but it would be another approach. Maybe we can merge somehow our ideas.
I would hope that it would be possible to create a renderer that could do something meaningful out of this information in the clusters. Could you agree with such a solution?
Let's assume that there are overlapping oneway roads and some railway lines (tram) in the wide parts of the image at top. My idea is now to simplify these to single ways, being clusters of all these ways.
What if they don't overlap but constitute a way-cluster? How can a way-cluster be generated then? Perhaps make several iterations increasing the width each time?
What if they don't overlap but constitute a way-cluster? How can a way-cluster be generated then? Perhaps make several iterations increasing the width each time?
My idea is not very mature yet, but it's true, I actually propose to make another attempt at constructing way-clusters. The main problem was the detection of parallel ways. You remember, we tried this with the help of elongated cycles. These had three drawbacks. First, it didn't work for open parallel ways, because they didn't form a cycle, second it was not able to detect short parallel ways, because the enclosing rectangle was not elongated, and third, curved parallel ways also did not produce elongated enclosing rectangles.
I now have a new idea how to detect parallel ways. In the image below, we are looking for parallel neighbors of the red ways. These are expanded so that the green polygons are created. Nearby ways are clipped with this polygon. If the remaining part of the way to be tested for parallelism, inside the polygon, is long compared to the red way (70%-80%?), it is considered as parallel (left) and otherwise not (right).
If it works, all the drawbacks mentioned above would be solved, it would work even for curved ways:
I have no idea what will happen at large intersections, whether it will be possible to elongate the way-clusters and merge them to a large intersection area, as you already proposed with the elongated cycles. Also, there will maybe arise a problem with special ways like tram ways. They would end at these areas. Additionally, the cases already mentioned above will need a special treatment, maybe by the construction of an additional intersection at the point, they leave the cluster:
It would be a new big adventure. I don't know if we should dare to do this.
It would be a new big adventure. I don't know if we should dare to do this.
The problem of generating way-clusters isn't solve yet. Overlapping parallel carriageways would look odd in Blender. It's important to solve this problem.
I think it's worth trying the new approach.
Eventually a combination of methods can be used.
I think it's worth trying the new approach.
OK, then I will first try to implement the new method for parallel way detection and see, how the result looks like. Then we see further.
I found an issue in the way manager. The way 240726810 in _/facade_visibility/bratislava_oldtown.osm has both, highway
and railway
tags:
highway=service
...
railway=tram
It is only delivered as category = 'highway'
by the way manager, so that a part of the tram rails is missing. That is a complete overlap now, and it is a question of how we want to handle that. Possibly a new category?
It is only delivered as
category = 'highway'
by the way manager, so that a part of the tram rails is missing. That is a complete overlap now, and it is a question of how we want to handle that. Possibly a new category?
I suggest for now to treat as an ordinary way with the attribute self.railway = True
. The object Way
would need an additional attribute self.railway
which is equal to False
by default.
I suggest for now to treat as an ordinary way with the attribute
self.railway = True
. The objectWay
would need an additional attributeself.railway
which is equal toFalse
by default.
OK. We will have to find a way on how it should then be integrated into a cluster. But we may discuss this later, when we define the interface for clusters.
If you are in the process of making changes to the way manager: I observed another strange issue. In order to get an overview of the situation, when only carriageways, tram tracks and railways are considered, and footways and cycleways are ignored, I commented out all way categories to be ignored from roadwayIntersectionCategories in /defs/way.py. But then the program crashes at line 38 in \way\manager.py with KeyError: 'other'
.
It seems that one way produces a category 'other'
that does not exist as key in self.layer
. Oddly enough, this does not happen when no categories are commented out.
The results from the construction of trimmed way-sections and intersection polygons have to be adapted for the use with objects based on geometry nodes. Let's discuss here the details of this task.