;;;;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 @#$#@#$#@ GRAPHICS-WINDOW 161 10 444 314 45 45 3.0 1 10 1 1 1 0 0 0 1 -45 45 -45 45 CC-WINDOW 5 328 453 423 Command Center 0 BUTTON 12 50 75 83 NIL setup NIL 1 T OBSERVER NIL NIL SLIDER 11 14 103 47 points points 3 20 11 1 1 NIL BUTTON 12 86 75 119 NIL go T 1 T OBSERVER NIL NIL SWITCH 12 165 150 198 move-points? move-points? 0 1 -1000 SWITCH 12 122 151 155 fuzzy-borders? fuzzy-borders? 1 1 -1000 BUTTON 82 50 140 83 NIL setup-grid NIL 1 T OBSERVER NIL NIL @#$#@#$#@ 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'