DelaunatorKotlin

DelaunatorKotlin is a fast library for Delaunay triangulation made for use in Android applications. It takes as input a set of point coordinates and produces as output a triangulation. The triangulation is represented as compact arrays of integers. It’s less convenient than other representations but is the reason the library is fast.

Delaunay triangles

After constructing a val delaunator: Delaunator = Delaunator(coordinates) object, it will have a triangles array and a halfEdges array, both indexed by half-edge id. What’s a half-edge?

A triangle edge may be shared with another triangle. Instead of thinking about each edge A↔︎B, we will use two half-edges A→B and B→A. Having two half-edges is the key to everything this library provides.

Half-edges e are the indices into both of delaunator’s outputs:

• delaunator.triangles[e] returns the point id where the half-edge starts
• delaunator.halfEdges[e] returns the opposite half-edge in the adjacent triangle, or -1 if there is no adjacent triangle

Triangle ids and half-edge ids are related.

• The half-edges of triangle t are 3*t, 3*t + 1, and 3*t + 2.
• The triangle of half-edge id e is floor(e/3).

Let’s use some helper functions for these:

  fun edgesOfTriangle(t: Int): IntArray {
    return intArrayOf(3 * t, 3 * t + 1, 3 * t + 2)
  }
  fun triangleOfEdge(e: Int): Int {
    return Math.floor(e / 3.0).toInt()
  }

It will also be useful to have some helper functions to go from one half-edge to the next and previous half-edges in the same triangle:

  fun nextHalfEdge(e: Int): Int {
    return if (e % 3 == 2) e - 2 else e + 1
  }
  fun prevHalfEdge(e: Int): Int {
    return if (e % 3 == 0) e + 2 else e - 1
  }

Note: the sample code on this page is written for readability, not performance.

Delaunay edges

We can draw all the triangle edges without constructing the triangles themselves. Each edge is two half-edges. A half-edge e starts at point with indices for the X and Y coordinates: [delaunator.triangles[e] * 2] and [delaunator.triangles[e] * 2 + 1]. Its opposite delaunator.halfEdges[e] starts at the other end, so that tells us the two endpoints of the edge. However, the half-edges along the convex hull won’t have an opposite, so the two indices [delaunator.halfEdges[e] * 2] and [delaunator.halfEdges[e] * 2 + 1] will be -1, and getting the coordinates will fail. To reliably find the other end of the edge, we need to instead use indices from nextHalfEdge(e). We can loop through the half-edges and pick half of them to draw:

  fun forEachTriangleEdge(delaunator: Delaunator) {
    for (e in delaunator.triangles.indices) {
      if (e > delaunator.halfEdges[e]) {

        val i1 = delaunator.triangles[e] * 2
        val x1 = delaunator.coordinates[i1]
        val y1 = delaunator.coordinates[i1 + 1]

        val i2 = delaunator.triangles[nextHalfEdge(e)] * 2
        val x2 = delaunator.coordinates[i2]
        val y2 = delaunator.coordinates[i2 + 1]

        // coordinates of the edge points are: (x1,y1) and (x2,y2)
      }
    }
  }
    

Constructing triangles

A triangle is formed from three consecutive half-edges, 3*t, 3*t + 1, 3*t + 2. Each half-edge e starts at points[e], so we can connect those three points into a triangle.

    fun edgesOfTriangle(t: Int): IntArray {
        return intArrayOf(3 * t, 3 * t + 1, 3 * t + 2)
    }

    fun forEachTriangle(delaunator: Delaunator) {
        for (t in 0 until delaunator.triangles.size / 3) {

            val i1 = delaunator.triangles[t]
            val x1 = delaunator.coordinates[i1 * 2]
            val y1 = delaunator.coordinates[i1 * 2 + 1]

            val i2 = delaunator.triangles[t + 1]
            val x2 = delaunator.coordinates[i2 * 2]
            val y2 = delaunator.coordinates[i2 * 2 + 1]

            val i3 = delaunator.triangles[t + 2]
            val x3 = delaunator.coordinates[i3 * 2]
            val y3 = delaunator.coordinates[i3 * 2 + 1]

            // coordinates of the triangle points are: (x1,y1), (x2,y2) and (x3,y3)
        }
    }
        

Adjacent triangles

We can also use the half-edges of a triangle to find the adjacent triangles. Each half-edge's opposite will be in an adjacent triangle, and the edgeIdToTriangleId helper function will tell us which triangle a half-edge is in:

  fun edgesOfTriangle(t: Int): IntArray {
     return intArrayOf(3 * t, 3 * t + 1, 3 * t + 2)
  }

  fun triangleOfEdge(e: Int): Int {
      return Math.floor(e / 3.0).toInt()
  }

  fun trianglesAdjacentToTriangle(delaunay: Delaunator, t: Int): ArrayList<Int> {
     val adjacentTriangles = arrayListOf<Int>()
     for (e in edgesOfTriangle(t)) {
       val opposite = delaunay.halfEdges[e]
       if (opposite >= 0) {
         adjacentTriangles.add(triangleOfEdge(opposite))
       }
     }
     return adjacentTriangles
  }