Where really are the parking spots?
Using RAPIDS to find more accurate walking distance
In the previous story, we explored the cuSpatial and cuGraph libraries from NVIDIA RAPIDS package and used them to find the walking distance to nearest parking points near Seattle’s Space Needle. This was only possible with great help from John Murray of Fusion Data Science who kindly provided a graph of King County roads in a form of a list of intersections (with geo coordinates) and list of edges linking the intersections with calculated length (in yards).
However, a quick look at the map above quickly reveals a problem with our relatively simple approach presented before: the distance from the nearest road intersection to the parking spot is a straight line (as-crow-flies yet again). In this story, we’ll look at how we can fix this.
As crow flies vs as people work revisited
How can we fix the above debacle? Well, an approach that would get us closer to the true walking distance would be to find a spot on a map (for each parking spot) where the location of the parking spot is perpendicular to the road itself as presented in the below graphic.
The blue lines show the current solution. As you can see, we are flying over (or thru) the buildings and intersections and that is something that normal people usually cannot do. The orange lines, however, show a more realistic approach where a person would walk along the roads to reach the chosen parking location.
Thus, we need to add more nodes and edges to our graph: one for each parking location such that the distance to the nearest road is minimized i.e. the node that lays on the line connecting two nodes and, when connected to the location of the parking meter, such line is perpendicular.
Let’s do some math!
Finding an intersection point of two lines given 3 points is a simple problem from elementary school so the below is just a quick refresher.
Given two points on a plane we can quickly find the slope a of the black line connecting the two nodes (road intersections) by taking the difference in latitudes between these two points and dividing it by their difference in longitudes:
a = (lat_pt_1-lat_pt_2) / (lon_pt_1-lon_pt_2)
The slope of the perpendicular line is simply the negative inverse of a:
a_perpendicular = -1/a
Equally simple is finding the constant b of the black line now that we know the slope:
b=lat_pt_1-a*lon_pt_1
We could, of course, use the other point with the same result. Given the slope of the perpendicular line and the location of the parking spot — we can now quickly do the same to find b_perpendicular.
Since the point at the intersection will have the same latitude no matter what equation we use (it is an intersection after all) we can set these equations equal to each other to find the longitude of the intersection point:
a*lon_intersection+b=a_perpendicular*lon_intersection+b_perpendicular
Quick algebraic transformations and we can clearly see the lon_intersection point:
lon_intersection = (b_perpendicular-b) / (a-a_perpendicular)
Finding the latitude is now trivial since we can use either of the equations to get it.
Let’s do some coding!
Now that we have the method, let’s transform it into a RAPIDS kernel.
The points x and y in the above kernel are the two points depicting road, the _REF point is the parking spot. Note: if you are not familiar with defining RAPIDS kernels I covered that in my two previous stories: Where should I park? and Where should I walk? so I won’t be discussing it here.
In our calculations above we did not solve for two special cases: when the road is either perfectly aligned along the north-south or east-west lines. In the former situation (north-south aligned) the longitude of the projected point is the longitude of either of the points and the latitude will be the latitude of the parking location. In the latter situation (east-west alignment) the solution will be the inverse: we take the latitude of either of the points and the longitude will be that of the parking spot.
We can now iterate over all the parking locations. First, we need to append the longitudes and latitudes to the road_graph_data DataFrame; as a refresher, this DataFrame contains only pair of nodes and the distance between them. We will get these from the road_nodes DataFrame.
There’s no point in calculating the distances between a parking location and all the points in the road_graph_data so we subset the list of nodes to those that are within ~2000 ft from the parking node being processed.
Now we can find the intersection point.
Since we are processing nodes that are within 2000 ft we need to check if the point lays between the two nodes. We do this by checking the sum of the haversine distance to each point from the intersection is less than or equal to the actual length between these two nodes.
To find the best fit we select the point with the smallest distance from the parking spot and add the node to the list of nodes.
Finally, we also add the edge that links the parking location and the found intersection point.
Processing ~1500 parking meter locations took only 3 minutes and 20 seconds (there are more than 127,000 road nodes in King County!) on the NVIDIA Titan RTX.
Did it work?!
Using the same cuGraph approach as we presented in the previous story, we can now find much more reliable way of traversing our graph and finding the nearest parking locations near Space Needle!
