C++ UE4 将凸多边形通过最优解拆分为多个三角形
// 计算凸多边形的最优三角形切分void MinWeightTriangulation(const TArray<FVector>& arr, TArray<int>& ArrTriangle)
{
if (arr.Num() < 3)
return;
float** t = new float* ;
int** s = new int* ;
memset(t, 0, sizeof(float*) * arr.Num());
memset(s, 0, sizeof(int*) * arr.Num());
for (int idx = 0; idx < arr.Num(); idx++)
{
t = new float;
s = new int;
memset(t, 0, sizeof(float) * arr.Num());
memset(s, 0, sizeof(int) * arr.Num());
}
int j;
for (int len = 2; len <= arr.Num() - 1; len++)
{
for (int i = 1; i <= arr.Num() - len; i++)
{
j = i + len - 1;
t = 0xFFFFFFF;
for (int k = i; k <= j - 1; k++)
{
float q = t + t + calweight(arr, arr, arr);
if (q < t)
{
t = q;
s = k;
}
}
}
}
outTringle(1, arr.Num() - 1, s, ArrTriangle);
for (int idx = 0; idx < arr.Num(); idx++)
{
delete[] t;
delete[] s;
}
delete t;
delete s;
}
float calweight(FVector a, FVector b, FVector c)
{
float x = (a - b).SizeSquared2D();
float y = (a - c).SizeSquared2D();
float z = (b - c).SizeSquared2D();
return x + y + z;
}
void outTringle(int i, int j, int** s, TArray<int>& trignles)
{
if (i == j)
return;
outTringle(i, s, s, trignles);
outTringle(s + 1, j, s, trignles);
trignles.Add(i - 1);
trignles.Add(s);
trignles.Add(j);
}
页:
[1]