7using System.Collections.Generic;
16 private List<Vector2> m_points =
new List<Vector2>();
20 m_points =
new List<Vector2>(points);
25 List<int> indices =
new List<int>();
27 int n = m_points.Count;
29 return indices.ToArray();
34 for (
int v = 0; v < n; v++)
39 for (
int v = 0; v < n; v++)
45 for (
int m = 0, v = nv - 1; nv > 2;)
48 return indices.ToArray();
60 if (Snip(u, v, w, nv, V))
70 for (s = v, t = v + 1; t < nv; s++, t++)
78 return indices.ToArray();
83 int n = m_points.Count;
85 for (
int p = n - 1, q = 0; q < n; p = q++)
87 Vector2 pval = m_points[p];
88 Vector2 qval = m_points[q];
89 A += pval.x * qval.y - qval.x * pval.y;
94 private bool Snip(
int u,
int v,
int w,
int n,
int[] V)
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))))
102 for (p = 0; p < n; p++)
104 if ((p == u) || (p == v) || (p == w))
106 Vector2 P = m_points[V[p]];
107 if (InsideTriangle(A, B, C, P))
113 private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
115 float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
116 float cCROSSap, bCROSScp, aCROSSbp;
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;
125 aCROSSbp = ax * bpy - ay * bpx;
126 cCROSSap = cx * apy - cy * apx;
127 bCROSScp = bx * cpy - by * cpx;
129 return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
Triangulator(Vector2[] points)
Credit Erdener Gonenc - @PixelEnvision.