algorithm - 分而治之 Delaunay 三角剖分 - 合并时获得第一个（又名“基础”）边缘

Question

我正在尝试实现此处找到的 Delaunay Triangulation 的分而治之算法，但我遇到了问题。合并两个集合时，我应该找到它们之间的最底部边缘，它不会与图中已经存在的任何边缘相交。

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

我很确定，这些点中至少有一个必须是该边缘的一部分，但无论如何我都无法证明。

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

所以我正在寻找一种找到这个基础边缘的方法。任何帮助，将不胜感激。

标签： algorithmgeometrydelaunay

Answer 1

我很确定，我刚刚想通了。在获得具有最低 y 值的顶点后，我遍历了这两个集合并寻找两个顶点，它们位于由先前选择的顶点形成的线（或线上）下方，并且与它的距离最大。如果两点与直线的距离相同，我在左边的情况下取 x 值最大的那个，在右边的情况下取最小的那个。

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