This page was automatically generated by NetLogo 5.0.
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Sun's Java site.
powered by NetLogo
view/download model file: best_fit_circles.nlogo
This is a demonstration of using physicomimetics to find best fit circles for a set of fixed points.
Initially the centers of the circles are placed randomly in the graphics pane. At each iteration these virtual centers move closer to a solution.
The fixed points we are trying to fit do not move. Rather, the agents in this demo are line segments that run between those fixed points and our virtual centers. These line segments (called virtual radii or v.r.) change in length and direction as the virtual centers move, but they always have one end anchored on the fixed points we are trying to fit.
In the best fit circles, the differences between the virtual radii will be minimized, i.e. they will all be as close to being the same length as possible. So we create a system in which they all strive to be the same length. In each iteration, we compute the length of each v.r. and their average length. Then we compute a force that tends to expand or compress each v.r. in the direction of that average length.
Changing the length of the v.r. moves the endpoint that was formerly attached to a virtual center, creating a new endpoint that either projects beyond that center or falls short of that center. All of these new endpoints are computed, and their x- and y-coordinates are averaged to create a new virtual center that is closer to the solution than the previous virtual center was.
The next iteration begins by computing the new virtual radii, and iteration continues until the virtual centers stop moving*.
*The phrase “stop moving” is necessarily vague. The virtual centers seems to asymptotically approach the solution centers with the force law I have selected, so it never really stops, it just becomes slower and slower. Maybe it’s better to say that the iteration continues until the rate of change is below the desired level of precision.
This simulation treats line segments as our agents, instead of particles. This simulation is not toroidal.
Click SETUP AGENTS to initialize the virtual centers. The number of virtual centers is determined by the NUMBER_OF_PARICLES slider. Then click MOVE AGENTS. Fixed points can be put in the environment by placing the mouse where you want the fixed point to be, and then clicking the mouse.
The CLEAR button will clear the graphics, which becomes handy when a lot of circles have been drawn.
The SPRING_CONSTANT slider controls the strength of the spring-like force law, FRICTION
controls the amount of friction, and TIME_STEP controls the time granularity of the simulation. All three of these sliders will affect the simulation when it is running.
When you place your first fixed point into the system, what happens? Is this problem very interesting?
Now what happens when you place a second fixed point in the system? How many solutions are there to this problem?
As you keep adding fixed points, do you think there is only one unique solution?
The red dot shows the center of mass of the fixed points. Note that the virtual centers of the best fit circles are not usually at the center of mass. Why is that?
See how the FRICTION changes behavior.
Similarly, try different values for the SPRING_CONSTANT.
Put all your fixed points in a straight line to send the virtual centers to the opposite edge of the graphics pane.
Try a different force law.
Try making the value of the SPRING_CONSTANT a function of the number of points and their distance from each other.
Allow fixed points to have different masses. Note that you can achieve a similar effect by clicking multiple times with your mouse in one location on the graphics pane.
Can you change the algorithm so that it will compute the smallest circle that encompasses all the fixed points?
Similarly, can you define an algorithm that tries to create the largest circles within the fixed points that do not include the fixed points?
Note, in order to change any NetLogo simulation, you must have the source code (i.e., “best_fit_circles.nlogo”) downloaded to your computer, as well as NetLogo itself. You can not change the code when you are running the simulation with your browser.
This simulation is an extension of best_fit_circle.nlogo to multiple circles.
The idea and the algorithm by Rodney Heil. NetLogo code by W. M. Spears.
If you mention this model in an academic publication, we ask that you include these citations for the model itself and for the NetLogo software:
- Spears, W. M. and Spears, D. F. (eds.) Physicomimetics: Physics-Based Swarm Intelligence, Springer-Verlag, (2012).
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
Copyright 2012 William M. Spears. All rights reserved.
Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:
a) this copyright notice is included, and
b) this model will not be redistributed for profit without permission from William M. Spears. Contact William M. Spears for appropriate licenses for redistribution for profit.
; William M. Spears May 2012
; Idea and algorithm by Rodney Heil April 2012
; Finding the "best fit" circle for a set of fixed_points!
; You introduce the fixed_points with your mouse.
; For research and educational use only
breed [particles particle] ; Introduce the "particle" breed
breed [fixed_points fixed_point] ; Introduce the "fixed_point" breed
globals [center_of_mass_x center_of_mass_y]
turtles-own [hood deltax deltay r F Fx Fy v vx vy dvx dvy mass ave_dist]
to setup
clear-all ; Clear everything
create-particles Number_of_Particles [setup-particles] ; Create the particles
reset-ticks
end
to setup-particles ; Set up the particles
setxy random-xcor random-ycor ; Randomly initialized locations
set heading random 360 ; Everyone has a random heading
set vx 0 set vy 0 set mass 1 ; Start with no motion and mass = 1
set color white set shape "circle" set size 5
end
to run-and-monitor
if ((count turtles) < 1) [user-message "Please click HALT and then SETUP AGENTS first" stop]
if ((count fixed_points) > 0) [
ask particles [ap-particles]
; Display circle of average radius around particle
ask particles [draw-circle who (round xcor) (round ycor) (round ave_dist)]
; Computes center of mass and displays location
set center_of_mass_x (sum [xcor * mass] of fixed_points) / (sum [mass] of fixed_points)
set center_of_mass_y (sum [ycor * mass] of fixed_points) / (sum [mass] of fixed_points)
ask patch (round center_of_mass_x) (round center_of_mass_y)
[ask patches in-radius 4 [set pcolor red]]
]
; Use mouse click to create fixed_points. Must make sure that mouse is within black graphics pane.
if (mouse-down? and mouse-inside?) [
ifelse ((count fixed_points) = 0)
[create-fixed_points 1 [setxy mouse-xcor mouse-ycor set vx 0 set vy 0 set shape "circle"
set size 10 set mass 1 set color green]]
[ask one-of fixed_points [hatch 1 [setxy mouse-xcor mouse-ycor]]]
wait 0.2 ; Pause so don't get a bunch of fixed_points at once
]
tick
end
; Draw circle around particle w at (x, y) with radius d
to draw-circle [w x y d]
ask patch x y
[ask patches in-radius (d + 1) [if ((round distance particle w) = d) [set pcolor yellow]]]
end
to ap-particles ; Run artificial physics on the particles
set Fx 0 set Fy 0 ; Initialize force components to zero
set vx (1 - Friction) * vx ; Slow down according to friction
set vy (1 - Friction) * vy
set ave_dist 0
set hood [who] of fixed_points ; Get the IDs of fixed_points
foreach hood [
set deltax (([xcor] of fixed_point ?) - xcor)
set deltay (([ycor] of fixed_point ?) - ycor)
set ave_dist ave_dist + sqrt (deltax * deltax + deltay * deltay)
]
set ave_dist (ave_dist / (count fixed_points)) ; Compute average distance
foreach hood [
set deltax (([xcor] of fixed_point ?) - xcor)
set deltay (([ycor] of fixed_point ?) - ycor)
set r sqrt (deltax * deltax + deltay * deltay) ; Compute the distance to each particle
set F (ave_dist - r) * Spring_Constant ; Simple linear force law
set Fx (Fx - (F * (deltax / r))) ; Repulsive force, x-component
set Fy (Fy - (F * (deltay / r))) ; Repulsive force, y-component
]
set dvx Time_Step * (Fx / mass)
set dvy Time_Step * (Fy / mass)
set vx (vx + dvx) ; The x-component of velocity
set vy (vy + dvy) ; The y-component of velocity
set v sqrt (vx * vx + vy * vy)
set deltax Time_Step * vx
set deltay Time_Step * vy
if ((deltax != 0) or (deltay != 0))
[set heading (atan deltax deltay)]
fd sqrt (deltax * deltax + deltay * deltay) ; Move the particle
end