voronoi-diagram_minimal


Information

Created with NetLogo version NetLogo 3.1.3
Running with NetLogoLite.jar version 314.



WHAT IS IT?


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

HOW IT WORKS


--------
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!);

Procedures

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
      

                    


Download Link

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