因此，我想我只需要一些通用方法即可将封闭的样条线/点列表转换为三角形网格。也许有更好的方法？
#1 楼
如果顶点的数量不是太大，我建议您研究“削耳”。只要没有孔，对可能凹的多边形进行三角剖分是一种简单的方法。但是，顶点数为$ O（n ^ 2）$，因此如果需要处理大量顶点，可能不是一个好选择。 Dave Eberly撰写了一篇有关耳夹的论文，并且还提供了C ++的开源实现。网络上也有许多其他链接。基本思想是找到多边形的“耳朵”，该耳朵定义为多边形的三角形子集，该子集由三个连续的顶点组成多边形的找到耳朵后，将其添加到输出三角形列表中，然后将其从原始多边形中删除（这会将顶点数量减少了一个）。重复此操作，直到多边形消失。
之所以成为$ O（n ^ 2）$，是因为您必须反复搜索顶点列表以找到另一只要去除的耳朵。也有更高效的三角剖分算法，但更难以实现。
评论
$ \ begingroup $
一种使这项工作更快的方法是对顶点数组执行预遍历，复制或合并非常接近的顶点，并删除两个相邻顶点之间的直线中的顶点。它们不会以有意义的方式对生成的网格做出贡献，因此无需考虑它们。您认为有效的错误数量取决于您。这是处理固有的“肮脏”用户输入的好方法
$ \ endgroup $
–史蒂文
17年2月21日在16:41
#2 楼
如果您的目标只是填充区域，并且您说自己正在使用opengl，那么Nathan关于使用三角剖分算法++的建议的另一种选择是使用模板缓冲区。假设您要填充奇数/偶数，请清除模板缓冲区，像以前一样将多边形切成小块，但使三角形（IIRC）刚好反转模板。全部发送后，仅在模板不为零的情况下再次绘制。 （已经有一段时间了，但是我认为您可以在第二次通过的同时清除模板缓冲区，以节省下一个复杂多边形的时间。）
模板缓冲区方法也应适用于自相交的多边形。
最后一件事，我认为如果切三角形时使用三角形条纹而不是风扇，则填充效率更高。您只需要以0、1，N-1、2，N-2等方式访问顶点。order
有关模板缓冲区的更多信息可以在OpenGL模板测试和工程图中找到使用模板缓冲区填充的凹面多边形
++但是，如果您确实想使用三角剖分算法但具有大量顶点，则可以尝试使用Seidel方法，因为它“相对”容易实现，但时间复杂度接近O（n）。
但是，如果您搜索Seidel，请注意Narkhede＆
Manocha中的代码实际上不是Seidel的方法，因为它们的代码仅为O（n log n），而不是更快的O（n log * n）您应该期望，如果不熟悉它，在哪里
$$ log ^ * n = \ begin {cases}
1+ log ^ *（log（n）） ＆\ text {if $ n $> 1} \\
0＆\ text {otherwise}
\ end {cases} $$
实际上，您可以考虑随着它如此缓慢地增长，它是恒定的。
评论
$ \ begingroup $
这是一种非常整洁的技术，谢谢。我想我设法找到了一个可以使用的现成的镶嵌器，但是我可能不得不尝试一下，因为这是一个不错的主意。
$ \ endgroup $
– Sushisource
17-2-22在17:40
#3 楼
您可以访问OpenGL实用程序库吗？如果是这样，则可以从中使用镶嵌功能。参见本指南：多边形镶嵌| OpenGL编程指南评论
$ \ begingroup $
有趣，谢谢。我正在使用rust和GLium，我认为这并没有约束力，但我可以考虑提供补丁。
$ \ endgroup $
– Sushisource
17-2-22在17:38
评论
该区域始终是凸形的，还是可能是凹形的？可以是-可以将其封闭。