141 lines
2.6 KiB
C#
141 lines
2.6 KiB
C#
using System.Collections.Generic;
|
|
using UnityEngine;
|
|
|
|
public class e2dTriangulator
|
|
{
|
|
private List<Vector2> mPoints = new List<Vector2>();
|
|
|
|
public e2dTriangulator(Vector2[] points)
|
|
{
|
|
mPoints = new List<Vector2>(points);
|
|
}
|
|
|
|
public List<int> Triangulate()
|
|
{
|
|
List<int> list = new List<int>();
|
|
int count = mPoints.Count;
|
|
if (count < 3)
|
|
{
|
|
return list;
|
|
}
|
|
int[] array = new int[count];
|
|
if (Area() > 0f)
|
|
{
|
|
for (int i = 0; i < count; i++)
|
|
{
|
|
array[i] = i;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for (int j = 0; j < count; j++)
|
|
{
|
|
array[j] = count - 1 - j;
|
|
}
|
|
}
|
|
int num = count;
|
|
int num2 = 2 * num;
|
|
int num3 = 0;
|
|
int num4 = num - 1;
|
|
while (num > 2)
|
|
{
|
|
if (num2-- <= 0)
|
|
{
|
|
return list;
|
|
}
|
|
int num5 = num4;
|
|
if (num <= num5)
|
|
{
|
|
num5 = 0;
|
|
}
|
|
num4 = num5 + 1;
|
|
if (num <= num4)
|
|
{
|
|
num4 = 0;
|
|
}
|
|
int num6 = num4 + 1;
|
|
if (num <= num6)
|
|
{
|
|
num6 = 0;
|
|
}
|
|
if (Snip(num5, num4, num6, num, array))
|
|
{
|
|
int item = array[num5];
|
|
int item2 = array[num4];
|
|
int item3 = array[num6];
|
|
list.Add(item);
|
|
list.Add(item2);
|
|
list.Add(item3);
|
|
num3++;
|
|
int num7 = num4;
|
|
for (int k = num4 + 1; k < num; k++)
|
|
{
|
|
array[num7] = array[k];
|
|
num7++;
|
|
}
|
|
num--;
|
|
num2 = 2 * num;
|
|
}
|
|
}
|
|
return list;
|
|
}
|
|
|
|
private float Area()
|
|
{
|
|
int count = mPoints.Count;
|
|
float num = 0f;
|
|
int index = count - 1;
|
|
int num2 = 0;
|
|
while (num2 < count)
|
|
{
|
|
Vector2 vector = mPoints[index];
|
|
Vector2 vector2 = mPoints[num2];
|
|
num += vector.x * vector2.y - vector2.x * vector.y;
|
|
index = num2++;
|
|
}
|
|
return num * 0.5f;
|
|
}
|
|
|
|
private bool Snip(int u, int v, int w, int n, int[] V)
|
|
{
|
|
Vector2 a = mPoints[V[u]];
|
|
Vector2 b = mPoints[V[v]];
|
|
Vector2 c = mPoints[V[w]];
|
|
if (1.1754944E-38f > (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x))
|
|
{
|
|
return false;
|
|
}
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
if (i != u && i != v && i != w)
|
|
{
|
|
Vector2 p = mPoints[V[i]];
|
|
if (InsideTriangle(a, b, c, p))
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
|
|
{
|
|
float num = C.x - B.x;
|
|
float num2 = C.y - B.y;
|
|
float num3 = A.x - C.x;
|
|
float num4 = A.y - C.y;
|
|
float num5 = B.x - A.x;
|
|
float num6 = B.y - A.y;
|
|
float num7 = P.x - A.x;
|
|
float num8 = P.y - A.y;
|
|
float num9 = P.x - B.x;
|
|
float num10 = P.y - B.y;
|
|
float num11 = P.x - C.x;
|
|
float num12 = P.y - C.y;
|
|
float num13 = num * num10 - num2 * num9;
|
|
float num14 = num5 * num8 - num6 * num7;
|
|
float num15 = num3 * num12 - num4 * num11;
|
|
return num13 >= 0f && num15 >= 0f && num14 >= 0f;
|
|
}
|
|
}
|