Lloyd's algorithm: Difference between revisions

Revision as of 09:23, 26 February 2017

Revision as of 09:25, 26 February 2017

Line 32:

==Algorithm description==

Lloyd's algorithm starts by an initial placement of some number ''k'' of point sites in the input ___domain. In mesh -smoothing applications, these would be the vertices of the mesh to be smoothed; in other applications they may be placed at random, or by intersecting a uniform triangular mesh of the appropriate size with the input ___domain.

It then repeatedly executes the following relaxation step:

* The [[Voronoi diagram]] of the ''k'' sites is computed.

* Each cell of the Voronoi diagram is integrated, and the centroid is computed.

* Each site is then moved to the centroid of its Voronoi cell.