Need help with Delaunay_Triangulation?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

212 Stars 25 Forks ISC License 63 Commits 0 Opened issues


My own implementation of a Delaunay triangulation and Voronoi partition in Python applied to images.

Services available


Need anything else?

Contributors list


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

Visit the successor project:

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:

Delaunay Triangulation and Voronoi Regions in images

This project consists of several parts which are joined together.

Image of an end result: Voronoi-diagrams of a sunset

  • 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 of a triangulation of 100 points

  • 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: Image of a triangulation of a photo of a sunset

    Example image when the points are equally distributed and not extracted from the picture: Image of a triangulation of a photo of some fireworks

  • 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: Image of Voronoi regions

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

  • 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: Image with triangles from edges

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

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.