0

I have a list of coordinate points that are already clustered. Each point is available to me as a row in a csv file, with one of the fields being the "zone id": the ID of the cluster to which a point belongs. I was wondering if there is a way, given the latitude, longitude and zone ID of each point, to draw polygons similar to Voronoi cells, such that:

  • each cluster is entirely contained within a polygon
  • each polygon contains points belonging to only one cluster
  • the union of the polygons is contiguous polygon that contains all the points. No holes: the polygons must border each other except at the edges. A fun extension would be to supply the "holes" (water bodies, for example) as part of the input.

I realise the problem is very abstract and could be very resource intensive, but I am curious to hear of any approaches. I am open to solutions using a variety or combination of tools, such as GIS software, Python, R, etc. I am also open to implementations that would be integrated into the clustering process.

Ayman
  • 1
  • 1
  • One way would be to calculate the Voronoi diagram from all points and merge the cells of those points that belong to the same zone. – Nico Schertler Jun 23 '18 at 12:54
  • Could you elaborate or give me a link to explain how that could be done? – Ayman Jun 24 '18 at 14:41
  • Take a look at [this question](https://stackoverflow.com/questions/545870/algorithm-to-compute-a-voronoi-diagram-on-a-sphere) for example. – Nico Schertler Jun 24 '18 at 18:47
  • But wouldn't this create cells that contain points from different zones? – Ayman Jun 25 '18 at 13:32
  • The initial Voronoi diagram will have cells with a single point. And then you explicitly merge cells. If you merge correctly, there will never be cells with points from different zones. – Nico Schertler Jun 25 '18 at 19:59

0 Answers0