algorithm - 如何找到表面已知顶点的所有三角形

Question

我需要找到构成我的曲面的所有顶点，但我只知道顶点(将它们保存为数组)和边。我在 XY 坐标系中进行。我需要它用于 Unity3D 项目(因此伪代码或 C# 代码将非常有帮助)，但也欢迎任何数学想法。

例如，我制作了一些图片。如果我的示例中没有凸角，那真的很简单——我选择任何顶点(例如 0)并在循环中取下两个顶点。它给了我三角形 0-1-2、0-2-3 和 0-3-4。

如果我有一个凸角，这也很容易。我不知道如何找到哪个顶点是凸的(有什么想法吗？)但它看起来并不复杂。然后我带他去做和上面一样的算法。

不幸的是，我的想法对更复杂的形状不起作用，例如(我的项目中总是有一个形状，我只是画了更多形状来展示更复杂的例子):

如果我有这样的形状并尝试使用上述方法，总是有任何三角形不符合我的形状。

我认为我可以使用任何数学知识。我的顶点在 XY 坐标上，所以我可以计算一些东西。如果需要，我也可以创建更多顶点，这样我就可以:

我试图尽可能准确地描述我的问题。我希望我的英语不太稳定。

请，如果您有任何想法 - 数学想法或伪代码想法如何为我的顶点制作表面 - 请写下来。如果你有任何单一的建议，而不是具体的想法——也写下来。我正在寻找灵感、想法等等。

Answer 1

我会做两个假设:

• 对于一种三角测量优于另一种测量，您没有任何特定标准。
• 你想要一些概念上简单的东西。

选取任何顶点。连接到任何其他顶点，使形成的线完全位于多边形内。这意味着

• 其他顶点不与原顶点相邻
• 连接线段不穿过多边形的边。

有可能没有这样的顶点。如果是这样，则移动到下一个顶点，迭代直到找到可以连接的一对。 将至少有一对。

当您绘制新线段时，您也将多边形分成两个多边形，每个多边形的顶点都比原始多边形少。

在这些多边形中的每一个上重复。每个线程上的停止情况(基本情况)是您不划分三角形。