Side-of-Street Routing at rideOS

In the near future, you’ll be able to hail an autonomous vehicle at the click of a button. But in order to ensure that those vehicles are dispatched safely and efficiently, there’s a lot that needs to go on behind the scenes. One major item, with a lot of technical complexity, is providing an autonomous vehicle with exact pickup and dropoff locations, including the side of the street the passenger should be picked up and dropped off from.

Autonomous vehicles will have different capabilities and restrictions, and because we can’t know what situations they’ll be able to handle or not, we need to prepare for the possibility that they won’t be able to navigate a U-turn or depart from the planned route to get the rider to a safe drop-off location.

As an example, let’s say we’re trying to navigate from the north side of Main Street to the east side of Harrison as depicted below:

An example of a Google Maps route that does not incorporate side-of-street routing. Even though the origin and destination were requested on the North and South sides of the respective roads, the route provided forces the rider to cross the middle of the road.

In this situation Google Maps does not incorporate the side of the street you’re actually on and the side you’re trying to get to. If this were a ride hail trip, you’d be forced to cross both Harrison and Main Street (both of which are very busy roads in San Francisco) in order to meet your driver and arrive at your destination, which is both dangerous and unsafe for the passenger!

rideOS’s routing engine ensures that a dispatched vehicle will arrive on the same side of the street you requested the ride from, allowing you to enter the vehicle safely without jaywalking across a busy road. The resulting route for the same request would look like this:

A rideOS route that takes into account the location of the dropped pins and routes based on side-of-street accordingly, allowing the rider to enter and exit the vehicle safely.

In addition to providing a safer experience, side-of-street routing allows our other dependent services like Fleet Planner to be more accurate and efficient. Since riders won’t need to cross roads or intersections to get to their vehicles, pickups will take less time, rides will be safer and more efficient.

A Deeper Look

Although side-of-street routing doesn’t seem particularly difficult to implement, there are a lot of interesting edge cases and technical issues that surface when you dig a little deeper. At a high level, we want to ask the question: which country am I in? And the answer can help us resolve which side of the street we should begin the route from. For example, if we know that the country we’re in is one that drives on the right-hand-side, we can use a vector cross product to help us determine which segment we should use for routing.

This is the basic flow we use to determine which side of the street we should use for routing. Note we have the option of returning both segments as well. In this case, we find the shortest path regardless of which side of the street is closer to the query point!

However, determining which country a point is in is trickier than it seems. As a first pass you might try to find an open dataset with every country’s boundary as a geometry, and then run a point in polygon algorithm to determine which country contains the point. Unfortunately, this method is not robust for points that are close to the boundary of a country (e.g. coastal cities). A country polygon may be very detailed, but can look simplified quite a bit at the boundaries in comparison to the true country outline.

The full polygon for the UK looks quite detailed and complete from outlook, but might be missing quite a bit of detail and is oversimplified on the coast.

This is actually not a trivial problem at all (see the Coastline Paradox). In actuality, this algorithm is a bit too extreme and assumes infinite detail, which will fail in a lot of practical edge cases. Furthermore, ingesting and using this level of detail for the polygon for a point in polygon check is quite inefficient. A ray casting algorithm grows in complexity linearly with the number of edges in the polygon, so this would not be a great way to scale.

To resolve this better, we might consider buffering out the polygons to some extent to handle edge cases near the ocean. However, this too has an unwanted side effect, namely messing up in areas close to a country-to-country boundary (e.g. Tijuana is in Mexico, but might be located in the buffered polygon of the US as well!).

Another idea could be to measure the minimum distance from the query point to each country’s border, and use that instead. Unfortunately, this method also suffers from the same complexity issues as the point in polygon check, and it can fail in some really strange edge cases (e.g. a point right outside of the country of Lesotho is closest to Lesotho’s boundary, but technically in South Africa).

One way to improve both the efficiency and accuracy of these lookups is to partition a country into multiple polygons, and index these into a fast lookup structure like an R-Tree. We have to be careful here again however, as mapping our geographies into something like a Mercator projection will have undesirable effects on countries that lie on the Anti Meridian (like Fiji). At rideOS we’ve developed a method for a doubly-indexed R-tree that can ingest countries that span and wrap the globe.

Finally, we have to consider the use case where no country is determinable for a point (e.g. Null Island). We don’t want to accidentally assign these points to countries that they clearly don’t belong to, but where do we draw the line? None of these are easy questions to answer and we are actively working on improving the efficiency and correctness of our algorithms.

You can try out our API’s and web service for free in certain service areas. Sign up for an account to start using them today!