C++ UE4 将凸多边形通过最优解拆分为多个三角形

admin

1. //        计算凸多边形的最优三角形切分
2. void MinWeightTriangulation(const TArray<FVector>& arr, TArray<int>& ArrTriangle)
3. {
4.         if (arr.Num() < 3)
5.                 return;
7.         float** t = new float* [arr.Num()];
8.         int** s = new int* [arr.Num()];
10.         memset(t, 0, sizeof(float*) * arr.Num());
11.         memset(s, 0, sizeof(int*) * arr.Num());
13.         for (int idx = 0; idx < arr.Num(); idx++)
14.         {
15.                 t[idx] = new float[arr.Num()];
16.                 s[idx] = new int[arr.Num()];
18.                 memset(t[idx], 0, sizeof(float) * arr.Num());
19.                 memset(s[idx], 0, sizeof(int) * arr.Num());
20.         }
22.         int j;
23.         for (int len = 2; len <= arr.Num() - 1; len++)
24.         {
25.                 for (int i = 1; i <= arr.Num() - len; i++)
26.                 {
27.                         j = i + len - 1;
28.                         t[i][j] = 0xFFFFFFF;
29.                         for (int k = i; k <= j - 1; k++)
30.                         {
31.                                 float q = t[i][k] + t[k + 1][j] + calweight(arr[i - 1], arr[k], arr[j]);
32.                                 if (q < t[i][j])
33.                                 {
34.                                         t[i][j] = q;
35.                                         s[i][j] = k;
36.                                 }
37.                         }
38.                 }
39.         }
41.         outTringle(1, arr.Num() - 1, s, ArrTriangle);
43.         for (int idx = 0; idx < arr.Num(); idx++)
44.         {
45.                 delete[] t[idx];
46.                 delete[] s[idx];
47.         }
48.         delete t;
49.         delete s;
50. }
52. float calweight(FVector a, FVector b, FVector c)
53. {
54.         float x = (a - b).SizeSquared2D();
55.         float y = (a - c).SizeSquared2D();
56.         float z = (b - c).SizeSquared2D();
57.         return x + y + z;
58. }
60. void outTringle(int i, int j, int** s, TArray<int>& trignles)
61. {
62.         if (i == j)
63.                 return;
64.         outTringle(i, s[i][j], s, trignles);
65.         outTringle(s[i][j] + 1, j, s, trignles);
66.         trignles.Add(i - 1);
67.         trignles.Add(s[i][j]);
68.         trignles.Add(j);
69. }

复制代码