(2015-09-08T15:16:18Z) @kevinkreiser : originally created valhalla/loki#62

Loki only checks the tile that you land in for an edge. There are two problems with this:

• there may be an edge that is right on the input but doesnt actually occur in the tile because the edge has no nodes in the tile
• there may be an edge closer to the input especially if the input is right near the tile edge

This happens most prominently in remote areas or areas transitioning from suburban to remote

The fix is to consider other tiles when certain conditions are met. Some possible conditions might be:

• no edges occur in this tile
• the input was close to the edge of a tile

(2015-10-07T20:20:14Z) @kevinkreiser : this issue is related to issue: https://github.com/valhalla/loki/issues/72

(2016-01-08T13:47:40Z) @kevinkreiser : originally created valhalla/mjolnir#336

in order to support https://github.com/valhalla/loki/issues/72 we need to bin the edges into the tiles. work is underway in midgard to support intersecting the bins: https://github.com/valhalla/midgard/pull/69

whats next is to hook this up in GraphValidator. once there we'll need to continue work on the loki issue mentioned above

(2016-01-08T20:02:31Z) @kevinkreiser : originally created valhalla/mjolnir#340

check the valhalla.json config for the required items before doing any of the work. nothing more annoying than getting most of the way through a conversion and then segfaulting at missing config item.

A request which includes a date_time from an area in a time zone with a positive offset from UTC such as the following:

https://valhalla.mapzen.com/route?json={%22locations%22:[{%22lat%22:52.51221,%22lon%22:13.32697,%22date_time%22:%222017-01-24T18:00%22},{%22lat%22:52.524742,%22lon%22:13.369563}],%22costing%22:%22auto%22}

returns the following JSON

{
  "trip" : {
  // ... //
    "locations": [
      {
        "type" : "break",
        "side_of_street" : "right",
        "lat":52.512211,
        "lon":13.326970,
        "date_time":"2017-01-24T18:0001:00"
    },
    {
        "type" : "break",
        "side_of_street" : "right",
        "lat":52.524742,
        "lon":13.369563,
        "date_time":"2017-01-24T18:0801:00"
    }
  ]
  // ... //
}

Note that there is a missing + to indicate UTC+1 in the time zone component (it should read 2017-01-24T18:08+1:00). The example in the documentation, which is in UTC-4 does have the correct time zone marker.

Java 8's java.time.OffsetDateTime.parse() fails with :

java.time.format.DateTimeParseException: Text '2017-01-24T23:1701:00' could not be parsed, unparsed text found at index 16

Hi, I'm not sure if this is the right project for the API or for the router implementation, but I'm getting an HTTP 504 timeout when I submit a very simple multimodal query to the service. Note that requesting a walking route for the same pair of locations does return successfully. I found the coordinates for a pair of test locations in Berlin, Germany, with the Search API, and used these location values to send the Mobility API request.

My JSON:

{
  "locations" : [ { "lat" : 13.32697, "lon" : 52.51221}, "lat" : 13.369563, "lon" : 52.524742 } ],
  "costing" : "multimodal",
  "date_time": {"type" : 1, "value" : "2017-01-17T10:50" }
}

and the request

https://valhalla.mapzen.com/route?json={"locations":[{"lat":13.32697,"lon":52.51221},{"lat":13.369563,"lon":52.524742}],"costing":"multimodal","date_time":{"type":1,"value":"2017-01-17T10:50"}}&api_key=mapzen-MyApiKey

Since all the multimodal examples in the documentation include a street and I'm not, I tried removing the street element from the request in the examples in the docs, but they do return data correctly, even without a street, so that's not the issue.

Any help would be appreciated. Thanks in advance!

(2015-07-07T22:23:18Z) @kevinkreiser : originally created valhalla/mjolnir#275

since we drop a bunch of temp files while parsing data and creating the graph it might be possible and useful (especially for larger imports) to pick up where the import left off. think about implementing this

• location Count - only need to know if it's 2 or multipoint for charting
• costing type - good
• only need trip length for analytics
• may be able to remove trip time (use only for debug)
• language - good
• admin - look into combining these into a list of countries and list of states instead of separate lines
• remove # passes (# of iterations??)

(2015-10-06T19:07:08Z) @kevinkreiser : originally created valhalla/loki#72

It can occur that the closest edge to return is actually not the edge that is returned. picture the following:

 ______________________________________________________
                    \         a 
                     \
                      \ c
                       \
                        \__________
                              b



                              X

The problem here is that we use a radius check to determine which edges are really reachable from a given spot. Clearly the correct edge to return here would be b but the edge that gets returned is a simply because a has a much larger length and so its radius of influence encompasses X where b's does not.

Clearly the radius approach would work well in a very dense urban area or even a place with homogeneously-lengthed edges, but sadly as is always the case, the real world is never like this. So the fix...

Ah but wait, you might be thinking.. we cant talk about a fix until we understand this 'radius of influence' non-sense. Ok fine.. The simple answer is we do this so we can quickly reject a large portion of edges that cant be all that close to the input. And in truth it works, except for when the best answer is reasonably far away from the input.

So yeah whats the fix?

• we could consider more edges by loosening the radius, this will make everything slower and still miss some cases
• we could look at the number of edges or nodes in a tile and decide to search them all if the tile is sparse, shouldnt hurt performance if we do it right but you could still get the wrong answer
• we could set a mask on every edge and only consider edges whose mask is close to the input location

lets exapnd on that last one (beause its a huge feature request...) link to feature request issue is forthcoming...

(2015-10-07T20:20:08Z) @kevinkreiser : this issue is related to issue: https://github.com/valhalla/loki/issues/62

(2015-12-17T18:57:50Z) @kevinkreiser : Ok so after thinking about this for a while it seems the last bullet point above has the most merit. The idea of marking edges in such a way as to know what subsection of a tile they belong to sounds promising.

The idea is that you can start with the subsection of the tile that is closest to the input and fan out radially from there. In terms of implementation though this seems a bit suboptimal. For one it we'd still have to iterate over all edges in a tile to find ones that hit our mask. It also doesn't allow you to address an edge that crosses through a given tile but doesnt have either end point in the tile. So we have a better implementation.

We are going to add a variable sized data structure to the end of the tile. The data structure will just be a list of global edgeids. This allows us to list edges that cross through tiles but dont have end points in them. We'll keep a structure that tells us where a given subsection (bin) within a tile starts and ends in that list. That way we can iterate over all the edges in that bin and fan out radially to bins surrounding that bin if need be.

(2016-02-23T13:54:01Z) @kevinkreiser : here's another case: https://www.openstreetmap.org/directions?engine=mapzen_car&route=53.7962%2C27.7552%3B53.7329%2C27.8498#map=14/53.7815/27.7791

(2016-04-12T14:25:20Z) @kevinkreiser : originally created valhalla/loki#118

if loki ends up finding a few results that are all pretty close to the same distance away we should send all of them on to thor (in the absence of proper fuzzy matching). this is somewhat of an interim form of fuzzy matching or the precursor to result scoring. basically the only criterion we have right now is distance so if the distances are similar we may as well include multiple similar results.

this may be quite tricky without refactoring the way that the favoring of a heading works.

Valhalla provides the shape of the path that it routes you along:

curl 'https://valhalla.mapzen.com/route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A42.358528%2C%22lon%22%3A-83.271400%7D%2C%7B%22lat%22%3A42.996613%2C%22lon%22%3A-78.749855%7D%5D%2C%22costing%22%3A%22auto%22%7D&api_key=valhalla-...'

{
  "trip": {
   ...
  "units": "kilometers",
  "legs": [
    {
      "shape": "_ojxoApmny}CnaB{AWik@]}_@U{j@Wy`@e@mi@G{`@Ma]Wik@?mU?sFUoSOwXGsFMcGqCupGe@mU{@sPu@kLiBaRm@sFsBqQiBuOkAmKu@yLe@sP?_JFoI\\gMt@{LhCiWnC{UrAuO\\oINoIFoI?cPWkj@qB_kG?_JOo]aBiqD?{A?{A]mhAGqGe@iaAGcFe@ceA?..."
    }
  ]
}

But what I'd really like is the IDs for the OSM ways that comprise this shape. Is there a way to get these out? If not, consider this a feature request.

(I wasn't sure which repo to file this on—feel free to close and suggest one.)

(2015-11-17T19:59:32Z) @kevinkreiser : originally created valhalla/mjolnir#318

add gzip encoding to curl when hitting transitland

(2015-05-29T20:36:34Z) @kevinkreiser : originally created valhalla/tyr#59

so the config file is in each repo. we should make a new repo with configs in it and make them all submodule of each repo that way there is only one place to make config changes. note to check each repos config dir and make sure everything makes it to this new config repo

(2016-01-18T14:48:04Z) @kevinkreiser : originally created valhalla/midgard#70

take a mostly horizontal line that stays in the same tile but crosses one subtile in the x direction. this will make it seem as if the linestring leaves the tile:

for a standard lat lon grid this shape should stay in one tile:

std::vector<PointLL> shape{{9.5499754, 47.250248},{9.55031681, 47.2501144}};

namely tile 791318

(2016-01-18T14:48:21Z) @kevinkreiser : unit test proving this. fix for it is forthcoming..

(2015-08-26T13:49:43Z) @kevinkreiser : originally created valhalla/mjolnir#296

Loki tests and (future) Thor tests need data to test on. Its crazy but that requires them to depend on Mjolnir for writing tiles. There is a bit of code already in Loki's search test that creates a fake tile on the fly. We should move this over to Mjolnir as a standalone binary program that takes some json input and creates fake tiles out of it...

If we wanted to be really crazy we could add datasource format support for geojson to pbfgraphbuilder (and change its godforsaken name) so that we could just cut tiles like normal but from a geojson source.

This wouldn't remove the Mjolnir dependency for Loki or Thor if they wanted to create tiles on the fly in code, but it would allow us to create and checkin test tiles for both Loki and Thor. We would only need to update these if the tile format changes, which is infrequent enough to make this palatable.

(2017-01-18T16:27:04Z) @kevinkreiser : Thinking about this some more lately as we are working on open traffic initiatives. @zerebubuth was working on some tests for a node search algorithm inside loki and had the same need for fake tiles. this got me thinking. a program working with geojson is still a good idea but its also nice to programatically be able to generate tiles. i started thinking about what would be the easiest way to do this. looking at valhalla_build_tiles it seemed to be the easiest thing to do would be to mimic the parsing step so that the rest of the builders enhancer validator etc could be run as normal. i was thinking we could implement the same interface as pbfgraphparser and then override the functionality of the parser callback stuff with something that just iterated over in memory data structures. what would be really cool is if we could template pbfgraphparser with the type of parser callback object some how and then just implement an in memory parser that takes in memory ways as input.

(2016-02-17T15:25:35Z) @kevinkreiser : originally created valhalla/odin#198

we want to build the languages into Odin for the sake of convenience. basically its nice to test this stuff in Odin where it belongs and its nice to not have to worry about where the language files are when you want to run the code.

(2015-08-25T16:57:44Z) @kevinkreiser : originally created valhalla/loki#59

Sometimes the closest point on a given edge is one of the end points. In this case we may want to return a node snapping result via CorrelateNode as this will return more edges in some very unlikely edge (pun intended) cases. Currently we will return a single edges directed edges with distance along set to 0/1.

(2015-09-25T14:30:25Z) @kevinkreiser : originally created valhalla/loki#66

when favoring you want to look at the shape before the point where the location is snapped. currently its looking at the shape leaving it. this doesnt make sense, because during location searching we want to find the edge that the person/bike/car/object is on currently using its current direction of travel. the current direction of travel wouldnt possibly factor in path geometry that is in front of it so why would we use this to make a match? its easiest to see why this is wrong by thinging about an edge that is just a cusp, like a V. if the thing is traveling from left to right and they are really close to the bottom cusp of the V their angle might be 165 or something. but if you were to consider the shape leaving the location the angle would look more like 15, and there for we would think that we had the wrong edge in the road network.

its more complicated than that of course. it may be the case that you want to consider the point at the end of an edge in the reverse direction and indeed there is no shape behind it to consider. the only thing to do in this case is to consider shape in front of the point but in the reverse direction.

what this ends up being is somewhat of an estimation of the angle of the tangent in a particular direction along a discretised curve.

Overall project description with some tips on what each repository contains.

(2016-01-08T14:13:03Z) @kevinkreiser : originally created valhalla/skadi#37

need to think about data scripts making geotiffs, particularly:

-double resolution to account for potential higher res sources
-mercator projected tiles for some selected zoom levels

(2015-10-02T14:45:32Z) @kevinkreiser : originally created valhalla/baldr#200

nodeinfo has redundant info:

NodeAdmin::dst is not needed as we can get it from boost time zone database
NodeTypeInfo::type doesnt need to have rail and bus differentiated since we already have multi transit stop, so delete kRailStop = 4 and kBusStop = 5
NodeTypeInfo::end is completely redundant with IntersectionType::kDeadEnd, delete the former keep the latter

Hi!

We list in this issue some trips that should give a solution, but Valhalla doesn't. They seem related to projecting on the wrong edge. I have ordered them by importance.

Foot on isolated steps

OK:
https://www.openstreetmap.org/directions?engine=mapzen_foot&route=48.90592%2C2.28339%3B48.90675%2C2.28512

KO:
https://www.openstreetmap.org/directions?engine=mapzen_foot&route=48.90588%2C2.28345%3B48.90675%2C2.28512

Projecting on https://www.openstreetmap.org/way/421240429 is not a good idea as it is an isolated highway=steps. This case is very frequent for us as isolated steps are frequent in OSM data. Thus, the rail station indoors in France are mapped with a lot of area=yes, creating isolated highway=*.

Dead ends (one way impasse)

OK: https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.84897%2C2.37071%3B48.84931%2C2.37145

KO:
https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.84931%2C2.37145%3B48.84897%2C2.37071

The 2 trips are the same in reverse. The OK one arrive on https://www.openstreetmap.org/way/48564260 that is a highway=service,oneway=yes with nothing after. The KO one start from this way, and thus can go nowhere.

Same problem by bike.

Car with a service road

OK:
https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.89362%2C1.87192%3B48.89403%2C1.87463

KO:
https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.89348%2C1.87196%3B48.89403%2C1.87463

Looks like projecting on https://www.openstreetmap.org/way/49706259 is OK. This way is highway=service. But projecting on https://www.openstreetmap.org/way/49706261#map=19/48.89298/1.87208 gives no results. This way is highway=road and is connected to the routing graph only via /way/49706259.

Double service by car

OK:
https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.87712%2C2.35972%3B48.87628%2C2.35741

KO:
https://www.openstreetmap.org/directions?engine=mapzen_car&route=48.87714%2C2.35971%3B48.87628%2C2.35741

By car, projecting on https://www.openstreetmap.org/way/402745839#map=19/48.87739/2.35898 highway=service,oneway=yes didn't find a trip, but projecting on https://www.openstreetmap.org/way/407973093 is OK (also highway=service,oneway=yes). It works by bike. Looks like there is a rule "can't go to a service road" that don't work in this case.

Walking parts inside underground parkings

OK:
https://www.openstreetmap.org/directions?engine=mapzen_foot&route=48.87742%2C2.35851%3B48.87628%2C2.35741

KO:
https://www.openstreetmap.org/directions?engine=mapzen_foot&route=48.87744%2C2.35853%3B48.87628%2C2.35741

Seems to project on https://www.openstreetmap.org/way/403517979 highway=service, but to go to the outside, we should take https://www.openstreetmap.org/way/402745839#map=19/48.87739/2.35898 which is highway=service,foot=no.

(2016-04-11T16:33:37Z) @kevinkreiser : originally created valhalla/loki#117

currently the connectivity information is at the local tile level in terms of granularity. this is pretty good but the way we make use of it isn’t great. essentially we take the input points and if the tiles they land in aren’t connected we say there is no route. this isn’t really very good. especially because loki can indeed find points up a certain threshold away from the original input. if the input were close to a tile that was connected but just not in it, the route would fail. so we need to use a similar approach.

we should check the set of tiles within this threshold to see if they are connected to be sure we aren't rejecting perfectly good routes. the downside is that some will still fail but the upside is that we wont reject ones that we shouldn't

(2017-02-01T18:28:53Z) @kevinkreiser : fixed in #131

(2016-03-22T20:16:03Z) @kevinkreiser : originally created valhalla/loki#113

How does searching in loki work!? Lets describe the current implementation and what is still desired from it. Pictures or ascii art would be a huge plus!

(2016-04-15T17:51:12Z) @kevinkreiser : originally created valhalla/baldr#242

so we make sure to right fixed width type integers in our tiles. this means that independent of the architecture we dont have to worry how many bits an int might take up.

what we dont make sure of is what order those bytes are in. an arm device can be bi-endian apparently (https://en.wikipedia.org/wiki/Endianness#Bi-endian_hardware) but the machine we are cutting tiles on is probably going to be little endian...

we have some options.

• write tiles in network order using inet.h and the nton(s|l|ll) functions and then have the clients convert them to host order using hton(s|l|ll)
  • this costs on both the tile making and tile reading but lets us have only one tile set
• write them in a specific order and only convert them if the client is different from that order
  • this is may be equivalent to the option above depending
• write two sets of tiles in each order and direct clients to the appropriate one
  • this make cutting tiles take longer but makes using them fastest

(2016-04-15T19:28:05Z) @kevinkreiser : seems android is pretty much all little endian as well but there be dragons with word alignment...

(2016-04-04T19:17:33Z) @kevinkreiser : originally created valhalla/midgard#80

polyline encoding is great because its pretty standard across the mapping world. its nice because it results in chars in the visible ascii range. but strictly speaking we dont care about viewing it when we use it to store shape in routing tiles. can we make use of even the invisible ascii range to save even more space (by having more precision per byte), indeed can we use another offset encoding scheme to do it faster or with less storage. do some research to test this...

(2016-05-16T14:07:32Z) @kevinkreiser : this has been done as of a few weeks ago

(2016-01-08T13:56:27Z) @kevinkreiser : originally created valhalla/tools#1

we want to put path_test, city_test, adjacency_list_benchmark, skadi_benchmark, loki_benchmark, time_distance_test tools/tests into this repo.

first step autotools scaffold. second step, move all the source.

(2016-01-08T13:58:00Z) @kevinkreiser : ill do the autotools fun, @dgearhart can have the code motion ;)

(2016-01-14T20:22:04Z) @dgearhart : moved over the path test scripts and route request files into new directory structure
re factored to work in new directory structure
added documentation for scripts

• check current performance on current services to tune configurations
• need to implement on new services such as trace_route & trace_attributes
  NOTE: We should advocate for POST requests for trace_route & trace_attributes

Note from Kevin: The thing about long request logging is that it should only be triggered when the request took abnormally long. The idea being that if it did, then maybe something is wrong with the request and we need it to debug it.

(2015-10-16T18:00:17Z) @kevinkreiser : originally created valhalla/baldr#203

Currently we load tiles on demand into a memory cache from disk. It turns out that we often max out disk iops well before the CPU. Basically we aren't able to feed the CPU route network data fast enough.

A while back we spent a bunch of R&D trying to figure out how to make a shared (amongst processes) cache for tiles. It turns out that really all approaches were slower than just reading the tile off the disk into memory and keeping it there for as long as you can. So that is what we do. Today.

So why were the previous approaches not good? Well, fundamentally our data is lots of little pieces (tiles) of a larger route network. Only 2% of all the tiles are larger than 1mb. The median tile is likely in the 100k range. That is pretty small. So most of the approaches would take these small items, pump them into an off the shelf cache (think memcached or kyotocabinet) and then retrieve them from it when needed. Hard problems like, consistency, eviction and synchronization are handled by the cache of choice. This is really nice because it means you dont have to tackle hard problems, but... It's really slow... By and order of magnitude in the best case...

So we did more experiments, this time with memory maps. Memory maps are amazing. We use them for lots of stuff because they provide all the things we need: shared, opportunistic, in-memory caching controlled by someone else (namely the OS). The thing about memory maps though is that they are only really useful for reasonably large files. The tiles just dont fit the bill and again they are basically just marginally slower than the current approach of just reading them from disk.

So we are screwed, we have a crap ton of little tiles, and lets face it, little tiles are the coolest thing about Valhalla. They allow for arbitrary extracts, they should allow for arbitrary updates, they make searching the data easier because you dont have to keep an index (they are the index), they may make associating other data easier as well. So yeah, there is nothing to do. Not exactly.

What if we just cram all the tiles into one file. They are still tiles, so you can still reference them individually but instead of referencing them by file name, you can reference them by a byte offset from the beginning of the file. Sure, we'd need to keep an index of what tiles are where within the file but we can scan through 35gb of planet data, in what, a minute on modern hard drives. We could even arrange the tiles within the file so that tiles close to each other in space are close to each other in the file. The good news is, we still have tiles. Which means we can still serve up individual tiles (either from the one large one) or as singular items on the disk/s3. But the even better news is that we can memory map the massive file and let the os handle which bits (tiles) are actually in memory at any one time. And because its shared amongst processes we can keep more in memory at any one time without wasting the overlap.

The best bit about all of this is that we wouldnt need to change much of the code. GraphTileReader would simply still return const GraphTile*. We would need two things:

• a little program that could:
  • write an index header followed by all the tiles into one big fat file
  • break the big fat file back into files on disk
• add to GraphTileReader to detect the big fat file and change its mode of operation accordingly

(2016-02-02T14:17:52Z) @dnesbitt61 : Might consider breaking into separate files based on hierarchy level.

(2016-02-02T15:24:47Z) @kevinkreiser : Yep totally!

example: location_count: , language: , trip_distance: , etc.
UDP?

Hi,
Looking at https://mapzen.com/projects/turn-by-turn/ it's not clear where/how to report bugs. The README in this repository lists multiple sub-projects but as outsider it's not entirely clear where a routing bug would make most sense.

1. go to http://www.openstreetmap.org/
2. search Newhaven, England => Dieppe, France and select Car (Mapzen)
3. the proposed route is 339km (4:20) via the Dover => Calais Eurotunnel

Other routing engines propose the ferry (about 4 hours). I could understand preferring the Eurotunnel when looking strictly at time-taken since the ferry runs only 4x per day.

When selecting Foot (Mapzen) I see Distance: 130km. Time: 25:34.. The time is odd since a person wouldn't walk the 130km.

(2015-07-17T15:35:35Z) @kevinkreiser : originally created valhalla/skadi#7

nested vrts help performance significantly when querying (quad tree collision detection is far cheaper than testing all tiles). however the current implementation of sample doesnt support this. gdallocationinfo does correctly support this so it should just be a matter of figuring out how it does this exactly and replicating that functionality in sample

turns out we do support nested vrts but we are very sensitive to the relative directory structure. this is apparently an issue with gdalbuildvrt and whether it sets the relativeToVRT to 0 or 1. so if you build a vrt like this:

gdalbuildvrt foo/bar.vrt foo/baz.vrt qux/norf.vrt

and you look at the resulting foo/bar.vrt you will see that because the it is in the same dir as foo/baz.vrt it will be set to 1. however the entry for qux/norf.vrt will have relativeToVRT set to 0. This doesnt make sense as you then dont know where the hell qux/norf.vrt is relative to (obviously relative to the CWD when you ran the command but that isnt stored anywhere).

(2015-09-29T13:07:27Z) @kevinkreiser : originally created valhalla/loki#67

currently loki::search is not robust to missing data. it assumes that if the closest edge to your input is found that its opposing edge will be there, regardless of whether it is in an adjacent tile, and whether that tile is even present. this is important for the future as we make extracts of tiles from the planet. we will end up with tiles that have edges ending in adjacent tiles that wont have been included in the extract.

one solution would be to filter any edge that has an end point in a non existent tile. using the connectivity singleton the filter could easily filter any such edge. if we choose this approach we might want to migrate this issue to sif

(2015-09-29T13:23:55Z) @kevinkreiser : seems since sif filters dont inherit functionality (as of yet) it might be best to keep this broader filtering in loki to avoid accidentally not including it in a future as of yet unwritten costings filter

(2016-05-16T14:39:04Z) @kevinkreiser : this has been fixed automatically as a result of using the binned edges for searching.

(2015-07-07T14:39:49Z) @kevinkreiser : originally created valhalla/thor#182

the scripts directory has many things other than scripts. it was fine when it was small but its huge now. we really should consider moving this to another directory

Using the Mobility Explorer, the isochrone with a starting point in Schönefeld Airport shows that it would take significantly more than 60 minutes to reach the city center. A quick look in any of the transit agencies in Berlin (BVG, VBB, or S-Bahn) show that this trip normally takes between 30 to 50 minutes depending on the route.

Such inaccuracies are widespread for any location chosen in the Berlin area. I haven't found a single location which reports correct information.

We were thinking of using the Mobility API for a project at university, but unfortunately the public transport data for Berlin is unusable. It seems to be in the registry at Translitland and I know for a fact that the City makes GTFS data publicly available, so I'm not sure where the problem is. Any help would be appreciated.

(2016-02-05T19:30:17Z) @kevinkreiser : originally created valhalla/midgard#74

there is a pretty straight forward way to version this library and let pkg-config detect the version etc. prime_server does this. it also removes the need for m4 files.

this is related to:

valhalla/chef-valhalla#88

(2016-05-16T14:30:50Z) @kevinkreiser : this has already been done but it since we're really trying to get this all in ppa form we can actually ditch the per repo pkg-configs. we'll do that after we have that working

(2016-06-14T17:57:09Z) @kevinkreiser : actually we'll let the per repo pkg-configs around in case someone likes developing that way (i think most of us do)

(2015-08-21T15:07:48Z) @kevinkreiser : originally created valhalla/loki#57

/locate is nice but it would be nicer if it returned more information for debug purposes but also nice to know what happens with the data

(2015-09-22T15:45:40Z) @kevinkreiser : started this, but much more to do: https://github.com/valhalla/loki/pull/63

(2016-02-23T14:00:22Z) @kevinkreiser : originally created valhalla/loki#106

It would be nice if the edge filter didnt give back a yes or no but rather a rating. This would allow use to given several options pick the best one. For example, for autos we could use factors like:

*distance to edge
*current_speed vs edge_speed
*edge class
*current_direction vs edge_direction

the trick would be getting the proper weighting of each attribute. thinking of it as a linear combination, maybe distance has a higher weight than the other two attributes

another point would be that some of the logic for this would be in loki (heading stuff) and some of it would be in sif where the edge filter currently lives

Add flag (like a dnt) for healthcheck. If flag, then do not log (healthcheck) in analytics logging

(2015-09-08T16:00:18Z) @kevinkreiser : originally created valhalla/mjolnir#302

so we made a fix not to allow loops that come from the ways, but it can turn out that you can get a loop that is at the graph edge level via a lolly pop way (a way that connects back to itself).

the initial thing we did was detect when the first and last node of a way was the same. however we simply need a more generic rule. if any nodes of a way are the same then we have a loop and need to split it.

so the fix will be in the same place but be a little more costly (n^2 or nlogn) depending on implementation where n is the number of nodes on the way.

(2015-07-07T22:26:09Z) @kevinkreiser : originally created valhalla/baldr#180

geohashes are a standard, and they are already hierarchical. seems like we might want to use this. it makes for nicer tile names (although we would still want ids). the question is how we would store what precision the geohash is at (so we know the size of the thing). this would make requesting tiles easier and would make our tiles more interoperable (at least slightly) with the rest of the world (standard)

(2015-11-17T19:59:09Z) @kevinkreiser : originally created valhalla/mjolnir#317

bboxes in the database get converted into geographies which are patches on the earth composed of 4 interesecting geodesics. this is fine in the y axis as longitudinal lines stay locked to the numbers provided. but it means that in the x axis, there is a slight curve away from the numbers provided. since we treat the earth as piecewise flat, some bbox querries will have more things above the top bbox edge and missing things near the bottom bbox edge (if in the northern hemisphere and the inverse in the southern hemisphere).

We'll want t compute a small buffer based on the extreme (ie mid) point on the x axis geodesics. We'll then need to filter out things that dont fall within the cartesian bounds.

We'll also want to do this when computing the tiles we need to fetch. In other words the bounding boxes that come back from the feeds.geojson must also be buffered. Unless the feeds already account for this. @drewda @irees what do you all have to say about the feeds bounding boxes? do they properly handle for geodesics or are they just the minimum axis aligned bounding box in the cartesian sense?

(2015-11-19T13:47:22Z) @kevinkreiser : @irees confirmed that indeed the feed bounding boxes are the envelope of the convex hull of the geography of a given feed. this means that we will have to find the mid points of the top corners and bottom corners to properly account for what tiles should intersect the regions

(2016-03-15T12:20:11Z) @kevinkreiser : originally created valhalla/odin#241

Currently if a locale is passed in that we dont support the user will get a 400. Previously we defaulted to en-US which was nice because at least you'd get back a route. We should probably re-implement en-US as the default and override it if the requested locale is available. For clarity we should also return the locale used in the response (just like we do for units).

We may also want to default to different units based on the provided locale as well, perhaps this is a separate issue though.

(2015-06-09T17:29:11Z) @kevinkreiser : originally created valhalla/loki#41

We need to be able to get at the json payload from the post body. Should be really easy. Body is already available. Just need to check it in case that no json key exists in the query params

(2016-01-08T14:01:08Z) @kevinkreiser : originally created valhalla/loki#89

right now loki has a mjolnir dep and because of that the rest of the repos that use loki do as well. so the plan is just migrate the fake tile generation code from loki tests to mjolnir and make a fake tile once for testing and any time the tile format changes..

this can do a lot to simplify things.

(2016-02-16T14:20:07Z) @kevinkreiser : originally created valhalla/mjolnir#389

Some ways are marked as area=yes in a lot of cases this ends up being a polygon and not something that is routable. So currently we throw away all ways marked like this.

The problem is, this does throw out some valid routable information. Go here http://taginfo.openstreetmap.org/tags/area=yes#combinations and refine it with highway to see of all marked area=yes what values of highway occur.

You'll notice that there are a lot of pedestrian stuff. Now it may be little pedestrian islands not connected to anything else but if its large enough we might want to still keep it (university on campus pedestrian routing routing?)

So there are a couple of things we could do. Perhaps we should, as @gknisely suggested, not throw away any area features. After all, if the other attribution on the way (the highway tag) makes the way seem not routable it should weed out stuff that is just polygons. Another check we could do is make sure the geometry is not a ring. This is good for most cases but you could see cases (none in taginfo though..) where its a junction=roundabout that might be marked as area as well as being routable.

I have been evaluating Valhalla for offline routing on iOS/Android/Windows Phone targets and
with several changes got it working. Some of the changes I had to do were technical (missing #includes, for example), while other were workarounds due to compiler/platform limitations. The main issue (that is not directly Valhalla related, more like our build system limitation/convenience issue) - we really do not want to use boost libraries that require linking. Header-only boost libraries are fine. The boost libraries that require linking are: regex, filesystem, date_time, system.

The first thing I noticed that though you require C++11 compiler, you still use boost::regex instead of std::regex. Is there are a particular reason to do this?

Another general suggestion - perhaps it would be a good idea to use abstract interface for tile loading?
I made some quick changes to graphreader.cc and graphtile.cc in baldr to use zip archive for tile storage, instead of file system. This allowed me to get rid of boost::filesystem dependency also.

I can prepare pull requests with the changes I made, the question is which of the following changes would you accept:

• Use std libraries where possible instead of boost libraries
• Add common header that is included to fix platform/compiler specific issues
• Implement GraphStorageHandler interface that has FileSystemStorageHandler logic copied from current graphreader and graphtile

(2015-09-22T16:07:14Z) @kevinkreiser : originally created valhalla/loki#64

We have a problem that when a node snap occurs it only gives back outbound edges from that node. But if that search was for a destination location, we really wanted all the opposing edges. There are a bunch of ways to solve this.

We could put it in the calling code, to get all the opposing edges of the returned results, but these wouldnt be filtered and technically could end up giving you an empty or invalid set of results.

That would motivate that we put it in the search itself however the complication of having to look for a destination or origin usable edges seems a bit much for loki and possibly better suited to sif. It might be reasonable to turn the edge filter into a proper functor and imbue the requirement of origin/destination/both into it.

The problem there is that loki still controlls which edges are checked and currently it only checks outbound ones. Which perhaps points to the main problem. For edge search results we consider both directed edges but for nodes we only consider one direction. So indeed we should consider all leaving and entering edges when node snapping!

So yeah the real fix is to, obviously, return all the edges leaving AND entering a node snapped result!

To those of you who are @ mentioned below we'd like to inform you we'll be migrating libvalhalla, which is currently comprised of the midgard, baldr, sif, skadi, meili, mjolnir, loki, thor, odin, tyr and tools repositories into this single repository. We're doing this in an effort to make ourselves more productive but also to make things easier for our contributors. The plan is to have this work completed on the 2nd of February 2017.

We'll be doing this in several steps to make sure the commit history as well as the issues are retained:

• merge the code together (git merge --allow-unrelated-histories) and resolve conflicts
• copy issues (not prs?) using github api, some authors will become mentions instead
• mark old repos as deprecated and eventually remove them
• simplify debian packaging
• update the docs by moving each individual readme to its own place, trim overlap and fix links
• simplify chef valhalla source install
• simplify docker valhalla source install
• simplify circle.yml
• test like mad
• 🎂

Note that because of the projects' directory structures, if you've got work in progress on libvalhalla you should be able to take your patch and apply it mostly cleanly to a branch from the new single repository. The only likely places for collisions would be in places like Makefile.am or configure.ac or anything at the top level directory.

If you are mentioned below its because you've made an issue, a pull request or a comment or you are a watcher or a stargazer on one or more of our main library repositories. A huge thank you goes out to everyone who has been helping us to make libvalhalla so great!

(2016-04-25T18:46:50Z) @kevinkreiser : originally created valhalla/loki#121

currently the ::search part of the api will find a set of edges at a given point. for some use-cases this is not enough. specifically some applications would benefit from a connected set of edges which denote a section of road. for one, address interpolation could use this type of output to generate addresses between two known addresses along a single street. so the current use-case we'll be describing here is directed at address interpolation although this method may be more broadly applicable.

the algorithm would essentially crawl the network to connect up locations on the same stretch of road. this is not a proper routing algorithm. the only criteria is that the edges we add to the path are 'the same' road. basically we want the name to match (hopefully we can use the name consistency flag). there are a couple of important things to think about here.

• api requirements
  • at least 2 locations
  • locations have to be at least with X units
  • locations have to correlate to roads who share the same name
• termination criteria
  • how much road do you unravel before you give up
  • bail when you find a loop?
• output
  • the shape
  • each locations side of street and percentage along the shape

@dianashk @missinglink @orangejulius @trescube @gknisely let me know what i should add to this issue to reflect the prototyping we're about to do

(2016-04-15T18:06:26Z) @kevinkreiser : originally created valhalla/baldr#243

in certain situations the set of tiles available to the routing engine may not be static. specifically if on a mobile device the user decides to download a new set of tiles or indeed they are downloading tiles on the fly, we'll want to either regenerate the connectivity map (geojson) or update the in memory data structure.