Finally start routing pedestrian area

General talk
1

This is a simple idea to finally make those area highways routable.
Right now highway=pedestrian area is the only exception where it is allowed to be an area and it is routable… somewhat on this living_street
So if you have got shop entrances on one side of the street, it will lead you to the other side… eventually, just not the obvious direct route.

How basics of a routing works

A node is the basic element of everything we map. We don’t “tag” it, but each node has specified to whcih other nodes it is “connected” This is a construct of ways.
Every area has this, because every node has information of 2 other nodes, so it can be “connected”

Now, if we have square image pedestrian area it has 4 nodes and the diagonal nodes should be virtually “connected”, so they can be routed.

But 4 nodes can form a delta shape imageas well and 2 of the nodes shouldn’t allow routing to directly reach each other.

How do we solve it?

Right now as a changeset is saved to the database, the system receives information which node is connected to each other in exactly the way how we design it. Ways can even overlap each other and that issue is not detected at all.
When we upload a pedestrian area it should be detected and calculated automatically which nodes can be directly connected and that information should be saved into those nodes.
– It should be saved so the routing doesn’t calculate it by itself everytime.

We have got some very complicated and big areas tho, with possibly hundreds of nodes and each of those nodes can possibly by assigned to a hundred other.
Will it be still too much for a routing to efficiently calculate a route via such a number of possibilities?
It might be, so in such a case we have got possibilities i see:

  • make a limit how many connections can a single node have generated and choose em via a smart algorithm
  • should it fail and require human guidance, we can have
    – tags for nodes that we want force connect
    – new interface for it in iD, but what about JOSM? Likely tags are better and relations too cumbersome.
  • add all ways within a pedestrian area to its relation, so nodes of those ways can be added into the automatic generation process

What is a pedestrian relation? It is a basic relation with outer and inner roles for closed ways assigned to such a relation (37 elems there)

The way i describe it, I believe it would be automatically compatible with any navigation system, coz even right now a single node can be connected to a hundred of others if we really design it so manually.
Within a pedestrian area we can already add lots of highway=pedestrian ways that manually connect EVERYTHING, but not only it’s lots of work, but it’s even more clutter than useful…

I put it here in general discussion, because i wonder if anyone tried this approach already?
I also look forward to this or similiar implementation, coz that can possibly solve a lot of other issues that we made some arbitrary rules, just to cope somehow with what we are technically able to map, how it can be routed and how it actually renders.
I look forward to responses.

3 Likes
2

OSM is a geospatial database, not a routing graph. OSM doesn’t store shape_length= and shape_area= for geoprocessing either. The responsibility to make use of the data belongs to routers. Go ask them. Pedestrian and bike routing on areas · Issue #17 · osmlab/osm-planning · GitHub

What you are describing seems similar to a visibility graph. As summarized, OpenTripPlanner already supports it. Build - OpenTripPlanner 2
Another mention as linked GitHub - PlazaRoute/plazaroute: Routing through pedestrian areas
It has been done in France for SNCF including indoor= routing https://www.youtube.com/watch?v=3hi4_2iOsPM Pedestrian routing in complex areas: the case of Paris railway stations :: State of the Map 2019 – General Tracks :: pretalx
Random old presentation with some illustrations for comparison. I didn’t look into how medial axis and straight skeleton look for non-linear shapes before. Maybe it can be a simpler and cheaper approximation (by comparing with the existing routing along the outline to distinguish between sides and diagonals)? Integrating Open Spaces into OSM Routing Graphs for Realistic Crossing Behaviour in Pedestrian Navigation | PPT
Manual generation or fixing isn’t a solution. It’s not scalable to be done widely or on large complicated areas, or reliable for user error and not being updated (forgetting, not knowing, not supproted by applications) when editing.

5 Likes
3

Please read again.
I’m not wanting to store length or its area.
How does OSM know from database that two nodes are forming a way?
– The information is stored already in the database.
I don’t know for certain what’s logic of the stored data, maybe you can simply present it’s logic?
But am i correct that individual nodes are stored in it, because where else?
Those nodes relate to each other, or a way is a separate construct organizing all the nodes within it? Line direction is stored in the database as well, routers do not gues or calculate any of those informations
Why are you implying like they have to?

If a way is a construct that stores information about nodes within it, then it surely knows which of those nodes are part of other ways as well. So i’m trying to gues why are you thinking that i’m describing anything new at all.
We are already connecting manually a lot of nodes just so the router can somewhat navigate and not fail completely
– I have given an example of that.

All i’m writing about is automated process so we can stop connecting a bunch of nodes by arbitrary ways, because system will do it for us and save em to the database just like if we did em all by hand.

As for user error… we already ask user to draw everything and allow em to make errors by design, so really not sure why you saying that user shouldn’t be able to have any influence over the connected node detection process.

4

I think you’re both mostly on the same page. In order to route through an area without relying on an explicitly mapped linear feature, some postprocessing has to happen. The proposed relation members sound like a hint to prioritize some visibility paths over others, but not quite a replacement for this postprocessing. The question is who needs to do the postprocessing.

It sounds like the proposal here is for the OSM API or the planet generation process to postprocess the geometries or the relation-based hints instead of leaving it to individual data consumers to implement. I’ve heard that many OpenTripPlanner instances even disable the visibility graph functionality because it’s resource-intensive. Centralizing that effort in the distribution could make sense if we consider it an essential step for making sense of the data.

I’d look at how the ecosystem is currently coping with the need to postprocess coastlines and lakelines, which are essential in cartography and also less than straightforward.

7 Likes
5

Having information about oneway=yes doesn’t mean OSM stores a directed graph for routing. They are 2 different things. And in fact, routers do have to process oneway= =-1 , =alternating , and =reversible , not to mention oneway:*= , and even *:forward= & *:backward= modes.
Currently, we are handcrafting lines as needed, reasonably done well with human brain. You are asking people to check and verify all highway= + area=yes machine-generated results, then fix them as needed, or even optimize them. That’s not a practical task.
As how =coastline has been mentioned, land or sea polygons are not stored in OSM either. It would be a separate database, service, and project, at most similar to OSM’s Nominatim. They need to be different “layers”. But it’s still impractical to ask for human intervention, to be done in time and for every failure, that you suggested.
Furthermore, I don’t see how tagging could work. You need to uniquely identify each connection. Creating some arbitrary numbering doesn’t fit tags. I don’t understand what a forced connection looks either.

6

First of all, different tags like oneway=yeshave no influence on logic of nodes, ways and it’s specified direction. Those tags use this logic, not change it.
The direction is specified and saved into the database. Every object can only have one way and that way has a direction.
It is not possible for it to not have one. We do have lots of tags that base their specification by this value.

Not asking em to verify all of them xD
This is equally same process as in iD you can see lots of information in the measurement panel and adjust your editing to that if you choose so

every node has an unique ID, When you draw a way it is saved into the database, which node ID has a direct connection to a different node ID.
So very easly as a user input you could tag ID of a node that you decide should be directly routable to a different node. And yeah, you could do it oldschool, but more preferably we’d have user interface for that, so you could select 2 or multiple nodes and just press one button [routable], so tags with IDs generate just like that. And such an interface could easly detect a user error and disallow it. (don’t mistake with generating ID for a separate node itself)
But i already see that it’d be possible for nodes that already have an ID saved in the database and is not a new one, coz otherwise it’d be a conflict nightmare solving puzzle that’s not feasible)

7

If you simply want to produce a preprocessed OSM file then you could use GitHub - PlazaRoute/plazaroute: Routing through pedestrian areas or similar (note that this is 8 years old now, so this has been a solved issue for a long time).

The problem is that the preprocessing is resource intensive and that in the end the routing engine has to deal with a lot more edges in the routing graph. That is already an issue just in pedestrian vs. motor vehicle routing. But yes you could make the argument that running the preprocessing just once could provide some incentive to routing engine operators to use such data instead of “raw” OSM.

4 Likes
8

yeah, i think it would be really useful, but it wouldn’t do all perfectly, coz i describe only user mapped nodes. You couldn’t route to an edge or some point middle of the ocean. A routing that’s plotting a course like that would still have to do preprocessing on its part.

I should have read up sooner, that a way is actually a construct and it has more properties than just a direction.
It is an ordered list of all the nodes and that’s how routings know that nodes in that order are routable one from another and in reverse order as well.
I still don’t know how routing knows which nodes are shared with different objects and how this information is saved in OSM database.
It is a key information, coz routing navigates just fine over shared nodes of different ways.

Who knows how is that determined? Because i don’t see that a way has an information how many other ways share its nodes

9

I did sometimes wonder if and how a way and its drawing direction are stored in the database. I think of it as kind of a relation of type ‘way’ with an ordered list of node members. A polygon then is an ordered list of nodes where the last node refers back to the first node. That would simply be an attribute of the “way relation”.

I can think of many operations editing tools could perform, resulting in additon of nodes or repositioning the nodes, i.e. actually changing the geometry or precision of a way or polygon. I can also think of many operations applications would like to perform on ways and polygons for their purposes, without actually changing the database.

And I can think of operations that applications would perform on ways and polygons, that actually could be written back tot the database, so others can profit. I could also think of operations that are, or could be performed before serving out the data to data users, which would otherwise be forced to do that themselves, all of them, every time.

Is prerouting over an area one of those operations? I don’t know, but I do know that writing the result back to the database would store something that isn’t seen and verified, but computed. Seems to me that could be a helpful function in the editor, so as to refine existing tagging. In a way that you could use a strava heatmap to refine the geometry of a track,which the mapper draws and upoads.
The function could take the pedestrian polygon, and the nodes representing the end points of the highways to the pedestrian area and maybe entrances of buildings, and come up with probable preferential paths over the area between each two intersection nodes. Which the mapper (or tool) could then use to verify and store a walkway over the area, preferably with option to indcate it’s a virtual route, not a physical track.

Tools serving out data maybe could have this functionality built-in, which IMO should be optional (default off). Or applications could use a preprocessing library functions like this one.

But saving the results of processing in the core elements of the database… it’s not visible and verifable enough for that, I think.

10

If that is indeed the case, I’d suggest that you create a proof of concept of that data somewhere, perhaps on the dev server. “Actually doing it” often brings to the surface issues that may not have been considered so far during the “thinking about doing it” stage.

11

yeah, definetly, but i do not have necessary info yet, as in the meanwhile i have found out logic of way is not i have originally supposed – nodes do not relate to each other within their logic. This logic is within way ordered list list of those nodes…

Also i have asked:

12

Typically, people who have covered that as part of a Computer Science course :smile: . I’m sure that there are online versions of those around these days.

Or you could start with a basic explainer that might link to some other useful things.

An alternative might be to start by looking at an OSM-based router and understand how it processes data - and it should help with that specific question. The basic answer to your question is that an OSM router takes OSM data and creates a routing graph with vertices, edges, and weights based on that data. This information isn’t saved in the OSM database - the router creates its own representation of the data in its own format containing the data that it needs.

1 Like
13

that’s somewhat unfortunate then.
We could start saving those connections within a routable area as actual ways from entrances at building wall to a central highway within that area and system could know these if we added them to a relation holding geometry of that area
That’d still require physical nodes added to that central highway tho…
But since i’m thinking about routing between nodes, so it’s automatically compatible with any router on the market, that’s the only solution. Not very clean and more intrusive that I’d like…

The main advantage would be stopping us to draw all those connections manually, but instead have the iD or JOSM client calculate for us. Much less clutter this way

14

That’s an essential part of the process of generating the routing graph (which will of course be customised based on the types of routes that someone wants to create). You can’t store that data in OSM because if you tried, it would be wrong as soon someone changed one routing parameter.

I’d suggest spending a bit of time looking at how an existing router works to understand the issues here.

1 Like
15

That would be possible, if it were just the tool against the one square or rounded area, to create one main connection. In reality, there are a lot of other things influencing the actual potential walk line(s).

For the sake of argument, suppose a tool could come up with nice routes over the area, and suppose you want to store these routes. Each route is an ordered list of nodes, representing the line where people will walk from A to B. I believe OSM already has an object type for that. Just a little ground truth will suffice to warrant saving it as a way.

16

You are talking about routing. Routability between 2 points on an area will be a derived spatial relationship, not inherent in the data structure. The conclusion is again, this will not be stored in OSM proper.
Storing id in tags isn’t done. If you need a specialized editing interface, it won’t be different to use a relation anyway. It’s still unclear what route this will produce. 2 points can only give you a straight line, which won’t work often enough, especially in the complicated cases that made it fail in the first place.
Currently, another significant issue in practice is the misuse of highway= + area=yes for linear areas that area:highway= is for, from misunderstanding, or “mischief” forcing it to render. Much computation resource and time will be wasted on generating area routing graphs on them.

2 Likes
17

Just as we do it with conventional routing, the area router/preprocessor/whatever will have (for the example I mentioned, has) configuration that determines what is used to generate edges and with which weights (that’s why its possible to do bicycle vs. pedestrian vs. motor vehicle vs. horse vs … routing).

1 Like
18

like i have described and linked, for you to see as well

image
image614×288 49.5 KB

it is a big issue on a living_street like this one

If we won’t be able to generate some helper “ways” and store that info in OSM database, no mainstream routing is ever going to route properly, maybe ever.
So what do we do to fix it? Add all those ways manually with all its possibilities tagging and clutter.
Just imagine 100 new ways added manually on this little space, just to connect all the entrances. Because yeah, they nood to be connected
You wan’t those 100 ways to render or you want em to be simply routable only?

Try to help solve the issue, so OSM based maps might be better than guggel some day and ppl actually use it.

19

I’ve seen a lot of talk about pedestrian routing and whenever people claim it doesn’t work (mostly concerning separately mapped footways), they provide an example where the start is at one side of a street and the end is at the other side of the street. These problems are artificial - you don’t need a router to cross a street. With more realistic tasks this problem doesn’t arise anymore.

1 Like
20

tell that to a person who has a sight disability,
anyway, that doesnt help in design.

I would love people try help solve the issue rather than proving that there is no issue at all for them peronally.

1 Like