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