# 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"])
]
]
)
```