Bundles, descriptions and issues

[polarkernel]

The first task in the search for objects of the class Bundle is the search for equidistant path segments. For a better understanding of the concept and its problems, I will first explain how the algorithm works.

First, all way-sections that exceed a minimal length and are not too curved are entered into a static spatial index. This index uses bounding boxes around the sections to find neighbor sections. Way-sections, whose bounding boxes overlap, are candidates as neighbors. For every section (template) in this index, its neighbors are searched and tested, whether they are equidistant to the template section. This is done as follows:

The black line is the centerline of the template section. A buffering polygon is constructed around this line, spaced according to the category of the section (red dotted polygon). Assume that the cyan line is the centerline of the neighbor candidate. A clipping algorithm first determines the length inLineLength of the candidate within the buffer polygon. In this example, this is the length between p1 and p2. This length must at least be 10 % of the total length of the candidate.

However, a short candidate line could be perpendicular to the template, but almost completely within the buffer polygon. So we need an additional condition: The distances d1 and d2 between the entry and exit points p1 and p2 and the template are computed. Then, some kind of slope relative to the template is determined from the difference between these distances and the length inLineLength of the candidate within the buffer polygon to as slope = abs(d1-d2)/inLineLength. Demanding a small value for slope rules such cases out.

This algorithm has the advantage, that overlapping way-sections continue the equidistant parts, as long as only one side is interrupted. For instance these three way-sections (black lines with red dotted surrounding buffer polygon) would be considered to belong to the same group (Bundle):

However, there is a disadvantage, when the intersections are almost perpendicular, so that this effect does not work anymore. In the image below on the left (middle part in _rotterdam01.osm) this effect is clearly visible. Overlapping sections result in parallel ways through the intersection (all the same color). In the image on the right (intersection between Karl-Marx-Allee and Straße der Pariser Kommune in _berlin_karl_marxallee.osm), the ways are almost perpendicular, and the groups always contain only the short parallel parts (same color is same group).

[vvoovv]

I renamed totalNumLanes to totalLanes and totalNumLanesOneway to totalLanesOneway in the PML file for brevity and consistence with the naming in the code.

[polarkernel]

Once a Street will be populated with items, I will finish assigning the style for all street items in the method Street.setStyle(..) of the module way.item.street.

Street is now integrated into StreetGenerator for the current state (it contains only one instance of Section). getStyle() is called for all such streets. The code is committed.

[polarkernel]

I created a version with debug output extracted to a file debug.py and conditionally disabled, using self.app.type, as described here. StreetGenerator now also runs in Blender if needed.

[vvoovv]

I removed the temporary code.

Why do some instances of the Street class have the end attribute equal to None?

[polarkernel]

Why do some instances of the Street class have the end attribute equal to None?

Was a bug, fixed now.

[vvoovv]

How can I access instances of the Street class in the WayManager to render the streets in Blender?

[polarkernel]

How can I access instances of the Street class in the WayManager to render the streets in Blender?

We didn't finally define this container after this post. For now, I have defined the instance waymap of the class WayMap in the WayManager class. Currently, all edges in waymap are instances of Street, but later, they may also be instances of Bundle. You may iterate through all edges of the way-map using

for src, dst, key, street in manager.waymap.iterSections():
    ...

src and dst are the ends (mathutils.Vector) of the street. key is usually 0, but is increased when multiple streets have the same end points. street is an instance of the class Street. When once Street and Bundle both will be mixed in waymap, you may select all streets by

for src, dst, key, street in manager.waymap.iterSections(Street):
    ...

If you know the endpoints src and dst of the street, you may access all edges in waymap using

for edge in manager.waymap.getSections(src, dst):
    ...

or, when you know the key of the edge

edge = manager.waymap.getSectionObject(src, dst, key)

But the last two methods of WayMap do not distinguish the type of the edge (may be Street or Bundle).

[vvoovv]

But a Bundle itself is a part of a Street as described in the original message.

[polarkernel]

But a Bundle itself is a part of a Street as described in the original message.

You are right, I missed that. For now, it is not a problem, because there are only instances of Street in waymap that contain one single Section.

Looking back at these definitions, I still have trouble understanding (and accepting) them. In my opinion, these structures do not correctly reflect the topology of the road network. They make the solution much more complicated than needed. Let me take the example of a Street implementation above:

The Street object is a collection of linear objects (Section, SymLane) that are connected as a doubly linked list. Each of these objects has two ends connected to the neighboring objects.. The Street object itself also has two ends, connected to intersections, which are the natural limits of a Street. The Intersection objects are different. They are not linear, they have multiple connections, and they have an area.

The example from the message violates this characteristic:

The SplitMerge (SM) object has three connectors and is more like an intersection than a section. Possibly even an area is required to represent it. The Bundle has two ends at the right (and could have multiple ends in general case). Topologically, they connect to different connectors of the intersection. It is the Bundle with its details, that connects to the intersection, and not the Street. Topologically, this construct is a graph, with a node SM in addition to the intersections.

I have even more trouble with the example, that we already discussed earlier:

The introduction of a PartialIntersection does not help. To represent this construction, Street needs an additional attribute besides start and end. It is a subgraph of the street network and not a linear structure.

These considerations led me to choose a graph as the basic structure in StreetGenerator. For now, we can keep the described interface to access the Street objects. However, maybe I may have to adapt it later.

[vvoovv]

There are issues to solve if a graph is accepted as the basic structure in StreetGenerator.

Is Crosswalk a node or an edge of the graph?

Is PtStop a node or an edge of the graph?

What is the relation between a Bundle and the nodes and the edges of the graph? Grouping into Bundles is also needed to generate separators (grass, etc) between the roadways that form a Bundle.

[polarkernel]

Is Crosswalk a node or an edge of the graph? Is PtStop a node or an edge of the graph?

What are they in the doubly linked list of a Street?

What is the relation between a Bundle and the nodes and the edges of the graph?

In the old solution, Bundles have been LongClusterWays, linear structures that ended at a (complicated) Intersection. The issue of PartialIntersections had been solved by splitting a LongClusterWay into SubClusters using a SplitDescriptor. So something like SubCluster could have been an edge of the graph and SplitDescriptor and Intersection been nodes.

However, I would like to change the procedure at this point. I have been trying to find solutions for this for years now, but have always failed. Either the problem is too complicated for me or I'm too stupid. I now feel tired and don't want any more to carry on working like this.

You seem to have an idea of how you would solve it. Also, you are looking at the problem from a different viewpoint than I am, from a rendering perspective. This can lead to new ideas and solutions. I suggest you tell me how you would like to have what structures, step by step, and I will adapt. If necessary, I will replace the graph (waymap) with something else (currently it could be just a dictionary).

Can you cope with that?

[vvoovv]

I'd like to have the structure presented in the original message. This structure would allow creating the separator areas by connecting the internal borders of the items and forming the polygons made of those internal border chunks.

Green numbers (1) and (2) on the image below represent the separator areas.

Those internal border chunks are shown with the green color of two shades on the image below:

Finally, I think a separate PartialIntersection class is not needed. The single class Intersection would be enough.

[polarkernel]

I'd like to have the structure presented in the original message.

OK, let me describe that in my own words so far, so that you can check, whether I understand it.

What I see are base objects (Section, PtStop, Intersection, SplitMerge, Crosswalk).

• A Section is an elongated object, that has a centerline and two connectors, one at each end. Its attributes are already well-defined in the corresponding class of the current code.
• A PtStop could be something similar to a Section, but with additional attributes. I suggest leaving its definition open until we start implementing it. See also #76.
• An Intersection is a polygonal object, that has two or more connectors.
• A SplitMerge looks like an Intersection to me. It has three connectors. Maybe it has a direction. Again, I suggest leaving its definition open until we start implementing it.
• A Crosswalk will require a special structure. Some ideas are already discussed in #73.

We need to discuss how these objects are connected and how they are passed from StreetGenerator to WayManager.

Green numbers (1) and (2) on the image below represent the separator areas.

These separators will only be valid between parallel way-sections, not when the road runs around a city block. The concept of a Bundle will be required for this, but like Street, this is no longer a base object.

[vvoovv]

OK, let me describe that in my own words so far, so that you can check, whether I understand it.

Yes, everything is correct with some minor notes.

What I see are base objects (Section, PtStop, Intersection, SplitMerge, Crosswalk).

I think the objects TransitionSymLane and TransitionSideLane are also the base ones.

TransitionSymLane is like an Intersection, but it has only two connectors. A Street can't end at a TransitionSymLane.

Also a Street can't end at a SplitMerge.

TransitionSideLane is like an Intersection with zero area, but it has only two connectors. A Street can't end at a TransitionSideLane

• An Intersection is a polygonal object, that has two or more connectors.

Doesn't it have three or more connectors?

[polarkernel]

Yes, everything is correct with some minor notes.

Thanks for the additions, they complete the set of base objects.

• An Intersection is a polygonal object, that has two or more connectors.

Doesn't it have three or more connectors?

Maybe, there is a special case at corners. I will post it as a new issue today.

[polarkernel]

Maybe, there is a special case at corners. I will post it as a new issue today.

Done in #84.

[vvoovv]

Another reason of having Bundles is the generation of sidewalks.

Without a Bundle the sidewalks are generated along both sides of a Section or another item.

If a Bundle is present, the sidewalks are generated along both sides of the Bundle (or the top Bundle if there is a hierarchy of Bundles), rather than the sides of each member of the Bundle.

[vvoovv]

for src, dst, key, street in manager.waymap.iterSections():
    ...

I started a rewrite of the street renderer. For now I managed to render instances of the class Section using the above method.

Let's discuss what data can be delivered to the renderer in the next step of the development.

[polarkernel]

Let's discuss what data can be delivered to the renderer in the next step of the development.

I see three different approaches:

• Implement first items within a Street: SideLane and SymLane. This would be interesting, because we could discuss and find out how to extend the doubly linked list in a Street.
• Implement PtStop. Requires detecting them, finding a way to hold them in a Street, and finally rendering them. This would be a very demanding task, but is a fairly open point of the structures.
• After the edges, implement the nodes in the waymap: Intersections. Could be based on the old implementation, using their connectors and the trimming of the way-sections. Nothing really new, but would "beautify" the rendered result. No clustered intersections for now.

[vvoovv]

I'd prefer to start from the intersections.

What are the obstacles now to get clustered intersections?

[polarkernel]

What are the obstacles now to get clustered intersections?

Clustered intersections require not only the definition and construction of clusters, but also those of bundles. This will be a huge and demanding development step. See also the discussion starting here. To get illustrations, you can run the code in script mode, using --highways --generateStreets.

[polarkernel]

I'd prefer to start from the intersections.

In the old implementation, the neighbors of intersections were way-sections. Their boundaries were intersected, as shown below, and these intersection points (red dots) were connected to a polygon (red) that was completed so that the connectors were perpendicular. The way-sections were then trimmed along their centerlines so that the connectors fit the intersection.

With the new structures, the neighbors of an instance of Intersection are instances of Street, connected to their start or end. Also, an intersection cluster at the tails of Bundles will be an instance of Intersection, and similar rules apply. Therefore, instances of Street and of Bundle must end in an instance of Section, otherwise, this algorithm can't be applied. We will need a solution for Crosswalks.

[vvoovv]

Therefore, instances of Street and of Bundle must end in an instance of Section, otherwise, this algorithm can't be applied. We will need a solution for Crosswalks.

What if Crosswalks, PtStops and other similar items are inserted into a Street after the algorithm finished its job? In this manner the algorithm will deal with Sections only, as the neighbors of Intersections.

[polarkernel]

What if Crosswalks, PtStops and other similar items are inserted into a Street after the algorithm finished its job? In this manner the algorithm will deal with Sections only, as the neighbors of Intersections.

This is a viable option. The only condition is, that the perpendicular connector line of the intersection still fits to whatever has been inserted.

Another point is the connection between Intersection and Street. I think, my first idea will not work:

The Intersection's connector should reference the instance of Street and, additionally, an information on which end of this instance. Instead of pred and succ of the Sections, new attributes pred and succ of the instance of Street should reference the instance of the Intersection, and additionally, their connector. When Crosswalks, PtStops and other similar items are inserted into a Street, only the attributes start and end have to be adapted, while the instance of Intersection remains unchanged.

[vvoovv]

I think, my first idea will not work

Then s1.pred = s2.succ = None to indicate that s1 and s2 are the first and the last items in the Street?

[polarkernel]

Then s1.pred = s2.succ = None to indicate that s1 and s2 are the first and the last items in the Street?

Yes. I also propose to rename start and end to head and tail, as it is usually done for doubly linked lists. succ and pred of Street would then reference the Intersection before and after the Street.

Next issue: How can one find the connector to an Intersection, when the street is given, and how can one reference the street that belongs to a connector, when the intersection is given? I would like to keep the idea to use direct references to objects and not to use any index or similar. Let me illustrate that using the image below.

Given the intersection is1, one of its connectors, for instance c2, could contain a tuple c2=(st1, i), where st1 is the reference to the street st1 and i the index of a point on the connector line of the intersection's polygon, as we had it already before. Similarly, the sign of i could indicate the start or the end of st1.

The inverse direction is more complicated. The reference pred of st1 lets us find the instance is1 of the intersection. But how can we find the corresponding connector c2? One could implement connectors as a Python list and add the index 2 to pred of st1. But the net may be modified, streets be removed or be combined to bundles, so that this index must be considered as mutable.

I had an idea, that may look strange in the first moment. I am also not really sure that it would work under all circumstances. It is possible to use an object as key of a dictionary in Python, given it has a __hash__() and a __eq__() method. These could be implemented for our objects, using for instance hash(location) for intersections or hash( (src,dst,key) ) for elongated objects. Using this feature, connectors would be implemented as a dictionary, using connectors[st1]=i to reference st1, while i=st1.pred.connectors[st1] would reference the connector to st1.

Do you have any ideas? Or do you maybe have less or additional requirements, seen from the viewpoint of the renderer?

[vvoovv]

Yes. I also propose to rename start and end to head and tail, as it is usually done for doubly linked lists.

Ok.

Next issue: How can one find the connector to an Intersection, when the street is given, and how can one reference the street that belongs to a connector, when the intersection is given?

Another possible solution is to use a separate class for the connectors and to get rid of the connector indices all together.

class IntConnector:

    def __init__(self, intersection):

        # the intersection, to which the connector belongs to
        self.intersection = intersection

        # the item, to which the connector is connected to
        self.item = None

        # the preceding connector in the intersection (for, example, when considered counterclockwise)
        self.pred = None

        # the succeeding connector in the intersection (for, example, when considered counterclockwise)
        self.succ = None

street.tail and street.head are then set to a instance of the class IntConnector.

[polarkernel]

Another possible solution is to use a separate class for the connectors and to get rid of the connector indices all together.

This is a great idea, I like it. A circular doubly-linked list of instances of IntConnector. The class Intersection would need an anchor to hold a start of this list, for example connectors. Similar to what we already did in the old implementation, within IntConnector, the attribute self.index is the index of a vertex in the intersection polygon, so that the item connects between self.index and self.index+1. Either the sign of this index or the additional attribute self.fwd, which is True, if the start of the street is connected, and False otherwise, define the direction of the street. I would prefer the latter. The order of the polygon in Intersection is counter-clockwise, so it makes sense to order this circular list in the same direction. The class definition becomes then

class IntConnector:

    def __init__(self, intersection):

        # the intersection, to which the connector belongs to
        self.intersection = intersection

        # the first index of the connector in the area polygon of Intersection
        self.index = None

        # the item, to which the connector is connected to
        self.item = None

        # the direction of the item, to which the connector is connected to
        self.fwd = None

        # the preceding connector in the intersection (in clockwise direction)
        self.pred = None

        # the succeeding connector in the intersection (in counter-clockwise direction)
        self.succ = None

OK for you?

street.tail and street.head are then set to a instance of the class IntConnector.

You mean street.pred and street.succ in my image.

Once all the items are set up by the StreetGenerator, do you already have an idea of how you want to access them? It is not possible to just provide a starting item and then to follow the links, because the network may contain islands.

[vvoovv]

The class Intersection would need an anchor to hold a start of this list, for example connectors.

Is a list of connectors? I suggest having an attribute with the name startConnector or firstConnector that holds a reference to an initial connector.

Either the sign of this index or the additional attribute self.fwd, which is True, if the start of the street is connected, and False otherwise, define the direction of the street. I would prefer the latter.

self.index can be also equal to zero, so it can't be used to define the direction of a street. I think the term "incoming" is used throughout the code. I suggest naming it self.incoming.

OK for you?

Yes, with the notes above and below.

You mean street.pred and street.succ in my image.

Yes.

Once all the items are set up by the StreetGenerator, do you already have an idea of how you want to access them?

for src, dst, key, street in manager.waymap.iterSections() seems to be ok for accessing the streets. There is a special case of a circular street. In that case street.tail is equal to street.head. The attributes street.pred and street.succ aren't used.

It is not possible to just provide a starting item and then to follow the links, because the network may contain islands.

Doesn't manager.waymap.iterSections() return all Streets if there are islands?

[polarkernel]

Is a list of connectors? I suggest having an attribute with the name startConnector or firstConnector that holds a reference to an initial connector.

It is a circular doubly-linked list. The attribute startConnector of IntConnector holds a reference to the first connector in the list:

self.index can be also equal to zero, so it can't be used to define the direction of a street. I think the term "incoming" is used throughout the code. I suggest naming it self.incoming.

You are right. To be consistent with the existing code, I named it self.leaving. If this is True, this means that the start of the street is at the intersection. The sequence of the items in Street start at head.

for src, dst, key, street in manager.waymap.iterSections() seems to be ok for accessing the streets. There is a special case of a circular street. In that case street.tail is equal to street.head.

Yes.

The attributes street.pred and street.succ aren't used.

Yes, if it is a circular street with no intersection. For a loop, which is also kind of circular, these must reference their intersections

Doesn't manager.waymap.iterSections() return all Streets if there are islands?

Yes, it returns all Streets in the network.

[vvoovv]

I think everything is agreed now. Looking forward to the intersections in the street renderer.

[polarkernel]

I think everything is agreed now. Looking forward to the intersections in the street renderer.

All this is already implemented in the current version. Most of the intersections already look as desired, when executed in script mode:

but there are overlaps, because we do not yet have any clustering, which can produce some "salad" like this

There also seem to be some minor bugs in the construction of the intersections. However, the structures should already be correct (though not yet thoroughly tested), so you might want to do some initial checks.

[vvoovv]

Would it be possible to enable trimming of centerlines due to the intersections?

[polarkernel]

Would it be possible to enable trimming of centerlines due to the intersections?

Committed. It is a very temporary solution, implemented only for your checks. It will be solved elsewhere, once I finalize the code.

Note: Section has become an attribute valid. Use only valid Sections.

[vvoovv]

Note: Section has become an attribute valid. Use only valid Sections.

If a Section in a Street is invalid, does it mean that the whole Street becomes invalid?

[vvoovv]

Also, I'd like to have all Intersections in a Python list (e.g. manager.intersections). I think it's much easier to create it in the street generator, than trace the intersection in the renderer down, since the Intersections are created consequently in the street generator.

[polarkernel]

If a Section in a Street is invalid, does it mean that the whole Street becomes invalid?

For now, yes. This is only a temporary solution, because I cannot handle all problems with short sections at the moment. Later, invalid sections will be removed, and the links will be adjusted somehow.

Also, I'd like to have all Intersections in a Python list (e.g. manager.intersections).

I assumed that when I asked for "how you want to access them". I will provide that as soon as possible. Currently, only intersections with three or more leaving sections are processed. Later, the others will become SymLanes, SideLanes, Corners(?), ..., they are not yet included in this list.

[polarkernel]

I will provide that as soon as possible.

Committed.

[vvoovv]

I'll take some time to develop the code.

I'd suggest including SymLanes and SideLanes in the next step. I suggest not including them to manager.intersections, since there is a 1-to-1 mapping between a transition and its Street.

[polarkernel]

I'd suggest including SymLanes and SideLanes in the next step. I suggest not including them to manager.intersections, since there is a 1-to-1 mapping between a transition and its Street.

OK, I intend to implement them as a linked instance between two Sections in a Street, as shown in the image here.

[vvoovv]

OK, I intend to implement them as a linked instance between two Sections in a Street, as shown in the image here.

I meant exactly that.

[polarkernel]

I'd suggest including SymLanes and SideLanes in the next step. I suggest not including them to manager.intersections, since there is a 1-to-1 mapping between a transition and its Street.

A first version has been committed. I think the new classes SymLane and SideLane are almost self-explanatory with my comments. They are embedded in their Street in a double-linked list, as shown here.

For SideLane, the incoming and outgoing sections are not trimmed at the transition vertex. The transition must be created in the addon. The widths of the incoming and outgoing sections are still corrected according to this post.

A SymLane contains an attribute area, which is the polygon of its transition area. The incoming and outgoing sections are trimmed at the transition vertex to fit the transition area. I didn't add connectors as we did for Intersections. The incoming (smaller) section always connects to the vertex area[0] and the outgoing section to area[2] (as the first vertex in counter-clockwise direction).

In the current version, sections are not yet split by Corners, as discussed here, because we do not yet use parallel sections.

[polarkernel]

I didn't add connectors as we did for Intersections.

Sorry, I forgot to remove some code that uses connectors in SymLane. A fixed version without this code is committed.

[polarkernel]

I committed a version with code for experimental intersection clustering. This is only for backup reasons, the code itself is not called.