Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have in my possession four sets of shapefiles:
1. Locations (points), around 1000
2. Roads (lines), each road has a speed attribute
3. Terrain (polygons), each zone also has a speed attribute
4. Rivers (lines), each river has a crossing delay time attribute

How can I construct a Voronoi diagram for my locationg using travel time as a distance metric? I could've used pgRouting if I had roads only, but I am not sure how to approach different off-road terrain and rivers. I'm willing to code this, but I've spent enough time trying to come up with an algorithm, but to no avail.

My current plan is to dump it all into a sufficiently large raster and create 1000 distance maps out of it, then use them to calculate the Voronoi cells, but I have a suspicion that a sufficiently large raster will take too long to process. Is there a better vector-based algorithm?

share|improve this question
I describe an extremely efficient solution in a recently awarded patent viewable at…. – whuber Jun 24 '13 at 16:43
@whuber Oh, interesting. It seems you're also rasterizing the region. I am not sure if I can use a patented algorithm, though. – Alexey Jun 25 '13 at 9:55
@whuber do you have a paper on that patent? – dassouki Jun 25 '13 at 13:25
@dassouki That's not how patents work :-(. You have to demonstrate priority and exclusiveness, which means you can't publish beforehand. I do have presentation slides, though: look for the "raster-vector hybrids" section at the end (part 4, pp 37-45 inclusive). To fully appreciate slide 38 ("Why not put the two together?"), though, you should look at the first three parts :-). – whuber Jun 25 '13 at 13:35
@whuber thanks! – dassouki Jun 25 '13 at 13:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.