## How to implement a basic Voronoi relaxation (Lloyd’s algorithm) in Processing in few simple steps

I stumbled upon this algorithm while researching for another project, I am not sure yet for what I will use it, anyway it’s nice and neat, so here it is.

The goal of the **Voronoi relaxation** algorithm is to obtain an **even distribution of** previously provided** points**. To achieve this, the **steps** of the algorithm, as described from the Wikipedia page, are:

Lloyd’s algorithm starts by an initial placement of some number

kof point sites in the input domain. […]It then repeatedly executes the following relaxation step:

- The Voronoi diagram of the
ksites 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.

Quite straightforward, let’s see the **implementation**. To get the Voronoi diagram we will use the famous Processing library **Toxiclibs**, so make sure to have it on your machine and to import it on your Processing sketch. We will also need the Java List interface.

import java.util.List; import toxi.geom.*; import toxi.geom.mesh2d.Voronoi;

Let’s create, as a global variable, the List of points that we are going to relax.

List<Vec2D> points;

Now we initialize them in `setup()`

.

void setup() { size(800, 600); noFill(); points = new ArrayList<Vec2D>(); int n_points = 50; for (int i=0; i<n_points; i++) { points.add( new Vec2D(random(width), random(height))); } }

Now we will relax the points. First we create a `Voronoi`

object, as per documentation, and we add all the `points`

of our List to it. From the `Voronoi`

object we can use the `getRegions()`

method to get the cells of our Voronoi diagram. For all the regions we can now get the centroids with `getCentroid()`

which will be the new positions of our points. We repeat the process at each iteration of `draw()`

.

There is **still a problem** to address: since the exterior regions of the Voronoi diagram are huge they will lead to unexpected behaviors and crashes when we use their centroids as new points’ locations. What we need to do is to clip them, so that they don’t go out of the boundaries of the screen. Luckily Toxiclibs has an easy class for this, the SutherlandHodgemanClipper clipper.

Here’s the code for the Voronoi relaxation:

Voronoi voronoi = new Voronoi(); voronoi.addPoints(points); Rect bound_rect = new Rect(0, 0, width, height); SutherlandHodgemanClipper clipper = new SutherlandHodgemanClipper(bound_rect); List<Polygon2D> regions = voronoi.getRegions(); for (int i=0; i<regions.size(); i++) { regions.set(i, clipper.clipPolygon(regions.get(i))); Vec2D centroid = regions.get(i).getCentroid(); points.set(i, centroid); }

Finally, few simple drawing functions for drawing points and polygons and **we are done** 😉

void drawPoints(List<Vec2D> pts) { for (Vec2D p : pts) ellipse(p.x, p.y, 2, 2); } void drawPolygons(List<Polygon2D> ps) { for (Polygon2D p : ps) drawPolygon(p); } void drawPolygon(Polygon2D p) { beginShape(); for (Vec2D v : p.vertices) vertex(v.x, v.y); endShape(CLOSE); }

Here’s the whole **code**, also on GitHub, enjoy.

import java.util.List; import toxi.geom.*; import toxi.geom.mesh2d.Voronoi; List<Vec2D> points; void setup() { size(800, 600); noFill(); points = new ArrayList<Vec2D>(); int n_points = 50; for (int i=0; i<n_points; i++) { points.add( new Vec2D(random(width), random(height))); } } void draw() { background(255); Voronoi voronoi = new Voronoi(); voronoi.addPoints(points); Rect bound_rect = new Rect(0, 0, width, height); SutherlandHodgemanClipper clipper = new SutherlandHodgemanClipper(bound_rect); List<Polygon2D> regions = voronoi.getRegions(); for (int i=0; i<regions.size(); i++) { regions.set(i, clipper.clipPolygon(regions.get(i))); Vec2D centroid = regions.get(i).getCentroid(); points.set(i, centroid); } drawPoints(points); drawPolygons(regions); } void drawPoints(List<Vec2D> pts) { for (Vec2D p : pts) ellipse(p.x, p.y, 2, 2); } void drawPolygons(List<Polygon2D> ps) { for (Polygon2D p : ps) drawPolygon(p); } void drawPolygon(Polygon2D p) { beginShape(); for (Vec2D v : p.vertices) vertex(v.x, v.y); endShape(CLOSE); } void mousePressed() { points.add(new Vec2D(mouseX, mouseY)); } void mouseDragged() { points.add(new Vec2D(mouseX, mouseY)); }