Voronoi - Emergent

No preview image

1 collaborator

Uri Wilensky (Author)

WHAT IS IT?

This model draws a Voronoi diagram by using turtles to define the boundaries between polygons that denote the region that is closest to a given point. Voronoi diagrams resemble many phenomena in the world including cells, forest canopies, territories of animals, fur and shell patterns, crystal growth and grain growth, cracks in dried mud and other geological phenomena, road networks, and so on. Voronoi diagrams are useful in computer graphics, vision and path planning for robots, marketing, and other applications.

HOW IT WORKS

At setup, a small number of seeds (circles) and a large number of turtles are randomly placed in the view. When the go button is clicked, the turtles begin to move. While they move they keep track of the seeds around them, and when they have two or more seeds that are equidistant to them, and are the closest seeds to them, they stop moving. As a result of this behavior, the turtles stop moving along the borders between seed regions, resulting in a Voronoi diagram.

This is one of two voronoi diagram models in the models library, but the two are quite different. In the other model, the voronoi diagram is created by having each patch look to its nearest seed to decide what color to be, which produces the colored polygons. In this model on the other hand, the agents move around trying to locate positions where they do not have a single nearest seed. In other words, they are trying to locate a point that is not part of a polygon at all. In trying to find these locations, the turtles collectively end up defining the boundaries of the polygons in the diagram. The polygons emerge from the lines created by the turtles when they stop moving.

HOW TO USE IT

Use the NUM-SEEDS slider to choose how many points you want and the NUM-TURTLES slider to determine how many turtles to add to the model, then press SETUP. The model will place seeds and turtles randomly in the view. When you press the GO button, you will see the turtles start to move around the screen, stopping when they are equidistant from their closest seeds. As more turtles come to rest, a Voronoi diagram emerges.

The GO-MODES chooser lets you define how the turtles will move. The RANDOM mode will have the turtles move based on the random direction they were facing at setup time. The ORGANIZED mode will have each turtle face the seed that it is closest to, then move away from it. In both modes, the turtles follow the same rules for deciding when to stop moving as discussed above in the How It Works section.

Keeping the GO button pressed, you can interact with the model by selecting an option from the MOUSE-ACTIONS chooser, and clicking the DO MOUSE ACTION button. There are four mouse actions defined for the model. The ADD-NEW-SEEDs option allows you to add new seeds to the model. The REMOVE-SEEDS option lets you click on existing seeds to remove them. The MOVE-SEEDS option lets you click and drag seeds around the screen. Finally, the ADD-TURTLES option allows you to add more turtles to the model. As you interact with the model, you will see the polygons redraw based on the changing seed arrangement.

If you unclick the GO button, you can still make changes to the seeds. When you press the GO button again, you will see the turtles begin to move again, creating a new Voronoi diagram based around the changes you have made.

THINGS TO NOTICE

The lines that are formed by the turtles between the seeds are exactly midway between them.

How many sides do the polygons formed by the turtles typically have? (You may want to ignore the polygons around the edges.)

What is the difference between the RANDOM and ORGANIZED turtle behaviors? Do the different behaviors result in different diagrams?

Looking at the code tab, the go-random and go-organized procedures control the turtle behavior. Both of these methods are very short, the RANDOM go-mode only has 3 lines! Can you figure out what these 3 lines are doing? Are you surprised that so few lines can produce such a complicated diagram?

THINGS TO TRY

Experiment with the effect of moving the points around, adding points, and removing points.

The turtles form polygons around the seeds - can you arrange the seeds to make the turtles form a triangle? How about a square? Or an octagon?

What happens if you arrange the seeds in a grid? Or a single straight line?

Does it always take the same amount of time for the turtles to find the boundary between points? Can you arrange the seeds in such a way that it takes the turtles a long time to find a place where they are equidistant from two points?

EXTENDING THE MODEL

Currently, the seeds and turtles are randomly distributed. By systematically placing the seeds, you can create pattern with the turtles. Add buttons that arrange the seeds in patterns that create specific shapes in the model.

You could imagine systems where there could be different size seeds, and turtles would have a strong or weaker attraction to the seeds based on the seeds size. Implement a model that has variable size seeds and replaces the distance calculation with an attraction calculation based on the seeds size. How does this change the resulting Voronoi diagrams?

NETLOGO FEATURES

The core procedures for the turtles are go-random and go-organized. The only difference between the two is that in go organized, we added two lines to make the turtles face the closest seed. These procedures use the min-one-of and distance reporters to find the nearest seed in a very succinct way.

The mouse-down?, mouse-xcor, and mouse-ycor primitives are used so the user can interact with the model.

The go method uses the run command to decide which behavior the turtles should follow by reading the go-mode chooser. Similarly, we use the run command to decide which mouse action to execute. This command allows one button (the DO MOUSE ACTION button) to produce different behaviors based on the value of the MOUSE-ACTION chooser.

tick-advance is used in place of tick to allow the go-mode methods to be executed multiple times per whole tick. This results in the view updating less frequently giving the turtles the appearance of moving faster.

We use the in-radius command to figure out if any of the seeds are too close together.

RELATED MODELS

Voronoi
MaterialSim Grain Growth
Fur
Honeycomb
Scatter
Hotelling's Law

CREDITS AND REFERENCES

For more information on Voronoi diagrams, see http://en.wikipedia.org/wiki/Voronoi. (There are also many other sites on this topic on the web.)

This model was inspired by a Processing implementation of a Voronoi diagram, available here: http://www.openprocessing.org/sketch/7571

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

Weintrop, D. and Wilensky, U. (2013). NetLogo Voronoi - Emergent model. http://ccl.northwestern.edu/netlogo/models/Voronoi-Emergent. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

breed [seeds seed]         ;; these are the circles in the middle of the polygons
breed [movers mover]       ;; these are the turtles that move around, forming the edges

to setup
  clear-all
  
  ;; create the seeds and randomly distribute them
  create-seeds num-seeds [
    set shape "circle"
    set size 2
    setxy random-xcor random-ycor
  ]
  
  ;; create the turtles and randomly distribute them
  create-movers num-turtles [
    set size .75
    setxy random-xcor random-ycor
  ]

  reset-ticks
end 

;;;;;;;;;;;;;;;;;;;;;
;;; Go procedures ;;;
;;;;;;;;;;;;;;;;;;;;;

to go
  separate-seeds
  run (word "go-" go-mode)    
  ;; the following line is used in place of tick to make the turtles
  ;; move further in each tick, resulting in them appearing to move faster  
  tick-advance .2
end 

;; check to make sure that the seeds are not too close together, as this interferes
;; with the emergent voronoi pattern

to separate-seeds
  ask seeds [
    ask other seeds in-radius 2 [
      face myself
      rt 180
      fd 1
    ]
  ]
end 

;; report the seeds that are the closest to the turtle
;; (rounding the distance to the nearest tenth)

to-report nearby-seeds ;; turtle reporter
  report seeds with-min [ precision (distance myself) 1 ]
end 

;; have the turtles move, but not change their heading based on the nearest seed 

to go-random
  ask movers [
    ;; the turtle first finds the seeds that are the closest to it 
    ;; (rounding the distance to the nearest tenth), next, it checks to see how many 
    ;; seeds are closest. If there is only one, the turtle then moves forward.
    ;; If there is more than one, it stops as it has found a midpoint between seeds.
    if count nearby-seeds = 1 [ fd .04 ]
    rt .5 - random-float 1
   ]
end 

;; have the turtles move, changing their heading based on the nearest seed

to go-organized
  ask movers [
    ;; the turtle first finds the seeds that are the closest to it 
    ;; (rounding the distance to the nearest tenth)
    let nearby nearby-seeds

    ;; If the turtle only has only one closest seeds, it faces that seed and moves backward
    if count nearby = 1 [
      face one-of nearby
      bk .04
      ;; Here we ask the turtle to slightly change its direction to introduce some
      ;;   noise into the turtle's movement    
      rt .5 - random-float 1
    ]
  ]
end 

;;;;;;;;;;;;;;;;;;;;;;;;
;;; Mouse procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;

to do-mouse-action
  run mouse-action
end 

to add-new-seed
  while [mouse-down?] [
    wait .1
    ;; create the new seed when the users releases the mouse button
    if not mouse-down? [
      create-seeds 1 [
        set shape "circle"
        set size 2
        setxy mouse-xcor mouse-ycor
      ]
      display
    ]
  ]
end 

to remove-seeds
  if mouse-down? [
    let candidate min-one-of seeds [distancexy mouse-xcor mouse-ycor]
    if [distancexy mouse-xcor mouse-ycor] of candidate < 1 [
      ask candidate [die]
      display
    ]
  ]
end 

to move-seeds
   if mouse-down? [
    let candidate min-one-of seeds [distancexy mouse-xcor mouse-ycor]
    if [distancexy mouse-xcor mouse-ycor] of candidate < 1 [
      while [mouse-down?] [
        go
        ask candidate [ setxy mouse-xcor mouse-ycor ]
      ]
    ]
  ]
end 

to add-turtles
  if mouse-down? [
    create-movers 1 [
      set size .75  
      setxy mouse-xcor mouse-ycor
    ]
    go
  ]
end 


; Copyright 2013 Uri Wilensky.
; See Info tab for full copyright and license.

There is only one version of this model, created over 11 years ago by Uri Wilensky.

Attached files

No files

This model does not have any ancestors.

This model does not have any descendants.

NetLogo