Created with
NetLogo version NetLogo 3.1.3

Running with NetLogoLite.jar version 314.

A hack to display a voronoi diagram for a set of points. Not super fast, patch-based.

Uses integer placement of the points and distance calculations to cheat faster performance.

Does not provide any of the cool extras other algorithms provide, such as the locations of the vertexes of the voronoi cells.

A set of points is created.

Each patch looks at every point to find the point nearest the patch.

The "cell" is identified by the point--patches with the same nearest point are in the same cell.

Patches adjacent to patches in a different cell are boundary patches.

Patches adjacent to two or more other cells are vertex patches.

The patches are colored to match their cell/nearest point.

Here is a more mathematical alogorithm to construct a diagram.

i=1,...,N-1

j=i+1,...,N

Consider a bisector of p(i) and p(j)

k=1,...,N except for i and j

Consider a bisector of p(i) and p(k)

Calculate the points of intersection of bisector(i,j) and bisector(i,k)

next k

Add the points x=0 and x=(the width of screen) of the bisector (i,j) into the points of intersections

Sort the points of intersections in terms of x coordinates

k=1,...,the number of intervals of the points of intersections

Let c be a midpoint of the interval of the points of intersection.

Let d be d(c,p(i))

h=1,...,N except for i and j

Let d' be d(c,p(h))

If d'<d then shout (Out!)

next h

If we did not shout, then draw the interval of the points of intersection

next k

next j

next i

References

Fortune, 1987;

Guibas and Stolfi, 1985;

Wikipedia;

Wolfram MathWorld;

Assorted Web Pages (specific cites needed!);

NetLogo Version: NetLogo 3.1.3

;;;;SUMMARY ;; Voronoi Cells ;;;; COPYRIGHT ;; Copyright © 2007 James P. Steiner ;; ;; ;; patches-own [ nearest ] turtles-own [ c-color ;; color for cells b-color ;; color for boundary cells v-color ;; color for vertex cells ] ;; startup always runs once when model loads to startup setup end to setup ;; random points ca ;; make some random points cct points [ setxy random-pxcor random-pycor initialize-point ] ;; display the intial diagram voronoi display end to setup-grid ;; grid of points ca ;; create a grid of points let gap int (world-width / 5) ask patches with [ pxcor mod gap = 0 and pycor mod gap = 0 ] [ sprout 1 [ initialize-point ] ] voronoi display end to go no-display if move-points? ;; a switch in the interface [ ;; turtles simply take a step forward (to the next patch center) ;; when at a world edge, turtles turn somewhat randomly ask turtles [ ifelse can-move? 1.5 and not any? (turtles-on (patch-ahead 1.5)) with [ self != myself ] [ jump 1.4 setxy pxcor pycor ] ;; placing turtles on patch centers (ie int coordinates) ;; makes the model much faster! [ rt 90 + 45 * random 5 ] ] ] ;; update the diagram voronoi display end to voronoi ifelse fuzzy-borders? [ ;; use the int of the distance, makes some borders ;; tend to dither--looks neat, probably not useful ask patches [ set nearest min-one-of turtles [ int distance myself ] ] ] [ ;; exact distances used, ;; but since turtles are on patch centers ;; ties may occur, and are settled randomly. ;; this produces interesting (but possibly undesired) results ;; also, nothing to keep two points from overlapping exactly ;; so their combined area is dithered randomly between them ask patches [ set nearest min-one-of turtles [ distance myself ] ] ] ;; patches adjacent to patches with different nearest points ;; are on a boundary. ;; patches adjacent to more than one different cell ;; are near a vertex ;ask patches with [ any? neighbors with [ nearest != nearest-of myself ] ] ;[ set boundary? true ; set vertex? ( 3 <= length (remove-duplicates (values-from neighbors [ nearest ]))) ;] ;; color the patches by cell, and whether on a boundary or vertex ask patches [ set pcolor c-color-of nearest ] end to initialize-point ;; defined the essential initial settings for a point set color 18 + who * 10 set heading random 360 set size 2 set shape "x" set c-color color - 3 set b-color color - 1 set v-color color + 1 end

voronoi-diagram_minimal

View or download the complete model file (to download: right-click, save-link-as):

-- Download voronoi-diagram_minimal --