A system accesses a three-dimensional map of a geographic region and generates a two-dimensional projection of the road based on the three-dimensional map. The two-dimensional projection comprises a plurality of points along the road and each point is assigned a score measuring a navigability of the point. Based on the navigability score of each point and history of vehicle positions on the road, the system identifies a plurality of navigable points on the two-dimensional projection of the road. Based on the plurality of navigable points, the system determines a navigable surface corresponding to a physical area over which a vehicle may safely navigate and navigable surface boundaries surrounding that area. The navigable surface area and boundaries on the two-dimensional projection are converted into a three-dimensional representation, which the system uses to generate an updated three-dimensional map of the geographic region.