Voronoi diagram: Difference between revisions
m minor rewording |
m whitespace/formatting |
||
Line 1: | Line 1: | ||
{{Draft task}} |
{{Draft task}} |
||
A [[wp:Voronoi Diagram|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''. |
A [[wp:Voronoi Diagram|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''. |
||
Line 8: | Line 7: | ||
[[File:voronoi-C.png|center|300px]] |
[[File:voronoi-C.png|center|300px]] |
||
C code drawing a color map of a set of Voronoi sites. Image is in PNM P6, written to stdout. Run as <code>a.out > stuff.pnm</code>. |
C code drawing a color map of a set of Voronoi sites. Image is in PNM P6, written to stdout. Run as <code>a.out > stuff.pnm</code>. |
||
<lang |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 75: | Line 74: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|Python}}== |
=={{header|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. |
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> |
|||
⚫ | |||
minx, miny = points[0] |
minx, miny = points[0] |
||
maxx, maxy = points[0] |
maxx, maxy = points[0] |
||
Line 115: | Line 112: | ||
return voronoi </lang> |
return voronoi </lang> |
||
=== Sample Output: === |
=== Sample Output: === |
||
voronoi = generate_voronoi([(0, 0), (5, 5)]) |
<lang python>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[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) < |
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) </lang> |
Revision as of 08:31, 19 July 2011
A 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.
The task is to demonstrate how to generate and display Voroni Diagram.
C
C code drawing a color map of a set of Voronoi sites. Image is in PNM P6, written to stdout. Run as a.out > stuff.pnm
.
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- define N_SITES 150
double site[N_SITES][2]; unsigned char rgb[N_SITES][3];
int size_x = 640, size_y = 480;
inline double sq2(double x, double y) { return x * x + y * y; }
void gen_map() { int i, j, k, nearest = 0; unsigned char *ptr, *buf, color; double dist, d;
ptr = buf = malloc(3 * size_x * size_y); for (i = 0; i < size_y; i++) { for (j = 0; j < size_x; j++, ptr += 3) { dist = 1e100; for (k = 0; k < N_SITES; k++) { d = sq2(i - site[k][1], j - site[k][0]); if (d >= dist) continue; dist = d; nearest = k; } memcpy(ptr, rgb[nearest], 3); } }
/* draw sites */ for (k = 0; k < N_SITES; k++) { color = (rgb[k][0]*.25 + rgb[k][1]*.6 + rgb[k][2]*.15 > 80) ? 0 : 255;
for (i = site[k][1] - 1; i <= site[k][1] + 1; i++) { if (i < 0 || i >= size_y) continue; for (j = site[k][0] - 1; j <= site[k][0] + 1; j++) { if (j < 0 || j >= size_x) continue; ptr = buf + 3 * (i * size_x + j); ptr[0] = ptr[1] = ptr[2] = color; } } }
printf("P6\n%d %d\n255\n", size_x, size_y); fflush(stdout); fwrite(buf, size_y * size_x * 3, 1, stdout); }
int main() { int i; for (i = 0; i < N_SITES; i++) { site[i][0] = (double)rand() / RAND_MAX * size_x; site[i][1] = (double)rand() / RAND_MAX * size_y; rgb[i][0] = (double)rand() / RAND_MAX * 256; rgb[i][1] = (double)rand() / RAND_MAX * 256; rgb[i][2] = (double)rand() / RAND_MAX * 256; } gen_map(); return 0; }</lang>
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:
<lang python>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) </lang>