New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Isochrones for public transit #1421

Closed
michaz opened this Issue Jul 3, 2018 · 19 comments

Comments

Projects
None yet
4 participants

@michaz michaz added the new feature label Jul 3, 2018

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 3, 2018

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 3, 2018

Note how intermodal isochrones look totally different from walk-only or car-only ones.

First, you get islands, and they are not artifacts, but part of the story. You can get to a far-away place, but you can't get off the bus in between.

Second, you get these cute ice-cream-cone-shaped things around routes, where towards the end of the time budget, the time you have left to spend walking away from the bus stop gets smaller.

@karussell

This comment has been minimized.

Copy link
Member

karussell commented Jul 3, 2018

Beautiful :)

@culebron

This comment has been minimized.

Copy link

culebron commented Jul 4, 2018

I used to do such isochrones with 2GIS or Google PT, but that was paid service, hence low res. In the end I made a hybrid router: routes to stations via PT router, then OSRM foot isochrone. But that was still expensive and error-prone (many unexpected bugs coming out at you).

I did a similar research in Moscow, where isochrones are spindle-shaped. In 30 minutes the subway catapults you in the center, but you can't reach the neighbor subway line.

image

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

@culebron Wow.

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

I think some kind of smoothing would be nice. Look at all the little holes (in Portland), where you can "just barely" not go within the budget. Those are correct, but probably not significant, since travel time should come with an error bar anyway, and the entire hole surely lies within it.

Does that make sense?

@karussell

This comment has been minimized.

Copy link
Member

karussell commented Jul 5, 2018

Yes, skipping holes at a certain is crucial because if we don't do this we would have to show single holes where no streets are leading to too complex polygons.

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

I'll let it sit for a while, since I want some theory before I just say "fill holes smaller than X".

Meaning I'm looking for a better reason than "too complex" (for what?). :-)

@karussell

This comment has been minimized.

Copy link
Member

karussell commented Jul 5, 2018

Meaning I'm looking for a better reason than "too complex" (for what?). :-)

haha, sure 👍

Highly likely this must be configurable (than you also avoid thinking about it ;)): because a database request needs a simple polygon to make the SQL request fast but for a visualization you could show a arbitrarily complex polygon and probably there are many use cases in between.

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

where no streets are

Yeeeeah, that's problem 2. And it's totally not clear to me yet. When dealing with networks, the only "isochrones" where it's totally clear (to me) what they mean are yours, where you just draw links which are reachable and don't draw links which are not, and don't say anything about non-links. But even there, you have problem 1: If one link in the middle is not reachable while all the others around it are, do you remove it or not? Is anything about it special, just because it is 3.7 seconds out of reach?

That's the analogue to the issue with the small holes above.

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

Problems 1+2: How exactly do you operationalize what a fire chief / city planner means when they say "draw me lines around the area which my engines can reach in 8 minutes / people can reach by transit within 20 minutes".

Any geographers here?

[plans a library day]

@karussell

This comment has been minimized.

Copy link
Member

karussell commented Jul 5, 2018

If we use a grid (independent of the road-network) both problems get simpler (I think, but not 100% sure :)):

we just fill a cell of the grid if it contains a reachable point and it stays empty if not and an isochrone polygon then describes the filled area. But for visualization this does not look that good, I fear. Even for high resolution. And for the database request the polygon at the border of this area might be still "too complex". Hmmh.

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

If we use a grid

Yeah, I found that solution implemented, too. It's nice, and it makes sense, but it seems to move the responsibility into the grid cell size parameter, which you just tweak until it looks the way you want it to look. Hmpf.

@culebron

This comment has been minimized.

Copy link

culebron commented Jul 5, 2018

@michaz at my work, we had discussions on smoothing, and I think there's no sane solution to this. I ended just cutting holes away, because in many places they were faults of routing rather than be in physical world.

Grid has its own problems as well. It creates islands of its own, even with foot or car isochrones, which unilke PT should be continuous.

With grid a straight road that goes diagonally (NE, NW, SE, SW) generates such islands. I tried curing it by adding nodes on the highway, which in turn causes more islands because on the other side of 2-way road nodes have much higher duration. See the example: most points fall on the wrong side of the road, and drive time is 10 minutes bigger (you need to make a U turn far away). But one point hits the right side, and gets much smaller drive time (24 minutes rather than 30+).

photo_2018-07-06_01-08-29

Another example:

photo_2018-07-06_01-16-05

We had a sort of "parallel red and green lines in a shape of cat" discussion there. Colleagues suggested ways to connect diagonally situated grid nodes, but in the end there's no easy algorithmic way. Again, the first picture with 24 minutes point faaaar away, won't be fixed this way.

photo_2018-07-06_01-08-02

Since client managers wanted pretty pictures, we just cut off islands smaller than 1/3 of the biggest polygon (yep, arbitrary beauty). You might try hexagonal grid, it does look prettier, but I suspect it still has some artifacts.

Smoothing does not connect islands, quite opposite, it cuts some peninsulas off. See the non-smoothed isochrone and a smoothed one: there are still some quite big islands.

photo_2018-07-06_01-05-19

Smooth surface creates it's own artifacts, I had to abandon this idea completely. In the next picture, you see it tries to continue the gradient (26=>16) to where it does not exist, producing pixels with values much less than 16.

photo_2018-07-06_01-00-49

And a larger view with edge artifacts. Any very different value causes "waves" and insane level curves.

photo_2018-07-06_01-16-08

I made an attempt to put points in every OSM vertice. But surprize, you must put another point on the other side of the 2-way road, because time is different for them. Otherwise, again you get islands:

photo_2018-07-06_01-01-25

Here's that one fixed. I had to add insane amout of points, and to make an insane PostGIS calculation (to put a mirroring point on the neighboring road). It took several minutes instead of 1 second as usual, and still not enough: the water is included in the isochrone while it should not be, but I gave up fixing it already.

photo_2018-07-06_01-00-54

Walking over a graph is more sane, at least Graphhopper produces the best isochrones I've seen. If it can be accelerated a bit, it would be perfect. Right now they are notably slower than OSRM grid + matplotlib, and for instance, in my work, we made about 10K-20K at a time (car/foot/car with traffic for 5,10,15,20,30 minutes, for 100-500 points at a time).

Options

I'd ask for one important option: if we build isochrones for like 10,20,30 minutes, they should be available in 2 ways. One is when 20-minute multipolygons include those for 10 minutes. The other way is have holes.

That's because sometimes you need to count all objects that are reachable in 20 minutes, sometimes you need only those between 10 and 20. In python, I just collected the outer circles of 10-min polys and added them as holes to the 20-min ones.

@culebron

This comment has been minimized.

Copy link

culebron commented Jul 5, 2018

Here's one more or less realistic isochrone with grid. It requires to check how far the point is from the graph. If it's like >250 metres, then it's considered unreachable. But it's not so pretty.

photo_2018-07-06_01-24-51

IIRC, the one with hexes is built this way. This is the absolute best I could ever get. Still, artifacts are visible, although not as disturbing to our corp clients.

photo_2018-07-06_01-00-22

@michaz

This comment has been minimized.

Copy link
Member

michaz commented Jul 5, 2018

+10 for putting this together, and for reinforcing my hunch that doing this graph-based is the way to go.

I had little specific feedback until now.

My re-confirmed current plan is now to let this sit until I have a big block of uninterrupted time, and then try and re-implement this using CGAL, which will let me get constrained triangulations, so that roads are not cut by isochrones just because an outside point encroaches, in sensible computation time, and then.. let's see.

Thanks again!

@culebron

This comment has been minimized.

Copy link

culebron commented Jul 13, 2018

Finally managed to assemble graphhopper to test this branch. When I make a request, it resets connection, but java server continues calculating something, using CPU a lot.

What is memory usage for GTFS? Berlin GTFS worked normally on a laptop with 10GB RAM, but strangely Saint Petersburg GTFS did not, I had difficulties building it.

@karussell karussell added this to the 0.12 milestone Nov 19, 2018

@karussell

This comment has been minimized.

Copy link
Member

karussell commented Nov 19, 2018

Fixed via #1480

@karussell karussell closed this Nov 19, 2018

@kasper747

This comment has been minimized.

Copy link

kasper747 commented Dec 8, 2018

Finally managed to assemble graphhopper to test this branch. When I make a request, it resets connection, but java server continues calculating something, using CPU a lot.

What is memory usage for GTFS? Berlin GTFS worked normally on a laptop with 10GB RAM, but strangely Saint Petersburg GTFS did not, I had difficulties building it.

For Brandenburg I needed 16GM. It takes a lot of memory when building. Therefore I build it on a virtual server.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment