用三角形填充平面（三角剖分）

Question

我尝试创建一个如下图所示的图像作为网站的随机背景，但经过多次尝试，我找不到完成这项工作的算法。

程序应该做什么？

它应该能够用三角形随机填充一个平面。这些三角形应该都是独立的，所以我不想简单地在画布上绘制长线并为创建的三角形着色。

到目前为止我尝试过的算法：

1.

• 随机点
• 以低于特定值的长度进行随机连接（这可能会导致三角形网络中出现洞）
• 尝试找出哪些连接构成三角形（我在这里失败了）

2.

• 从单个三角形开始

• 在现有连接附近创建一个新点，并从那里添加一个不会导致任何交叉的三角形。每当它留下如图所示的小孔时，就会出现问题：

  

3.

• 随机点
• 建立所有可能的连接（每个点都相互连接）
• 按长度对连接进行排序
• 对于从最短绘制开始的每个连接（如果它不与任何其他绘制的线相交）。否则删除连接。

这实际上是我最好的尝试，即使程序花了很长时间才只用几个点来完成。结果如下：

我没有找到一种方法来找出三角形的连接，因此我无法独立地为它们着色......

所以希望您知道如何创建一个漂亮的三角形填充画布，如第一张图片所示，并让我知道......

Answer 1

一个好的解决方案是从随机点（具有您首选的分布）开始并应用一些三角测量算法。其中，Delaunay 三角剖分是一个很好的候选者，因为它的计算复杂度低且代码可用性高。

Answer 2

无需三角测量即可解决，与第二种方法类似。仅生成新点将导致这种越来越凹的图案，但如果在添加之间有一个连接未连接但可能连接的点（意味着有一个点将它们两个连接到，并且新线不会与任何其他相交）（添加新三角形）这不会发生。 （在我看来，最好只在一定长度限制下添加此类行。）