Voronoi diagram
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.
You are encouraged to solve this task according to the task description, using any language you may know.
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)