正如TaW的评论中正确指出的那样,以下基本形式的算法并不总是能找到最佳解决方案或根本没有解决方案,因为它从两个最近点开始贪婪。
但这可以通过重复算法来解决:如果找不到三角形,您可以忽略第一个最近的点来重复它。
如果您没有很多点,您可以始终针对不同的起点重复该算法,以确保找到最佳解决方案。
1)找到距离D最近的点,我们称之为A
2)找到距离D第二近的点,我们称之为B
3)找到穿过D和A的直线方程,我们称之为L1(缺失点必须在L1的另一侧而不是B)
4)找到穿过D和B的直线方程,我们称之为L2(缺失的点必须在L2的另一边而不是A)
5) 过滤其余点:仅保留位于L1与B另一侧的点,以及位于L2与A另一侧的点
6)如果没有这样的点,则抛出异常(或以不同的起点重复)
7)否则找到最接近的一个,我们称之为C
8) 结果是三角形ABC

补充笔记:
如果这个方程的坐标给出不同的符号,则两个点位于直线的不同侧(X,Y,Z是直线方程系数,通常使用A,B,C但我不想将它们与点标签混淆多于):
通过坐标为(V1x, V1y)和(V2x, V2y)的两点的直线方程可以通过以下公式找到:
给出了以下线性方程系数公式: