Voronoi diagram
You are encouraged to solve this task according to the task description, using any language you may know.
A wp:Voronoi Diagram is a diagram consisting of a number of sites. Each Voronoi s also has a Voronoi cell consisting of all points closest to s.
Python
This implementation takes in a list of points, each point being a tuple and returns a dictionary consisting of all the points at a given site.
<lang python> def generate_voronoi(points): minx, miny = points[0] maxx, maxy = points[0] for x, y in points: ## Find the minimum x and minimum y if x < minx: minx = x if x > maxx: maxx = x if y < miny: miny = y if y > maxy: maxy = y nx = [] ny = [] voronoi = {} hypot = math.hypot cell_num = 0 for x, y in points: voronoi[cell_num] = [] nx.append(x) ny.append(y) cell_num += 1 for y in range(miny-height_padding, maxy): for x in range(minx-width_padding, maxx): dmin = hypot(maxx+-1, maxy-1) j = -1 for i in range(cell_num): d = hypot(nx[i]-x, ny[i]-y) if d < dmin: dmin = d j = i voronoi[j].append((x, y)) return voronoi </lang>
Sample Output:
voronoi = generate_voronoi([(0, 0), (5, 5)]) voronoi[0] : (0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (0, 2), (1, 2), (2, 2), (3, 2), (0, 3), (1, 3), (2, 3), (0, 4), (1, 4), (0, 5) // Points closest to (0, 0) voronoi[1] : (5, 1), (4, 2), (5, 2), (3, 3), (4, 3), (5, 3), (2, 4), (3, 4), (4, 4), (5, 4), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5) // Points closest to (5, 5)