Voronoi diagram
A Voronoi diagram is a diagram consisting of a number of sites. Each Voronoi site 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>
Icon and Unicon
The sample images to the right show the screen size, number of sites, and metric used in the title bar.
<lang Icon>link graphics,printf,strings
record site(x,y,colour) # site data position and colour invocable all # needed for string metrics
procedure main(A) # voronoi
&window := open("Voronoi","g","bg=black") | stop("Unable to open window")
WAttrib("canvas=hidden") # figure out maximal size width & height WAttrib(sprintf("size=%d,%d",WAttrib("displaywidth"),WAttrib("displayheight"))) WAttrib("canvas=maximal") height := WAttrib("height") width := WAttrib("width")
metrics := ["hypot","taxi","taxi3"] # different metrics
while case a := get(A) of { # command line arguments
"--sites" | "-s" : sites := 0 < integer(a := get(A)) | runerr(205,a) "--height" | "-h" : height := 0 < (height >= integer(a := get(A))) | runerr(205,a) "--width" | "-w" : width := 0 < (width >= integer(a := get(A))) | runerr(205,a) "--metric" | "-m" : metric := ((a := get(A)) == !metrics) | runerr(205,a) "--help" | "-?" : write("Usage:\n voronoi [[--sites|-s] n] ",
"[[--height|-h] pixels] [[--width|-w] pixels]", "[[--metric|-m] metric_procedure]", "[--help|-?]\n\n")
}
/metric := metrics[1] # default to normal /sites := ?(r := integer(.1*width)) + r # sites = random .1 to .2 of width if not given
WAttrib(sprintf("label=Voronoi %dx%d %d %s",width,height,sites,metric)) WAttrib(sprintf("size=%d,%d",width,height))
x := "0123456789abcdef" # hex for random sites (colour) siteL := [] every 1 to sites do # random sites
put(siteL, site(?width,?height,cat("#",?x,?x,?x,?x,?x,?x)))
VoronoiDiagram(width,height,siteL,metric) # Voronoi-ize it WDone() end
procedure hypot(x,y,site) # normal metric return sqrt((x-site.x)^2 + (y-site.y)^2) end
procedure taxi(x,y,site) # "taxi" metric return abs(x-site.x)+abs(y-site.y) end
procedure taxi3(x,y,site) # copied from a commented out version (TCL) return (abs(x-site.x)^3+abs(y-site.y)^3)^(.3) end
procedure VoronoiDiagram(width,height,siteL,metric)
/metric := hypot every y := 1 to height & x := 1 to width do { dist := width+height # anything larger than diagonal every site := !siteL do { if dist < (dt := metric(x,y,site)) then next # skip else if dist >:= dt then Fg(site.colour) # site else Fg("#000000") # unowned DrawPoint(x,y) } }
Fg("Black") every site := !siteL do # mark sites DrawCircle(site.x,site.y,1)
end</lang>
printf.icn provides the printf family graphics.icn provides graphics support strings.icn provides cat
Prolog
Works with SWI-Prolog and XPCE.
3 Voronoi diagrams are given for the same sites, one with the Manhattan distance, one with the Euclidean distance and the last with the Minkowski distance (order 3).
<lang Prolog>:- dynamic pt/6. voronoi :- V is random(20) + 20, retractall(pt(_,_,_,_)), forall(between(1, V, I), ( X is random(390) + 5, Y is random(390) + 5, R is random(65535), G is random(65535), B is random(65535), assertz(pt(I,X,Y, R, G, B)) )), voronoi(manhattan, V), voronoi(euclide, V), voronoi(minkowski_3, V).
voronoi(Distance, V) :- sformat(A, 'Voronoi 400X400 ~w ~w', [V, Distance]), new(D, window(A)), send(D, size, size(400,400)), new(Img, image(@nil, width := 400, height := 400 , kind := pixmap)),
% get the list of the sites
bagof((N, X, Y), R^G^B^pt(N, X, Y, R, G, B), L),
forall(between(0,399, I), forall(between(0,399, J), ( get_nearest_site(V, Distance, I, J, L, S), pt(S, _, _, R, G, B), send(Img, pixel(I, J, colour(@default, R, G, B)))))),
new(Bmp, bitmap(Img)), send(D, display, Bmp, point(0,0)), send(D, open).
% define predicatea foldl (functionnal spirit) foldl([], _Pred, R, R).
foldl([H | T], Pred, Acc, R) :- call(Pred, H, Acc, R1), foldl(T, Pred, R1, R).
% predicate for foldl compare(Distance, XP, YP, (N, X, Y), (D, S), R) :- call(Distance, XP, YP, X, Y, DT), ( DT < D -> R = (DT, N) ; R = (D, S)).
% use of a fake site for the init of foldl get_nearest_site(Distance, I, J, L, S) :- foldl(L, compare(Distance, I, J), (65535, nil), (_, S)).
manhattan(X1, Y1, X2, Y2, D) :- D is abs(X2 - X1) + abs(Y2-Y1).
euclide(X1, Y1, X2, Y2, D) :- D is sqrt((X2 - X1)**2 + (Y2-Y1)**2).
minkowski_3(X1, Y1, X2, Y2, D) :-
D is (abs(X2 - X1)**3 + abs(Y2-Y1)**3)**0.33.
</lang>
PureBasic
Euclidean
![](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 = RGBA(j, k, l, 255) a(i)\FillColour = RGBA(255-j, 255-k, 255-l, 255) Next i ProcedureReturn #True
EndProcedure
Procedure MakeVoronoiDiagram(Array a.VCoo(1),xMax, yMax) ; Euclidean
Protected i, x, y, img, dist.d, dt.d img = CreateImage(#PB_Any, xMax+1, yMax+1) If StartDrawing(ImageOutput(img)) For y=0 To yMax For x=0 To xMax dist = Infinity() For i=0 To ArraySize(a()) dt = SQ2(x-a(i)\x, y-a(i)\y) If dt > dist Continue ElseIf dt < dist dist = dt Plot(x,y,a(i)\FillColour) Else ; 'Owner ship' is unclear, set pixel to transparent. Plot(x,y,RGBA(0, 0, 0, 0)) EndIf Next Next Next For i=0 To ArraySize(a()) Circle(a(i)\x, a(i)\y, 1, a(i)\Colour) 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>
Taxicab
![](http://static.miraheze.org/rosettacodewiki/thumb/5/5d/Voronoi_Diagram_in_PureBasic_%28Taxicab%29.png/320px-Voronoi_Diagram_in_PureBasic_%28Taxicab%29.png)
<lang PureBasic>Structure VCoo
x.i: y.i Colour.i: FillColour.i
EndStructure
Macro RandInt(MAXLIMIT)
Int(MAXLIMIT*(Random(#MAXLONG)/#MAXLONG))
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 = RGBA(j, k, l, 255) a(i)\FillColour = RGBA(255-j, 255-k, 255-l, 255) Next i ProcedureReturn #True
EndProcedure
Procedure MakeVoronoiDiagram(Array a.VCoo(1),xMax, yMax)
Protected i, x, y, img, dist, dt, dx, dy img = CreateImage(#PB_Any, xMax+1, yMax+1, 32) If StartDrawing(ImageOutput(img)) For y=0 To yMax For x=0 To xMax dist = #MAXLONG For i=0 To ArraySize(a()) dx = x-a(i)\x dy = y-a(i)\y dt = Sign(dx)*dx + Sign(dy)*dy If dt > dist ; no update Continue ElseIf dt < dist ; an new 'owner' is found dist = dt Plot(x,y,a(i)\FillColour) Else ; dt = dist Plot(x,y,RGBA(0,0,0,0)) ; no clear 'owner', make the pixel transparent EndIf Next Next Next For i=0 To ArraySize(a()) Circle(a(i)\x, a(i)\y, 1, a(i)\Colour) 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.randrange(imgx)) ny.append(random.randrange(imgy)) nr.append(random.randrange(256)) ng.append(random.randrange(256)) nb.append(random.randrange(256)) 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)
Tcl
<lang tcl>package require Tk proc r to {expr {int(rand()*$to)}}; # Simple helper
proc voronoi {photo pointCount} {
for {set i 0} {$i < $pointCount} {incr i} {
lappend points [r [image width $photo]] [r [image height $photo]]
} foreach {x y} $points {
lappend colors [format "#%02x%02x%02x" [r 256] [r 256] [r 256]]
} set initd [expr {[image width $photo] + [image height $photo]}] for {set i 0} {$i < [image width $photo]} {incr i} {
for {set j 0} {$j < [image height $photo]} {incr j} { set color black set d $initd foreach {x y} $points c $colors { set h [expr {hypot($x-$i,$y-$j)}] ### Other interesting metrics #set h [expr {abs($x-$i)+abs($y-$j)}] #set h [expr {(abs($x-$i)**3+abs($y-$j)**3)**0.3}] if {$d > $h} {set d $h;set color $c} } $photo put $color -to $i $j } # To display while generating, uncomment this line and the other one so commented #if {$i%4==0} {update idletasks}
}
}
- Generate a 600x400 Voronoi diagram with 60 random points
image create photo demo -width 600 -height 400 pack [label .l -image demo]
- To display while generating, uncomment this line and the other one so commented
- update
voronoi demo 60</lang>