Emergent voronoi test upload

No preview image

4 collaborators

David Weintrop (Author)

Uri Wilensky (Author)

Arthur Hjorth (Team member)

Bryan Head (Team member)

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, as they move they keep track of the closest seed to their current location. The turtles keep moving until they don't have a single closest seed, but instead have two (or more) seeds that are equally close. When they have more than one closest seed, they stop moving. As a result of this behavior, the turtles stop moving along the borders between seed regions, resulting in a Voronoi diagram.

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 the seeds and turtles randomly in the view. Then press the GO button, and you will see the turtles start to move around the screen, stopping when they are equidistant from two or more 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 set of rules to decide when to stop moving, which are discussed above in the How It Works section.

Keeping the GO button pressed, you can use the four bottom buttons to interact with the model as it runs. The ADD NEW SEED button allows you to add a new seed to the model. The REMOVE SEEDS button lets you click on existing seeds to remove them. The MOVE SEEDS button will let you click and drag seeds around the screen. Finally, the ADD TURTLES button 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 points is 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 straignt 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.

RELATED MODELS

Voronoi
MaterialSim Grain Growth
Fur
Honeycomb
Scatter

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

Comments and Questions

Arthur Hjorth

This is our cool model

n/t

Posted about 11 years ago

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
  reset-ticks
  
  ;; create the nodes 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
  ]
end 

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

to go
  run (word "go-" go-mode)
  tick
end 

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

to go-random
  ask movers [
    ;; the turtle first finds the nodes that are the closest to it 
    ;; (rounding the distance to the nearest tenth), next, it checks to see how many 
    ;; nodes are closest, if there is only one, the turtle then moves forward
    if count seeds with-min [precision (distance myself) 1 ] = 1 [
      fd .04 
    ]

    rt .5 - random-float 1
   ]
end 

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

to go-organized
  ask movers [
    ;; the turtle first finds the nodes that are the closest to it 
    ;; (rounding the distance to the nearest tenth)
    let nearby seeds with-min [precision (distance myself) 1 ] 

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

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

to add-new-node
    if mouse-down?     
    [
      create-seeds 1 [
        set shape "circle"
        set size 2
        setxy mouse-xcor mouse-ycor
      ]
      stop
    ]
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]
    ]
  ]
end 

to move-seed
   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

There is only one version of this model, created about 11 years ago by David Weintrop.

Attached files

No files

This model does not have any ancestors.

This model does not have any descendants.

NetLogo