Compute Delaunay Triangulations and Voronoi Meshes in 2D using Swift. A port of the Delaunator javascript library of mapbox to the Swift programming language, with detailed annotation of the core algorithm. Small improvements include a better inCircumCircle error bound (from Shewchuk's Robust Predicates ) and small fixes to patching the convex hull.

This library produces Delaunay triangulations (or the dual Voronoi Mesh) for a set of points defined in an input JSON file; included is a bare bones SwiftUI renderer which will show these structures.

When a triangulation includes near degenerate triangles, i.e. almost collinear, the points which define the Voronoi diverge will diverge to infinity; making rendering the Voronoi mesh numerically unstable. But for less extreme triangulations the Voronoi Mesh will be well behaved.

The bare minimum usage example would be

// Delaunator_Swift always uses coordinates of type => struct Point: Hashable, Codable { var x, y: Double }
let list = [Point(x:0.0, y:0.0), Point(x:1.0, y:0.0), Point(x:1.0, y:1.0), Point(x:0.0, y:1.0)] // [{x 0, y 0}, {x 1, y 0}, {x 1, y 1}, {x 0, y 1}]

// Calculate the triangulation
var delaunay = Delaunator_Swift(from: list)

// The output
print(delaunay.triangles) // [0, 2, 1, 0, 3, 2]\n"
print(delaunay.halfEdges) // "[5, -1, -1, -1, -1, 0]\n"
print(delaunay.hull)      // "[0, 3, 2, 1]\n"

If you have Swift5.2 you just need the Delaunator.swift file for basic usage. You can simply open it in a playground.

Most of the files are for efficient input, output and a very simple rendering app for SwiftUI. Data can be input using JSON formatted files; if you want to do this but don't need the renderer you will need the Zone.swift file too.

Each zone has a name, and to do anything useful with it a provided list of points. The example above using JSON would be - the data is decoded as a StoredZones struct. Again you can try this out in a playground.

let jsonData = """
{
"zones": [
{
"name": "square",
"points": [[0, 0], [1, 0], [1, 1], [0, 1]]
}
]
}
""".data(using: .utf8)!

do {
  let stored:StoredZones = try JSONDecoder().decode(StoredZones.self, from:jsonData)
  print(stored)

  // Creating a zone from the stored zone
  let zone:Zone = Zone(from: stored.zones[0])

  // Create the point list
  var points = [Point]()
  let list   = zone.points ?? [[Double]]()
  for (_, p) in list.enumerated() {
    points.append(Point(x:p[0], y:p[1]))
  }

  // This is the triangulation step
  var delaunay = Delaunator_Swift(from: points)

  // The output
  print(delaunay.triangles) // [0, 2, 1, 0, 3, 2]\n"
  print(delaunay.halfEdges) // "[5, -1, -1, -1, -1, 0]\n"
  print(delaunay.hull)      // "[0, 3, 2, 1]\n"

}
catch { () }

Constructs a delaunay triangulation object given an array of points Point(x:Double, y:Double)

An array [Int] of triangle vertex indices (each group of three numbers forms a triangle). All triangles are directed anticlockwise.

An array [Int] of triangle half-edge indices that allows you to traverse the triangulation. i-th half-edge in the array corresponds to vertex triangles[i] the half-edge is coming from. halfedges[i] is the index of a twin half-edge in an adjacent triangle (or -1 for outer half-edges on the convex hull).

The flat array-based data structures might be counterintuitive, but they're one of the key reasons this library is fast.

An [Int] array of indices that reference points on the convex hull of the input data, counter-clockwise.

Comprehensive details on the data structures used are available via mapbox

Some implementation details are avialable in the Delaunator.Swift file.