Behind the curbs: Building the curb map
We’ve talked before about how we took pictures of all the parking signs in San Francisco, but that’s only the beginning. Since we launched the SF Curb Explorer tool, we’ve been getting some questions about how we figured out where the curbs in San Francisco actually are. Sounds easy, right? It turns out that there’s some neat geometry and a little bit of map manipulation under the hood. Read on to find out how we made it all work.
Finding the Streets
The first thing we needed was a map of all the streets in San Francisco. In some cities, we use maps provided by the city government, but in San Francisco we went to OpenStreetMap, an open-source, collaboratively-produced map of the world. While you might have seen OpenStreetMap’s data before in an app, or used it as a base layer through services like Carto or Mapbox, what drew us to OSM wasn’t map tiles but the underlying data. What we wanted was a network representation of a city: a map that told us not just where the streets were but where they connected. This is important not just for naming curbs (for instance, to say that a parking spot is on Van Ness between Mission and Market, you need to know that the streets intersect!) but also for figuring out where they start and end.
OpenStreetMap is made up of “nodes” (points on the surface of the earth) which are combined into “ways” (lists of points). Roads are made up of ways, but these don’t always start and end where you want them to. In the example below, you can see a way, highlighted in red, that ends right in the middle of a block! So the very first thing we do is take OpenStreetMap’s ways and combine them into longer units we call “roadways”. A roadway is a continuous street with the same name for its entire length. Where two or more roadways meet at a node, we create an “intersection”. The goal here is for every complete block to at least be part of the same roadway. Otherwise, we might stop collecting parking regulations in the middle of a block, which would lead to confusion and even inaccurate regulations.
From Streets to Curbs
Now that we’ve glued ways together into roadways, we cut those roadways up again, this time into curb faces: continuous stretches of curb from one intersection to the next. In the Curbs API, every curb face gets its own ID, and you can use these IDs to query just the regulations on a single curb.
Not all roadways get curb faces — we want to ignore roads like highway on-ramps and pedestrian-only paths where you can’t possibly park a car or even drop someone off — but the roadways that do get curb faces get two sets, one on each side. A road with a median will be made up of two roadways, one on each side of the median, and thus gets four curbs. This is important since, as the Curb Explorer reveals, sometimes you are allowed to park along medians.
OpenStreetMap represents streets by their centerlines: as you can see in the example above, we know where the middle of a road is, but not where its edges are. To find a road’s edges, we have to move our curb face lines from the center of the street out to the edge, based on an estimate of the width of the road. To make life easier, we also give each curb a direction. The “start” and “end” of a curb are always oriented so that the curb is to the right of its corresponding road as you go from start to end.
We’re not done yet: centerlines are in fact longer than curbs. While they meet in the middle of the intersection, curbs meet at the edges. So, we have to chop off any part of the curb that’s sticking into the intersection. This makes some curbs go away entirely, if they represent segments of a roadway that are completely within an intersection. It turns out it’s easy for a human to see this visually, but it’s another thing entirely to teach it to a computer.
Below is pseudocode for how we do this in practice.
for each intersection i:
for each street s meeting at i:
let heading[s] be the compass heading of s as it enters i
for each street s in ascending order of heading[s]:
let s* be the next street in heading order
(wrapping around at the end of the list)
let c_r be the curb face of s that ends at i
let c_l be the curb face of s* that starts at i
compute p, the intersection point of c_r and c_l
compute ds[c_l], the distance along l from where it starts
until you hit p
compute de[c_r], the distance along r from where it starts
(remember that’s not at this intersection!)
until you hit p
for each curb face c:
trim c so it starts at ds[c] and ends at de[c]
(by now these should both be defined for every curb face)To help understand this algorithm, see if you can prove these two things to yourself:
- The right-hand sides of two streets can never meet at an intersection;
- By processing each curb at every intersection, you end up handling every curb exactly twice, once as a “right-hand curb” and once as a “left-hand curb”.
We’ve found that this method works well for producing geographically accurate curb locations, even with complicated intersection geometries. Try querying our curbs API to see how they line up — you can try Market and Octavia (latitude=37.771929&longitude=-122.423434) to see a particularly interesting example.
Epilogue: Linear Referencing
Now that we know where all the curbs are, we attach our surveyed information to them and compute regulations. We store all of our regulation data as linear references along curbs: rather than keep lat/lng coordinates for each sign, we say, “this sign is 20 feet past Mission on the right-hand side of Valencia” (for instance). This way, all the geometry stays in the underlying curb map, and we can process every individual curb’s regulations using only one dimension.
We’re happy to see linear referencing increasingly become a standard way of attaching data to street maps, especially because it can help take data from one base map and put it onto another — -but that’s a topic for another day. In the meantime, we’d love to hear about your experience with the curbs API! Chat with our team on coord.co or email me at jacob@coord.co with any questions or feedback.
