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

Question

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

javascriptalgorithmcanvastriangulationtriangular

3

我尝试为网站创建一个像下面这样的随机背景图像，但经过多次尝试，我无法找到一个可以完成这项工作的算法。

程序应该做什么？

它应该能够随机填充平面三角形。这些三角形应该是独立的，因此我不希望只是在画布上绘制长线并着色创建的三角形。

我尝试过的算法：

1.

生成随机点
使用小于特定值的长度生成随机连接（这可能导致三角形网中出现孔洞）
尝试找出哪些连接构成三角形（我在这里失败了）

2.

从单个三角形开始
在现有连接附近创建一个新点，并添加一个不会导致任何交叉的三角形。每当出现像这张图片中的小洞时，就会遇到问题：

3.

生成随机点
建立所有可能的连接（每个点到其他每个点）
按长度对连接进行排序
对于每个以最短距离开始的连接，如果它没有与任何其他已绘制的线相交，则绘制。否则删除该连接。

即使只有少数点，这实际上是我的最佳尝试，但程序需要很长时间才能完成。这是结果的样子：

我找不到一种方法来确定哪些连接成三角形，因此我无法将它们独立着色...

希望你知道一种创建像第一张图片中填充三角形的漂亮画布的方法并让我知道...

- Anton Ballmaier

你能不能设置一个点，例如在周围随机画4个点，并将它们与中间的点和周围的点连接起来，然后再用更多的点重复这个过程。 - Jonas Wilms

6

Google Delaunay 三角剖分. - meowgoesthedog

2

根据@spug的建议：Delaunay三角剖分具有最大化任何三角形最小角度的属性 - 也就是说，它们避免创建“长而瘦”的三角形（只要可能）。 - j_random_hacker

1

说实话，这个示例图像不是德劳内三角剖分，因此如果重复该过程将不会生成“如下所示”的图像，如果这很重要的话。 - samgak

@samgak 嗯，我想要的只是它看起来好看...为此，Delaunay 三角剖分应该可以胜任 :) - Anton Ballmaier

2个回答

0

这个问题可以不用三角测量来解决，类似于第二种方法。只有生成新的点才会导致越来越凹的图案，但是如果在添加新的点之间连接那些尚未连接但可以连接的点（也就是说，存在一个点它们都连接到，而且新的线段不会与其他线段相交）（添加一个新的三角形），就不会出现这种情况。（在我看来，最好只在一定长度限制下添加这样的线段。）

- FKris

1

你的回答可以通过提供更多的支持性信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

一个好的解决方案是从随机点（使用您喜欢的分布）开始，然后应用一些三角剖分算法。其中，Delaunay三角剖分是一个很好的选择，因为它具有较低的计算复杂度和代码可用性。