iShapeTriangulation

Complex polygon triangulation, tessellation and split into convex polygons. A fast O(n*log(n)) algorithm based on "Triangulation of monotone polygons". The result can be represented as a Delaunay triangulation.

Delaunay triangulation

Breaking into convex polygons

Triangulation with extra points

Tessellation

Centroid net

Features

💡 Fast O(n*log(n)) algorithm based on "Triangulation of monotone polygons"

💡 All code is written to suit "Data Oriented Design". No reference type like class, just structs.

💡 Supports polygons with holes

💡 Supports plain and Delaunay triangulation

💡 Supports tesselation

💡 Supports breaking into convex polygons

💡 Supports building centroid net

💡 Same points is not restricted

💡 Polygon must not have self intersections

💡 Use integer geometry for calculations

💡 More then 100 tests

---

Basic Usage

Add import:

import iGeometry
import iShapeTriangulation

After that you need represent your polygon as an array of vertices listed in a clockwise direction. Let's have a look for an example of a cheese polygon.

    let path = [
        // vertices listed in clockwise direction
        Point(x: 0, y: 20),       // 0
        Point(x: 8, y: 10),       // 1
        Point(x: 7, y: 6),        // 2
        Point(x: 9, y: 1),        // 3
        Point(x: 13, y: -1),      // 4
        Point(x: 17, y: 1),       // 5
        Point(x: 26, y: -7),      // 6
        Point(x: 14, y: -15),     // 7
        Point(x: 0, y: -18),      // 8
        Point(x: -14, y: -15),    // 9
        Point(x: -25, y: -7),     // 10
        Point(x: -18, y: 0),      // 11
        Point(x: -16, y: -3),     // 12
        Point(x: -13, y: -4),     // 13
        Point(x: -8, y: -2),      // 14
        Point(x: -6, y: 2),       // 15
        Point(x: -7, y: 6),       // 16
        Point(x: -10, y: 8)       // 17
    ]

Then get an instance of a Triangulator class and triangulate your polygon. As the result you will get an array of indices on your vertices array. Where each triple are represent an indices of a triangle vertices.

    let triangulator = Triangulator()
    let triangles = triangulator.triangulateDelaunay(points: path)

    for i in 0..<triangles.count / 3 {
        let ai = triangles[3 * i]
        let bi = triangles[3 * i + 1]
        let ci = triangles[3 * i + 2]
        print("triangle \(i): (\(ai), \(bi), \(ci))")
    }

The triple are always list vertices in a clock wise direction.

Lets look another example for a polygon with a hole. Now you need represent a hole as an array of vertices listed in counterclockwise direction

    let hole = [
        // vertices listed in counterclockwise direction
        Point(x: 2, y: 0),    // 18
        Point(x: -2, y: -2),  // 19
        Point(x: -4, y: -5),  // 20
        Point(x: -2, y: -9),  // 21
        Point(x: 2, y: -11),  // 22
        Point(x: 5, y: -9),   // 23
        Point(x: 7, y: -5),   // 24
        Point(x: 5, y: -2)    // 25
    ]
    
    let points = path + hole
    let triangles = triangulator.triangulateDelaunay(points: points, hull: points[0..<path.count], holes: [points[path.count..<points.count]], extraPoints: nil)

    for i in 0..<triangles.count / 3 {
        let ai = triangles[3 * i]
        let bi = triangles[3 * i + 1]
        let ci = triangles[3 * i + 2]
        print("triangle \(i): (\(ai), \(bi), \(ci))")
    }

---

Installation

add imports:

import iGeometry
import iShapeTriangulation

CocoaPods

Add the following to your Podfile:

pod 'iShapeTriangulation'

Cartage

Add the following to your Cartfile:

github "iShape-Swift/iShapeTriangulation"

Package Manager

Add the following to your Package.swift:

let package = Package(
    name: "[your name]",
    products: [
        dependencies: [
            .package(url: "https://github.com/iShape-Swift/iShapeTriangulation", from: "0.8.0")
        ],
        targets: [
            .target(
                name: "[your target]",
                dependencies: ["iShapeTriangulation"])
        ]
    ]
)