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):
Other examples follow:
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:
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:
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!
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:
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!