Lloyd Optimizer Tool

Lloyd Optimizer

The Lloyd Optimizer tool optimizes the angles in a triangular grid to make them close to 60 degrees. It can run for a given time, number of iterations, or until a point no longer moves far. It can also require that all points move far enough.

From CGAL:

This optimization process alternates relocating vertices to the center of mass of their Voronoi cells, and updating the Delaunay connectivity of the triangulation. The center of mass is computed with respect to a sizing function that was designed to preserve the local density of points in the grid...

Input Parameters

• Input grid – A UGrid containing triangles to optimize.
• Number of iterations to perform – The maximum number of iterations to perform before stopping. Can be set to 0 for no limit.
• Maximum duration, in seconds – The maximum amount of time to optimize for, in seconds. Set to "0" for no limit.
• Minimum movement ratio – Fraction of the length of a vertex's shortest incident edge by which it must move during an iteration. If an iteration would move the vertex by less than this amount, then movement of the vertex will be skipped during this iteration. Other vertices may still move during the iteration, and the skipped vertex may be moved during a later iteration if the vertex gets a larger proposed move. This can be useful to prevent the optimizer from spending time moving vertices by tiny amounts. It should be a value between 0 and 1. A value of 0 will disable this condition.
• Freeze ratio – Similar to Move ratio, except that the optimization will stop rather than skip the move.

Additional Notes

The optimizer will not move points on boundary polygons or the boundaries of holes.

During development, points were observed moving across boundaries in some cases. This issue can no longer be reproduced, which prevents understanding the underlying cause and verifying that it is truly resolved. To be on the safe side, the tool will delete any points that migrate across boundaries during optimization.

While this tool operates on any 2D UGrid, it requires that the grid be fully triangulated. To accomodate this, the tool will generate a triangulated grid based on the input grid and optimize the triangulated grid instead. This may result in swapped interior edges and non-triangular cells being broken down into triangular ones. Boundaries and holes will still be preserved.

The optimizer requires that either the Timeout option, number of Iterations option, or both be set to a nonzero value to ensure it converges. If the chosen values prove too low, it is possible to resume the optimization where it left off to save time. To resume optimization, run the tool again and use the previous output grid as the new input grid.

Output Parameters

• Smoothed grid – Name of the output grid.

Current Location in Toolbox

Unstructured Grids/Lloyd Optimizer