Dividing up a map into polygon regions based on a list of single point coordinates

Question

I'm trying to divide up a city map into polygon regions based on a list of single point coordinates.

The idea is that a polygon region would extend outwards from a single point in all directions until it bordered with polygon regions extending out from nearby / adjacent points. I don't want to use a fixed radius because I want the end result to be complete coverage of the map. So the regions will be irregularly shapes and sized, extending their "territory" as far as possible before bumping up against other territories or the map boundary.

Does anyone know of an algorithm, library or program that can generate such a list of polygons given a list of single point coordinates and a map boundary?

Answer 1

Perhaps you want delaunay-triangulation or a voronoi diagram.

Example page from JSTS

• delaunay triangulation
• voronoi diagram