# iShape-Swift/iShapeTriangulation Tag 0.9.0

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

Keywords
algorithm, convex-polygons, delaunay, delaunay-triangulation, mesh, monotone-polygons, polygon, swift, tesselation, triangle-vertices, triangulation
MIT

# 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.

## 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

```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

```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(