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.
💡 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
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()
if let triangles = try? 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
if let triangles = try? 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))")
}
}
add imports:
import iGeometry
import iShapeTriangulation
Add the following to your Podfile
:
pod 'iShapeTriangulation'
Add the following to your Cartfile
:
github "iShape-Swift/iShapeTriangulation"
Add the following to your Package.swift
:
let package = Package(
name: "[your name]",
products: [
dependencies: [
.package(url: "https://github.com/iShape-Swift/iShapeTriangulation", from: "1.0.0")
],
targets: [
.target(
name: "[your target]",
dependencies: ["iShapeTriangulation"])
]
]
)
Or add it directly throw .xcodeproj