algorithm - 分而治之 Delaunay 三角剖分 - 合并时获得第一个(aka "base")边缘

Question

我正在尝试为发现的 Delaunay 三角剖分实现分而治之算法 here ，但我遇到了一个问题。合并两组时，我应该找到它们之间的最底部边缘，该边缘不与图中已有的任何边缘相交。

我的第一个问题是，最底部根本没有定义，而且不明显。很多文本，我读过，比如说，可以安全地使用两组中具有最低 y 值的顶点之间的边缘，但事实并非如此，如下图所示:

我很确定，这些点中至少有一个一定是那条边的一部分，但我无法证明这一点。

我不想根据图表检查每对边，因为对于较大的数据集，这可能需要很长时间。

所以我正在寻找一种方法来找到这个底边。任何帮助将不胜感激。

Answer 1

我很确定，我刚刚弄明白了。在获得具有最低 y 值的顶点后，我遍历了两个集合并寻找两个顶点，它们位于由先前选择的顶点形成的线下方(或线上)并且与它的距离最大。如果两点与线的距离相同，我在左侧集合中取 x 值最大的点，在右侧集合中取最小值。

这似乎工作得很好。这是因为我注意到，为了发生交点，该线下方需要有一个点，该点是与我们的底边相交的边的一部分。这样，我想我找到了与这两个集合相切的最低边缘，这意味着，如果我旋转这个集合，那么这条线是水平的，它下面不存在任何点。