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_circle.nlogo
This is a demonstration of using physicomimetics to find the best fit circle for a set of fixed points.
Initially the center of the circle is placed near the center of the graphics pane. At each iteration this virtual center moves 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 center. These line segments (called virtual radii or v.r.) change in length and direction as the virtual center moves, but they always have one end anchored on the fixed points we are trying to fit.
In the best fit circle, 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 the 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 center stops moving*.
*The phrase “stops moving” is necessarily vague. The virtual center seems to asymptotically approach the solution center 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 center. 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 graph shows the average of the virtual radii. How does this graph change as you add new fixed points?
The red dot shows the center of mass of the fixed points. Note that the virtual center of the best fit circle is 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 center 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.
Extend the simulation to have multiple virtual centers all independently trying to find
solutions (or see “best_fit_circles.html”).
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 give the largest circle within the fixed points that does not include the fixed points?
Note, in order to change any NetLogo simulation, you must have the source code (i.e., “best_fit_circle.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.
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 [ave_dist center_of_mass_x center_of_mass_y]
turtles-own [hood deltax deltay r F Fx Fy v vx vy dvx dvy mass]
to setup
clear-all ; Clear everything
create-particles 1 [setup-particles] ; Setup only one particle
reset-ticks
end
; Note, the code can be modified for an arbitrary number of moving particles,
; but for this application we only need one.
to setup-particles ; Set up the particles
setxy (random-normal 0 10)
(random-normal 0 10) ; Start near the center
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 fixed_points [compute_distance] ; Compute r
set ave_dist mean [r] of fixed_points ; Compute mean r
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]]
; Graph the plot
do-plots
]
; 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 compute_distance ; Compute distance of particle to the fixed_points
set hood [who] of particles ; Get the IDs of all particles
foreach hood [
set deltax (([xcor] of particle ?) - xcor)
set deltay (([ycor] of particle ?) - ycor)
set r sqrt (deltax * deltax + deltay * deltay) ; Compute the distance to each particle
]
end
to ap-particles ; Run artificial physics on the particle
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 hood [who] of fixed_points ; Get the IDs of the fixed_points
foreach hood [
set deltax (([xcor] of fixed_point ?) - xcor)
set deltay (([ycor] of fixed_point ?) - ycor)
set r ([r] of fixed_point ?) ; No need to recompute r
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
to do-plots
set-current-plot "Average Radius" ; Select the Average Radius Plot
set-current-plot-pen "Ave Radius" ; Select the Ave Radius pen
plot ave_dist ; Plot the average radius
end