A map region is analyzed by a mobile device or by a server. The map region including one or more road segments is identified. Multiple points are selected from the map region. From each of the selected points, a distance is measured from the selected point to a nearest road segment of the one or more road segments. A road density value is determined from the distances. The road density value may be based on an average of the distances. In one example, the road density value is an inverse of the average of the distances. The road density value may be a parameter for matching subsequent probe points to a road segment in the map region.