Code covered by the BSD License  

Highlights from
Lloyd's Algorithm

5.0

5.0 | 1 rating Rate this file 57 Downloads (last 30 days) File Size: 3.68 KB File ID: #41507
image thumbnail

Lloyd's Algorithm

by

 

26 Apr 2013 (Updated )

Starts with a point set, repeatedly moves each point to centroid of Voronoi cell.

| Watch this File

File Information
Description

LLOYDSALGORITHM runs Lloyd's algorithm on the particles at xy positions
 (Px,Py) within the boundary polygon crs for numIterations iterations
 showPlot = true will display the results graphically.
 
 Lloyd's algorithm starts with an initial distribution of samples or
 points and consists of repeatedly executing one relaxation step:
   1. The Voronoi diagram of all the points is computed.
   2. Each cell of the Voronoi diagram is integrated and the centroid is computed.
   3. Each point is then moved to the centroid of its Voronoi cell.
 Inspired by http://www.mathworks.com/matlabcentral/fileexchange/34428-voronoilimit
 Requires the Polybool function of the mapping toolbox to run.

 Run with no input to see example. To initialize a square with 50 robots
 in left middle, run:
lloydsAlgorithm(0.01*rand(50,1),zeros(50,1)+1/2, [0,0;0,1;1,1;1,0], 200, true)

Acknowledgements

Voronoi Limit inspired this file.

Required Products Mapping Toolbox
MATLAB
MATLAB release MATLAB 7.14 (R2012a)
MATLAB Search Path
/
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (4)
04 Nov 2014 Aaron Becker

Corrected error when called as a function by adding a calculation for n, removed warning about order of vertices by sorting them in CW order, added example call as a function. Thanks for the feedback Kirill Smirnov!

03 Nov 2014 Kirill Smirnov

I just downloaded this file but when I specify the arguments, I have an error message:
'Undefined function or variable "n".
Error in lloydsAlgorithm (line 63)'.
Because 'n' is initialized only in the 'demo' part of the code. If I put at the beginning something like n = length(Px), everything works fine. Anyway, thank you for your effort!

24 Jul 2014 Aaron Becker

Certainly Lindsey -- the code was designed so you can supply the boundary of your environment by supplying the variable crs. Alternatively, to get rid of the white rectangle in the top middle just comment out lines 42,43,44, and 45:
crs = [ 0, 0;
0, yrange;
% 1/3*xrange, yrange; % a world with a narrow passage
% 1/3*xrange, 1/4*yrange;
% 2/3*xrange, 1/4*yrange;
% 2/3*xrange, yrange;
xrange, yrange;
xrange, 0];

Aaron T. Becker

24 Jul 2014 Lindsey

Dear All,

First of all, thank you for sharing the Lloyd Algorithm with everyone. I have a question regarding the algorithm. Is it possible to remove the white space in the code?

Thank you and I appreciate if you can help me on this regard,

Lindsey

Updates
29 Apr 2013

removed dependency on www.mathworks.com/matlabcentral/fileexchange/34428 (which sometimes miscalculates the Voronoi cell boundaries), robots never leave the boundary, reduces to a single file.

29 Apr 2013

When run with no arguments, starts the robots in a small grid pattern.

04 Nov 2014

Corrected error when called as a function by adding a calculation for n, removed warning about order of vertices by sorting them in CW order, added example call as a function. Thanks for the feedback Kirill Smirnov!

Contact us