ie. a combination of Voronoi polygons with isochrones, so that the Voronoi polygons are based on driving distance instead of Euclidean distance. Is there a name or a described method for this?

  • 1
    I don't know any exact name for this, but an exact analogy to Euclidean distance isn't always possible for driving routes. Consider one-ways roads: they cause some street locations to be such that distances don't adhere to the triangle inequality. Commented Feb 8, 2011 at 18:38

2 Answers 2


I don't think there is a name for this exact technique, but hopefully some of what follows will provide some options:

In general, there are many interpolation techniques for moving between a point representation and a continuous surface, such the TIN interpolation method underdark has illustrated. The continuous surface could then be classified by value to produce the isochrones.

On a network such as roads, if the distances along the edges are known, you can compute the distances to any location using something like the A* algorithm -- again this data could be partitioned by distance into isochrones.

  • Interpolation off-road is meaningless unless you explicitly permit off-road travel. In that case, the correct answer is not an interpolation per se, but is computed with a cost-distance procedure (of which the A* algorithm is an example) for off road travel, not for travel along the road "edges." Neither IDW nor kriging are appropriate here.
    – whuber
    Commented Feb 19, 2011 at 4:07
  • Interpolation off-road can just be there for presentation purposes. Imagine a city map which indicates to which hospital you should go based on driving time.
    – johanvdw
    Commented Feb 19, 2011 at 7:54
  • (anyway in that case IDW or kriging are bad techniques. Better use voronoi polygons to just connect the same travel times)
    – johanvdw
    Commented Feb 19, 2011 at 11:03
  • 1
    I've updated the methods to mention using TINs for interpolation (keep everything in vector). As this approach is intended as a visualization technique to give an overall picture of movement time, not a point-to-point true cost, I think IDW or similar is fine: it isn't accurate in a scientific sense, but that is often not the intention of maps of this nature (e.g. mysociety.org/2007/more-travel-maps, definitions-marketing.com/IMG/jpg/courbe-isochrone.jpg).
    – scw
    Commented Feb 25, 2011 at 7:48
  • 1
    I use the phrase interpolation to be consistent with the software, but I agree that this is really a cartographic generalization approach: another area where the multifaceted uses of GIS ranging from the artistic to the scientific can cause conceptual mismatches.
    – scw
    Commented Feb 25, 2011 at 7:50

I could see two ways of going about this problem. One is pretty straightforward. The other requires a great deal of supporting data.

The straightforward algorithm would rely on convex hulls rather than voronoi polygons. Construct the convex hull of the vector endpoints and vertices for the street segments that fall inside your drive time cutoffs. Then, use this convex hull to select the connected networks inside your convex hull which are outside your drive time cutoff. These are the pockets inside your general area that are not reachable in the drive time (e.g. one way cutoffs, complex interior subdivisions, etc). Construct a convex hull for each of these isolated pocket networks and use these hulls as interior rings to your original convex hull.

Note that this particular algorithm gets a lot more complex if you are using true curves, since a true curve could fall outside your vertex constructed convex hull.

For the supporting data algorithm, you use a land partitioning. Parcels are the most obvious land partitioning, but not necessarily effective for every scenario. Based on your solution network, each parcel is either determined to be accessed from or inaccessible to the solution network. If the parcel is accessible, you place it inside the catchment area. If not, outside. On an area with developed planimetrics this can be pretty easy; just include driveways and private roads as components of the road network. If the partition touches the solution network, it is accessible. One of the difficulties here ensuring that all potentially accessible partitions touch the network. For example, if you have an interior common ground parcel in a subdivision, you need to merge that in some way with a parcel or parcels that touch the network. But you might have regions, like interior trails in a large park, that are not accessible at all that are simply left not touching the network. Like I said, a lot of supporting data, but a very effective algorithm once you have the data.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.