[游戏开发]C++ UE4 将凸多边形通过最优解拆分为多个三角形

记录一下根据网络内容完成的算法，将一个凸多边形拆分为多个三角形的算法，语法借助了UE4。如有侵权，请私信我删除。

//	计算凸多边形的最优三角形切分
void MinWeightTriangulation(const TArray<FVector>& arr, TArray<int>& ArrTriangle)
{
	if (arr.Num() < 3)
		return;

	float** t = new float* [arr.Num()];
	int** s = new int* [arr.Num()];

	memset(t, 0, sizeof(float*) * arr.Num());
	memset(s, 0, sizeof(int*) * arr.Num());

	for (int idx = 0; idx < arr.Num(); idx++)
	{
		t[idx] = new float[arr.Num()];
		s[idx] = new int[arr.Num()];

		memset(t[idx], 0, sizeof(float) * arr.Num());
		memset(s[idx], 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[i][j] = 0xFFFFFFF;
			for (int k = i; k <= j - 1; k++) 
			{
				float q = t[i][k] + t[k + 1][j] + calweight(arr[i - 1], arr[k], arr[j]);
				if (q < t[i][j]) 
				{
					t[i][j] = q;
					s[i][j] = k;
				}
			}
		}
	}

	outTringle(1, arr.Num() - 1, s, ArrTriangle);

	for (int idx = 0; idx < arr.Num(); idx++)
	{
		delete[] t[idx];
		delete[] s[idx];
	}
	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[i][j], s, trignles);
	outTringle(s[i][j] + 1, j, s, trignles);
	trignles.Add(i - 1);
	trignles.Add(s[i][j]);
	trignles.Add(j);
}

调用函数MinWeightTriangulation即可获取到拆分到的三角形合集，存的是三角形点的索引，每三个为一组。