Voronoi diagram: Difference between revisions
m (minor grammatical fix) |
(→{{header|C}}: now with anti-aliasing (frivolous, I know)) |
||
Line 22: | Line 22: | ||
} |
} |
||
⚫ | |||
int nearest_site(double x, double y) |
|||
{ |
|||
int k, ret = 0; |
|||
⚫ | |||
for_k { |
|||
d = sq2(x - site[k][0], y - site[k][1]); |
|||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
return ret; |
|||
} |
|||
/* see if a pixel is different from any neighboring ones */ |
|||
int at_edge(int *color, int y, int x) |
|||
{ |
|||
int i, j, c = color[y * size_x + x]; |
|||
⚫ | |||
if (i < 0 || i >= size_y) continue; |
|||
⚫ | |||
if (j < 0 || j >= size_x) continue; |
|||
if (color[i * size_x + j] != c) return 1; |
|||
⚫ | |||
} |
|||
return 0; |
|||
} |
|||
#define AA_RES 4 /* average over 4x4 supersampling grid */ |
|||
void aa_color(unsigned char *pix, int y, int x) |
|||
{ |
|||
int i, j, n; |
|||
double r = 0, g = 0, b = 0, xx, yy; |
|||
⚫ | |||
yy = y + 1. / AA_RES * i + .5; |
|||
for (j = 0; j < AA_RES; j++) { |
|||
xx = x + 1. / AA_RES * j + .5; |
|||
n = nearest_site(xx, yy); |
|||
r += rgb[n][0]; |
|||
g += rgb[n][1]; |
|||
b += rgb[n][2]; |
|||
} |
|||
} |
|||
pix[0] = r / (AA_RES * AA_RES); |
|||
pix[1] = g / (AA_RES * AA_RES); |
|||
pix[2] = b / (AA_RES * AA_RES); |
|||
} |
|||
#define for_i for (i = 0; i < size_y; i++) |
|||
#define for_j for (j = 0; j < size_x; j++) |
|||
void gen_map() |
void gen_map() |
||
{ |
{ |
||
int i, j, k |
int i, j, k; |
||
int *nearest = malloc(sizeof(int) * size_y * size_x); |
|||
unsigned char *ptr, *buf, color; |
unsigned char *ptr, *buf, color; |
||
⚫ | |||
ptr = buf = malloc(3 * size_x * size_y); |
ptr = buf = malloc(3 * size_x * size_y); |
||
for_i for_j nearest[i * size_x + j] = nearest_site(j, i); |
|||
⚫ | |||
⚫ | |||
for_i for_j { |
|||
⚫ | |||
if (!at_edge(nearest, i, j)) |
|||
⚫ | |||
memcpy(ptr, rgb[nearest[i * size_x + j]], 3); |
|||
else /* at edge, do anti-alias rastering */ |
|||
⚫ | |||
aa_color(ptr, i, j); |
|||
ptr += 3; |
|||
⚫ | |||
memcpy(ptr, rgb[nearest], 3); |
|||
⚫ | |||
} |
} |
||
Line 48: | Line 96: | ||
for (i = site[k][1] - 1; i <= site[k][1] + 1; i++) { |
for (i = site[k][1] - 1; i <= site[k][1] + 1; i++) { |
||
if (i < 0 || i >= size_y) continue; |
if (i < 0 || i >= size_y) continue; |
||
for (j = site[k][0] - 1; j <= site[k][0] + 1; j++) { |
for (j = site[k][0] - 1; j <= site[k][0] + 1; j++) { |
||
if (j < 0 || j >= size_x) continue; |
if (j < 0 || j >= size_x) continue; |
||
ptr = buf + 3 * (i * size_x + j); |
ptr = buf + 3 * (i * size_x + j); |
||
ptr[0] = ptr[1] = ptr[2] = color; |
ptr[0] = ptr[1] = ptr[2] = color; |
||
Line 61: | Line 111: | ||
} |
} |
||
#define frand(x) (rand() / (1. + RAND_MAX) * x) |
|||
int main() |
int main() |
||
{ |
{ |
||
int |
int k; |
||
for_k { |
|||
⚫ | |||
site[ |
site[k][0] = frand(size_x); |
||
site[ |
site[k][1] = frand(size_y); |
||
rgb[ |
rgb [k][0] = frand(256); |
||
rgb[ |
rgb [k][1] = frand(256); |
||
rgb[ |
rgb [k][2] = frand(256); |
||
} |
} |
||
gen_map(); |
gen_map(); |
||
return 0; |
return 0; |
Revision as of 14:09, 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 a Voroni diagram.
C
![](http://static.miraheze.org/rosettacodewiki/thumb/6/6b/Voronoi-C.png/300px-Voronoi-C.png)
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; }
- define for_k for (k = 0; k < N_SITES; k++)
int nearest_site(double x, double y) { int k, ret = 0; double d, dist = 0; for_k { d = sq2(x - site[k][0], y - site[k][1]); if (!k || d < dist) { dist = d, ret = k; } } return ret; }
/* see if a pixel is different from any neighboring ones */ int at_edge(int *color, int y, int x) { int i, j, c = color[y * size_x + x]; for (i = y - 1; i <= y + 1; i++) { if (i < 0 || i >= size_y) continue;
for (j = x - 1; j <= x + 1; j++) { if (j < 0 || j >= size_x) continue; if (color[i * size_x + j] != c) return 1; } } return 0; }
- define AA_RES 4 /* average over 4x4 supersampling grid */
void aa_color(unsigned char *pix, int y, int x) { int i, j, n; double r = 0, g = 0, b = 0, xx, yy; for (i = 0; i < AA_RES; i++) { yy = y + 1. / AA_RES * i + .5; for (j = 0; j < AA_RES; j++) { xx = x + 1. / AA_RES * j + .5; n = nearest_site(xx, yy); r += rgb[n][0]; g += rgb[n][1]; b += rgb[n][2]; } } pix[0] = r / (AA_RES * AA_RES); pix[1] = g / (AA_RES * AA_RES); pix[2] = b / (AA_RES * AA_RES); }
- define for_i for (i = 0; i < size_y; i++)
- define for_j for (j = 0; j < size_x; j++)
void gen_map() { int i, j, k; int *nearest = malloc(sizeof(int) * size_y * size_x); unsigned char *ptr, *buf, color;
ptr = buf = malloc(3 * size_x * size_y); for_i for_j nearest[i * size_x + j] = nearest_site(j, i);
for_i for_j { if (!at_edge(nearest, i, j)) memcpy(ptr, rgb[nearest[i * size_x + j]], 3); else /* at edge, do anti-alias rastering */ aa_color(ptr, i, j); ptr += 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); }
- define frand(x) (rand() / (1. + RAND_MAX) * x)
int main() { int k; for_k { site[k][0] = frand(size_x); site[k][1] = frand(size_y); rgb [k][0] = frand(256); rgb [k][1] = frand(256); rgb [k][2] = frand(256); }
gen_map(); return 0; }</lang>
PureBasic
![](http://static.miraheze.org/rosettacodewiki/thumb/6/6d/Voronoi_PureBasic.png/320px-Voronoi_PureBasic.png)
<lang PureBasic>Structure VCoo
x.i: y.i Colour.i: FillColour.i
EndStructure
Macro RandInt(MAXLIMIT)
Int(MAXLIMIT*(Random(#MAXLONG)/#MAXLONG))
EndMacro
Macro SQ2(X, Y)
((X)*(X) + (Y)*(Y))
EndMacro
Procedure GenRandomPoints(Array a.VCoo(1), xMax, yMax, cnt)
Protected i, j, k, l cnt-1 Dim a(cnt) For i=0 To cnt a(i)\x = RandInt(xMax): a(i)\y = RandInt(yMax) j = RandInt(255): k = RandInt(255): l = RandInt(255) a(i)\Colour = RGB(j, k, l) a(i)\FillColour = RGB(255-j, 255-k, 255-l) Next i ProcedureReturn #True
EndProcedure
Procedure MakeVoronoiDiagram(Array a.VCoo(1),xMax, yMax)
Protected i, x, y, img, dist.d, dt.d img = CreateImage(#PB_Any, xMax+1, yMax+1) If StartDrawing(ImageOutput(img)) For x=0 To xMax For y=0 To yMax dist = Infinity() For i=0 To ArraySize(a()) dt = SQ2(x-a(i)\x, y-a(i)\y) If dt >= dist :Continue: EndIf dist = dt If x=a(i)\x And y=a(i)\y Plot(x,y,a(i)\Colour) Else Plot(x,y,a(i)\FillColour) EndIf Next Next Next StopDrawing() EndIf ProcedureReturn img
EndProcedure
- Main code
Define img, x, y, file$ Dim V.VCoo(0) x = 640: y = 480 If Not GenRandomPoints(V(), x, y, 150): End: EndIf img = MakeVoronoiDiagram(V(), x, y) If img And OpenWindow(0, 0, 0, x, y, "Voronoi Diagram in PureBasic", #PB_Window_SystemMenu)
ImageGadget(0, 0, 0, x, y, ImageID(img)) Repeat: Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf
UsePNGImageEncoder() file$ = SaveFileRequester("Save Image?", "Voronoi_Diagram_in_PureBasic.png", "PNG|*.png", 0) If file$ <> ""
SaveImage(img, file$, #PB_ImagePlugin_PNG)
EndIf</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>