[Deprecated]

This tool for image manipulation with Voronoi/Delaunay is deprecated and was rewritten.

Visit the successor project: github.com/MauriceGit/Voronoi_Image_Manipulation

Please use the new tool for the following reasons:

• More functionality
• A lot more user friendly
• Real-time with an actual GUI
• A lot faster (a LOT. We are talking speed improvement of factor >100)
• A lot more robust
• Actual O(n log(n)) performance

Visit the successor project: github.com/MauriceGit/Voronoi_Image_Manipulation

Delaunay Triangulation and Voronoi Regions in images

This project consists of several parts which are joined together.

Image of an end result:

• Triangulation

  I always wanted to properly implement a Delaunay triangulation. So here it is. It runs in Omega(n logn). As soon as I change the data structure, also in O(n logn). Anyway. You provide a list of points (tuples with x,y-coordinates!) and get back a list of triangles (also tuples with three points per triangle!). In the new version it also transforms the triangles into Voronoi regions (polygons --> list of list of points).

  Example image of 100 random points triangulated:

• Image-Triangulation:

  This is the actual application of the Delaunay triangulation. You can specify a .jpg-Image and the program will perform some gauss-filtering and edge detection. Based on the contrast difference of the image there is a propability that a point is set on that spot (per pixel). With that there will be more points generated in areas with high contrast differences than in areas with equal colors and contrasts. These points will then be triangulated. After that each triangle will get colored with the approximate mean color of the pixels inside the triangle. Approximate because only the Vertices and the center of the triangle will be considered. These colored triangles will then be rendered into an new jpg-image.

  Example image with about 4000 different points triangulated and colored according to the original picture:

  Example image when the points are equally distributed and not extracted from the picture:

• Voronoi-Diagrams:

  The Delaunay triangulation is taken and transformed in O(n) into Voronoi regions. These regions will then be rendered into an image just like the triangles before. The color is determined by the average color of each corner and the center of the polygon.

  Example image directly converted from triangles to Voronoi regions:

  Now with equally distributed point selection (looking a bit better with Voronoi regions in my opionion):

• Point-Distribution:

  There are different options for determining points in the image for triangulation. Points can be determined from edge-detection and are more common in parts of the image where bigger color-differences occure. Otherwise points can be distributed equally over the image space. The choice has a quite big influence on the outcome-image. For the Delaunay triangulation I prefer more points in edging areas. For Voronoi regions it looks more pleasant if the regions are more equally distributed. Anyway the results are stunning (in my opinion) :).

  Result of a triangulation with point-extraction from edges and constrast:

  The next image shows the exact same extracted triangles with random colors and not colored from the photo: