meemoo hackable web apps


14 Jul 2014 by Vilson Vieira

Now that we have a working noflo-canvas it is time to try more complex shapes. Voronoi Diagram and Delaunay Triangulation are canonical algorithms from Computational Geometry and were made classic for generative art or creative coding. These algorithms are useful to create textures or meshes. In general, you can give them a set of points and Voronoi will create cells around your points. Delaunay will draw triangles for each possible triple of points, with non-crossing edges. This figure presents both Voronoi Diagram (in pink) and Delaunay Triangulation (in blue) for some random points (in yellow):

Voronoi and Delaunay

Other examples follow:

Voronoi and Delaunay

To better understand the Delaunay Triangulation, let’s see an example. The following figure shows a triangulation for a set of points. Note the circumcircles around each possible triangle:

Delaunay right example (modified from Wikipedia)

There’s no points inside of any of the circumcircles: the points are located right in circumcircles’ edges. You can try to find other triangles which points are not inside circumcircles, but you won’t. Let me give you an example of a wrong triangle:

Delaunay wrong example (modified from Wikipedia)

As you can see, the red points are inside the circumcircle of our green triangle, so it’s not a valid triangle. That’s what Delaunay Triangulation is about: for a given set of points, it finds all the triangles which points are not inside a circumcircle (formed by the triangles).

And what about Voronoi Diagram? There’s many ways to understand what Voronoi algorithm is about, but there’s an easy way now that we know Delaunay Triangulation. Voronoi is dual (or related) to Delaunay. If we connect the center points of all the triangle circumcircles obtained by the Delaunay Triangulation, we have the Voronoi Diagram!

Voronoi and Delaunay duality (modified from Wikipedia)

The noflo-geometry implements both Voronoi and Delaunay algorithms. Being NoFlo a general purpose flow-based environment, it is a common approach to search for JS libraries which implements what you want and encapsulate them as a bunch of components. For noflo-geometry we used libraries by @ironwallaby and @gorhill, and thanks to NoFlo now you can use both as components with a common interface, at the same environment:



Here are some examples of tessellations generated by the Voronoi and Delaunay component:

Voronoi diagram 1

Delaunay tessellation 1

Delaunay tessellation 1

Delaunay tessellation 1

Delaunay tessellation 1

Delaunay tessellation 1

Delaunay tessellation 1

Delaunay tessellation 1

Next steps

Forrest was invited to the super cool Assembly demo party (!!!) so we are planning to work on components for threejs, Web Audio API and timeline to create a demo! Fun times coming, please keep following!



comments powered by Disqus