Tanoda
Triangulator.cs
Go to the documentation of this file.
1
5
6using UnityEngine;
7using System.Collections.Generic;
8
10{
13[ExecuteInEditMode]
14public class Triangulator
15{
16 private List<Vector2> m_points = new List<Vector2>();
17
18 public Triangulator(Vector2[] points)
19 {
20 m_points = new List<Vector2>(points);
21 }
22
23 public int[] Triangulate()
24 {
25 List<int> indices = new List<int>();
26
27 int n = m_points.Count;
28 if (n < 3)
29 return indices.ToArray();
30
31 int[] V = new int[n];
32 if (Area() > 0)
33 {
34 for (int v = 0; v < n; v++)
35 V[v] = v;
36 }
37 else
38 {
39 for (int v = 0; v < n; v++)
40 V[v] = (n - 1) - v;
41 }
42
43 int nv = n;
44 int count = 2 * nv;
45 for (int m = 0, v = nv - 1; nv > 2;)
46 {
47 if ((count--) <= 0)
48 return indices.ToArray();
49
50 int u = v;
51 if (nv <= u)
52 u = 0;
53 v = u + 1;
54 if (nv <= v)
55 v = 0;
56 int w = v + 1;
57 if (nv <= w)
58 w = 0;
59
60 if (Snip(u, v, w, nv, V))
61 {
62 int a, b, c, s, t;
63 a = V[u];
64 b = V[v];
65 c = V[w];
66 indices.Add(a);
67 indices.Add(b);
68 indices.Add(c);
69 m++;
70 for (s = v, t = v + 1; t < nv; s++, t++)
71 V[s] = V[t];
72 nv--;
73 count = 2 * nv;
74 }
75 }
76
77 indices.Reverse();
78 return indices.ToArray();
79 }
80
81 private float Area()
82 {
83 int n = m_points.Count;
84 float A = 0.0f;
85 for (int p = n - 1, q = 0; q < n; p = q++)
86 {
87 Vector2 pval = m_points[p];
88 Vector2 qval = m_points[q];
89 A += pval.x * qval.y - qval.x * pval.y;
90 }
91 return (A * 0.5f);
92 }
93
94 private bool Snip(int u, int v, int w, int n, int[] V)
95 {
96 int p;
97 Vector2 A = m_points[V[u]];
98 Vector2 B = m_points[V[v]];
99 Vector2 C = m_points[V[w]];
100 if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
101 return false;
102 for (p = 0; p < n; p++)
103 {
104 if ((p == u) || (p == v) || (p == w))
105 continue;
106 Vector2 P = m_points[V[p]];
107 if (InsideTriangle(A, B, C, P))
108 return false;
109 }
110 return true;
111 }
112
113 private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
114 {
115 float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
116 float cCROSSap, bCROSScp, aCROSSbp;
117
118 ax = C.x - B.x; ay = C.y - B.y;
119 bx = A.x - C.x; by = A.y - C.y;
120 cx = B.x - A.x; cy = B.y - A.y;
121 apx = P.x - A.x; apy = P.y - A.y;
122 bpx = P.x - B.x; bpy = P.y - B.y;
123 cpx = P.x - C.x; cpy = P.y - C.y;
124
125 aCROSSbp = ax * bpy - ay * bpx;
126 cCROSSap = cx * apy - cy * apx;
127 bCROSScp = bx * cpy - by * cpx;
128
129 return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
130 }
131}
132}
Credit Erdener Gonenc - @PixelEnvision.