image - 如何将点变成三角形？

Question

我正在尝试以编程方式制作所有三角形的图像。我认为解决这个问题的方法是随机选择一些点，然后将它们“连接”成三角形。问题是我无法想出一个连接它们的好方法。

我想做的一件事是选择一个随机点开始（点 1），然后找到最近的点（点 2），然后“连接”它们。然后，我会通过选择与点 1 和点 2 的组合距离最小的点来找到最近的第三点。这会给我一个三角形。我可以重复这个直到我有一堆三角形。这里的问题是三角形将是分开的（它们不会连接）。

我是不是在愚蠢地想这些？有没有更简单的方法来做到这一点？

Answer 1

您正在寻找的是Delaunay 三角测量！

它的基本作用是将三个点组合在一个三角形中，如果通过它们的圆不包含任何其他点，并且它有效地做到了。可能会有点在一条线上的特殊情况，或者在同一个圆上超过 3 个点。

Answer 2

我认为您在开始时走在正确的轨道上，将第一步视为创建 3 条边，然后取每条边并制作一个新三角形，每个边上都有一个额外的点。理论上，每条边应该有 2 个三角形。