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