如何将点转换为三角形?

Has*_*san 2 algorithm image

我正在尝试以编程方式将三角形的图像全部粘在一起.我认为我接近这个问题的方法是随机选择一些点,然后"连接"它们来制作三角形.问题是我无法想出一个连接它们的好方法.

我要做的一件事就是选择一个随机点开始(第1点),然后找到最近点(第2点),然后"连接"它们.然后,通过选择距离点1和点2的组合距离最小的那个,我找到最接近的第三点.这会给我一个三角形.我可以重复这个,直到我有一堆三角形.这里的问题是三角形将是分开的(它们将不连接).

我愚蠢地过度思考这个吗?有更简单的方法吗?

Sha*_*baz 6

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

它基本上做的是,如果通过它们的圆圈不包含任何其他点,则将三个点组合成三角形,并且它有效地完成.会有一些特殊情况在一条线上有点,或在同一个圆上有超过3个点.