


We also say that the triangles satisfy the empty circle property (Figure 2).įigure 2: All triangles satisfy the empty circle property.Īfter this short theoretical introduction, we want to apply this technique to a more practical yet aesthetical field, concretely to transform an input image to its triangulated counterpart. So, considering that we have a set of six points, we can obtain a triangulated polygon by tracing a circle around each vertex of the constructed triangle in such a manner that the circumcircle of all five triangles is empty. This will get valuable meaning in the following sections. The circumcircle of a triangle is the unique circle passing through all the vertices of the triangle. “…a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).”

Wikipedia has a very succinct definition of the Delaunay triangulation: This is what differentiates the Delaunay triangulation from the other triangulation techniques.įigure 1: Point set triangulation. But to think of a point set as a convex polygon, the points from the interior of the convex hull should not be ignored completely. In other terms, the triangulation might be conceived as a geometric object defined by a point set, but what differentiates the polygons from a point set is that the latter does not have an interior, except if we treat the point set as a convex hull/polygon. This will be an attempt to explore the fields of computer technology and art.īut first, what is triangulation? Simply spoken, triangulation partitions a polygon into triangles, which allows, for instance, to compute the area of a polygon and make some operations on the computed polygon surface - for example, to interpolate the triangulated area color palette and repaint it with the obtained average color. In this article, we present a technique to triangulate source images, converting them to abstract, somewhat artistic images composed of tiles of triangles.
