Isochrone bugs

[dabreegster]

@tnederlof, I've spotted at least 3 different existing bugs with the isochrones. Dumping the investigation here.

Problem 1: time to SidewalkEndpoints vs buildings

Repro: click any start point, go a few streets away, and hover over several buildings attached to the same sidewalk. I can find many examples where the time shown in the tooltip will increase/decrease in the wrong direction, or suddenly jump values.

The problem is https://github.com/a-b-street/abstreet/blob/ecce96fd75cd0ec7ab6d5791916b7a79a73be335/map_model/src/connectivity/walking.rs#L138. We correctly visit SidewalkEndpoint nodes in increasing order. But then after we've produced the costs for those nodes, we have to somehow calculate the cost for each building. The current calculation will pick the SidewalkEndpoint that's closest to the building. But the problem is, that endpoint might not be the one closest to our start point! So in other words, the path that's happening in some cases looks like this: The two circled buildings are closest to the intersection labelled 3. So the path cost we ultimately return reflects that "doubling back" weirdness.

The same bug doesn't happen if you switch to biking mode, because https://github.com/a-b-street/abstreet/blob/ecce96fd75cd0ec7ab6d5791916b7a79a73be335/map_model/src/connectivity/mod.rs#L111 doesn't attempt to fill in the extra detail of building distance along the sidewalk at all.

I'm working on a fix for this problem; it's hopefully simpler than the current implementation.

Problem 2: Contour polygons are wrong or cover stuff up

I would expect that any building in green that you hover on has a time <= 5 minutes, but this one is 6 minutes. I think the problem is how we map to grid cells: https://a-b-street.github.io/docs//side_projects/fifteen_min.html#drawing-the-isochrone There's a physically nearby building with a much lower cost, and I think it happened to "win" here: https://github.com/a-b-street/abstreet/blob/ecce96fd75cd0ec7ab6d5791916b7a79a73be335/fifteen_min/src/isochrone.rs#L158

Even when buildings are physically close by, sometimes the cost to reach them is pretty different and happens to cross that threshold. Sometimes it's because they're on opposite sides of the street, and for bike paths, you have to do a convoluted thing right now to turn around and get on the proper side of the street.

Not sure what to do about this yet.

Problem 3: holes in the contour

This looks confusing / bad. It's because the contours library at the end of the day needs a grid, but our data is spatially sparse -- there are no buildings in the middle of a park/water.

There are actually two attempts elsewhere to deal with this. In the elevation contour map in the main game, we try to fill out every grid cell and just populate it with a value from the nearest matching point: https://github.com/a-b-street/abstreet/blob/ecce96fd75cd0ec7ab6d5791916b7a79a73be335/game/src/layer/elevation.rs#L243

And in the population heatmap, we can optionally "smooth" the grid: https://github.com/a-b-street/abstreet/blob/ecce96fd75cd0ec7ab6d5791916b7a79a73be335/map_gui/src/tools/heatmap.rs#L157

Not sure what we should do for 15m. If we come up with a good technique, probably worth refactoring the 3 places and making Grid handle it directly?

I've googled around for a contouring algorithm that doesn't need a grid as input and can just use points, but I've only found things based on Marching Squares.

[dabreegster]

@tnederlof, I got curious what other approaches to filling out the 2D grid for contouring would do. Here's the current strategy, just mapping each building to its grid cell: Awkward holes where there are no buildings.

Here's using ClosestMatch for each grid cell, searching up to 300m away from the grid cell's center to a building:

[tnederlof]

Interesting! so basically for each grid cell you look at the closest building from the center and color based on that building?

[dabreegster]

Exactly. I might just make a mode to draw the buildings themselves the 3 colors, to be totally clear what the "raw" data is. Everything else really is just interpolation for the sake of communicating the patterns more easily