1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
| public static class Triangulate
{
static public List<uint> ProcessIndex(List<Vector> contour)
{
int n = contour.Count;
if (n < 3)
throw new Exception("[Triangulate::ProcessIndex] ERROR - vertex count <3 !");
else if (n == 3)
return new List<uint>(new uint[] { 0, 1, 2});
int[] V = new int[n];
/* we want a counter-clockwise polygon in V */
if (0.0 < Area(contour))
for (int v = 0; v < n; v++) V[v] = v;
else
for (int v = 0; v < n; v++) V[v] = (n - 1) - v;
int nv = n;
/* remove nv-2 Vertices, creating 1 triangle every time */
int count = 2 * nv; /* error detection */
List<uint> result = new List<uint>(count);
for (int m = 0, v = nv - 1; nv > 2; )
{
/* if we loop, it is probably a non-simple polygon */
if (0 >= (count--))
{
throw new Exception("[Triangulate::ProcessIndex] ERROR - probable bad polygon!");
}
/* three consecutive vertices in current polygon, <u,v,w> */
int u = v; if (nv <= u) u = 0; /* previous */
v = u + 1; if (nv <= v) v = 0; /* new v */
int w = v + 1; if (nv <= w) w = 0; /* next */
if (Snip(contour, u, v, w, nv, V))
{
int a, b, c, s, t;
/* true names of the vertices */
a = V[u]; b = V[v]; c = V[w];
/* output Triangle */
result.Add((uint)a);
result.Add((uint)b);
result.Add((uint)c);
m++;
/* remove v from remaining polygon */
for (s = v, t = v + 1; t < nv; s++, t++) V[s] = V[t]; nv--;
/* resest error detection counter */
count = 2 * nv;
}
}
return result;
}
// compute area of a contour/polygon
static double Area(List<Vector> contour)
{
int n = contour.Count;
double A = 0.0f;
for (int p = n - 1, q = 0; q < n; p = q++)
{
A += contour[p].x * contour[q].y - contour[q].x * contour[p].y;
}
return A * 0.5f;
}
/*
InsideTriangle decides if a point P is Inside of the triangle
defined by A, B, C.
*/
static bool InsideTriangle( double Ax, double Ay,
double Bx, double By,
double Cx, double Cy,
double Px, double Py)
{
double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
double cCROSSap, bCROSScp, aCROSSbp;
ax = Cx - Bx; ay = Cy - By;
bx = Ax - Cx; by = Ay - Cy;
cx = Bx - Ax; cy = By - Ay;
apx= Px - Ax; apy= Py - Ay;
bpx= Px - Bx; bpy= Py - By;
cpx= Px - Cx; cpy= Py - Cy;
aCROSSbp = ax*bpy - ay*bpx;
cCROSSap = cx*apy - cy*apx;
bCROSScp = bx*cpy - by*cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}
static bool Snip(List<Vector> contour,int u,int v,int w,int n,int[] V)
{
int p;
double Ax, Ay, Bx, By, Cx, Cy, Px, Py;
Ax = contour[V[u]].x;
Ay = contour[V[u]].y;
Bx = contour[V[v]].x;
By = contour[V[v]].y;
Cx = contour[V[w]].x;
Cy = contour[V[w]].y;
if (Constants.Epsilon > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) return false;
for (p = 0; p < n; p++)
{
if ((p == u) || (p == v) || (p == w)) continue;
Px = contour[V[p]].x;
Py = contour[V[p]].y;
if (InsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) return false;
}
return true;
}
} |
Partager