Voronoi diagram: Difference between revisions
(→{{header|C}}: now with anti-aliasing (frivolous, I know)) |
(Updated Python code to reflect task) |
||
Line 198: | Line 198: | ||
=={{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> |
<lang python>from PIL import Image |
||
import random |
|||
minx, miny = points[0] |
|||
import math |
|||
maxx, maxy = points[0] |
|||
for x, y in points: |
|||
def generate_voronoi_diagram(width, height, num_cells): |
|||
## Find the minimum x and minimum y |
|||
image = Image.new("RGB", (width, height)) |
|||
if x < minx: |
|||
putpixel = image.putpixel |
|||
minx = x |
|||
imgx, imgy = image.size |
|||
if x > maxx: |
|||
maxx = x |
|||
if y < miny: |
|||
miny = y |
|||
if y > maxy: |
|||
maxy = y |
|||
nx = [] |
nx = [] |
||
ny = [] |
ny = [] |
||
nr = [] |
|||
ng = [] |
|||
nb = [] |
|||
for |
for i in range(num_cells): |
||
nx.append(random.randint(0, imgx-1)) |
|||
voronoi[cell_num] = [] |
|||
ny.append(random.randint(0, imgy-1)) |
|||
nr.append(random.randint(0, 255)) |
|||
ng.append(random.randint(0, 255)) |
|||
cell_num += 1 |
|||
nb.append(random.randint(0, 255)) |
|||
for y in range(miny-height_padding, maxy): |
|||
for y in range(imgy): |
|||
for x in range(imgx): |
|||
dmin = hypot( |
dmin = math.hypot(imgx-1, imgy-1) |
||
j = -1 |
j = -1 |
||
for i in range( |
for i in range(num_cells): |
||
d = hypot(nx[i]-x, ny[i]-y) |
d = math.hypot(nx[i]-x, ny[i]-y) |
||
if d < dmin: |
if d < dmin: |
||
dmin = d |
dmin = d |
||
j = i |
j = i |
||
putpixel((x, y), (nr[j], ng[j], nb[j])) |
|||
image.save("VoronoiDiagram.png", "PNG") |
|||
return voronoi </lang> |
|||
image.show() |
|||
generate_voronoi_diagram(500, 500, 25)</lang> |
|||
=== Sample Output: === |
=== Sample Output: === |
||
[[File:Voronoi_python.png|500px|thumb|center|Voronoi Diagram in Python]] |
|||
<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> |
Revision as of 14:48, 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>from PIL import Image import random import math
def generate_voronoi_diagram(width, height, num_cells): image = Image.new("RGB", (width, height)) putpixel = image.putpixel imgx, imgy = image.size nx = [] ny = [] nr = [] ng = [] nb = [] for i in range(num_cells): nx.append(random.randint(0, imgx-1)) ny.append(random.randint(0, imgy-1)) nr.append(random.randint(0, 255)) ng.append(random.randint(0, 255)) nb.append(random.randint(0, 255)) for y in range(imgy): for x in range(imgx): dmin = math.hypot(imgx-1, imgy-1) j = -1 for i in range(num_cells): d = math.hypot(nx[i]-x, ny[i]-y) if d < dmin: dmin = d j = i putpixel((x, y), (nr[j], ng[j], nb[j])) image.save("VoronoiDiagram.png", "PNG")
image.show()
generate_voronoi_diagram(500, 500, 25)</lang>
Sample Output:
![](http://static.miraheze.org/rosettacodewiki/8/83/Voronoi_python.png)