I have a collection of points, and I need to generate shapes around these points.

Let's assume that these points are locations of offices and that the shapes are the 'area of responsibility' around the offices. The area of responsibility is defined by airline distance. This can be easily solved by a buffer function.

But now: It is possible that offices are very close to each other and that the areas of responsibility of two or more offices overlap. In this case, only one (the closest) office is responsible.

Is it possible to generate such shapes without iterating over the positions in the overlapped area?


You don't say which software you're using, but the thing you're looking for is Voronoi polygons (AKA Theissen polygons). This is the set of polygons such that any point within a polygon is nearest to its seed point.

You will find that the polygons tessellate, which might be a problem if your offices have a maximum distance of responsibility. If that is the case, one way is to generate buffer polygons around each building, and take the intersection of that buffer with the Voronoi polygon associated with the building.

| improve this answer | |
  • Yes, great, exactly what I'm looking for. I'm using PostGIS, and QuantumGIS. I'm going to check if these tools support Voronoi polygons. – ABX Apr 10 '12 at 13:50
  • 4
    (+1) For some animated illustrations of this, see mathematica.stackexchange.com/questions/3963. – whuber Apr 10 '12 at 15:54

I was having a similar problem but I wanted to create voronoi buffers from polygons not points. The Spatial Analyst Cost Allocation in ArcGIS solved my problem.

Got the idea from here: http://forums.esri.com/Thread.asp?c=93&f=982&t=144963

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.