Voronoi diagram

Voronoi diagram is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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>

1. include <stdlib.h>
2. include <string.h>

1. 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; }

1. 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; }

1. 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); }

1. define for_i for (i = 0; i < size_y; i++)
2. 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); }

1. 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

Euclidean

Voronoi Diagram in PureBasic

<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>

Taxicab

Voronoi Diagram in PureBasic

<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 = 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.f, dt.f, dx, dy
 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())
         dx = x-a(i)\x
         dy = y-a(i)\y
         dt = Sign(dx)*dx + Sign(dy)*dy
         If dt >= dist :Continue: EndIf
         dist = dt
         Plot(x,y,a(i)\FillColour)
       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.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:

Voronoi Diagram in Python

Tcl

Library: Tk

<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}

   }

}

1. Generate a 600x400 Voronoi diagram with 60 random points

image create photo demo -width 600 -height 400 pack [label .l -image demo]

1. To display while generating, uncomment this line and the other one so commented
2. update

voronoi demo 60</lang>