得到形成三角形的最近点

Ric*_*o-E 9 .net c# geometry mesh

在此输入图像描述

我在2D中有一些点(蓝色).

我希望得到这三个点,它们以这种方式形成一个三角形,点D(红色)位于这个三角形内.如果没有这样的三角形,则可以抛出异常.

所以对于上面的图片我想得到黑点:

在此输入图像描述

到目前为止我做了什么:我以为我可以通过它们与D的距离来命令点数,而不是从排序列表中取出前三个点.但问题是,它可能是,这三个最近的点形成一个三角形的并没有包含点d.如下图所示:

在此输入图像描述

除了得到错误的点之外,我无法确定天气与否,D位于找到的点的凸包中,因此如果存在包含点D的三角形.这就是我遇到困难的地方.

Bar*_*zKP 2

正如TaW的评论中正确指出的那样,以下基本形式的算法并不总是能找到最佳解决方案或根本没有解决方案,因为它从两个最近点开始贪婪。

但这可以通过重复算法来解决:如果找不到三角形,您可以忽略第一个最近的点来重复它。

如果您没有很多点,您可以始终针对不同的起点重复该算法,以确保找到最佳解决方案。

1)找到距离D最近的点,我们称之为A

2)找到距离D第二近的点,我们称之为B

3)找到穿过DA的直线方程,我们称之为L1(缺失点必须在L1的另一侧而不是B

4)找到穿过DB的直线方程,我们称之为L2(缺失的点必须在L2的另一边而不是A

5) 过滤其余点:仅保留位于L1B另一侧的点,以及位于L2A另一侧的点

6)如果没有这样的点,则抛出异常(或以不同的起点重复)

7)否则找到最接近的一个,我们称之为C

8) 结果是三角形ABC

在此输入图像描述

补充笔记:

如果这个方程的坐标给出不同的符号,则两个点位于直线的不同侧(XYZ是直线方程系数,通常使用ABC但我不想将它们与点标签混淆多于):

公式1

通过坐标为(V1x, V1y)(V2x, V2y)的两点的直线方程可以通过以下公式找到:

公式2

给出了以下线性方程系数公式:

公式3

公式4

公式5