Code covered by the BSD License

### Highlights from Lloyd's Algorithm

5.0

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

# Lloyd's Algorithm

26 Apr 2013 (Updated )

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

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
`/`
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!

03 Nov 2014

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

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

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

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!