我一直在研究Delaunay 三角剖分（不是作业），我想到了以下问题：给定S平面上的一组点（基数为n）和一组三角形T（基数应为n-2） - 如何确定是否三角形设置T形成一个德劳内三角剖分DT(S)？
第一个问题是 Delaunay 三角剖分不是唯一的，因此再次为点集重建它并与三角形集进行比较不会给我们答案。此外，最优的 Delaunay 三角剖分算法很难实现（但是，使用像 CGAL 这样的库就可以了）。
假设我们知道如何检查三角形集是否是三角剖分（不一定是 Delaunay）。那么我们应该使用 Delanuay 三角剖分的定义：对于三角剖分中的每个三角形t，没有一点 inS严格位于 的圆周内t。这导致我们采用以下方法：
- 琐碎的方法。只需迭代
T，计算圆周并迭代S，检查点是否在圆周内。然而，这需要O(n^2)时间，这不是非常理想的。 - 迷人的方法。再次，迭代
T并计算周长。如果有一点s在圆周内，则表示它到圆周中心的距离小于半径。使用最近邻搜索结构S，我们将加快我们的算法。例如，简单的 kd-tree结构将我们引导到O(n log n)平均和O(n sqrt(n))最坏情况下的算法。 - 有没有人有更简单的想法？
现在让我们回到检查是否T是三角剖分的问题。诸如 的相等性S和三角形的顶点集之类的琐碎先决条件的执行速度不会比O(n log n). 剩下的——检查每两个三角形是否T在一个共同的面上相交，或者根本不相交。
T同样，我们可以通过一遍又一遍地迭代来做到这一点T，检查交叉点，但这是O(n^2)算法。- 让我们想想«三角形
t1和t2相交»是什么意思？如果它们的边相交或者如果一个三角形完全位于另一个三角形中，则它们相交。O(n log n)使用Bentley-Ottmann 算法可以及时解决所有边相交的问题（最坏的情况是O((n + k) log n)，其中k是交叉点的计数，但我们可以在找到第一个交叉点的那一刻停止算法）。此外，我们没有认识到一个三角形完全包含另一个三角形的情况，但我相信我们可以修改 Bentley-Ottmann 算法以保持三角形穿过扫描线而不是线段，正如我所说，这产生了我们的O(n log n)算法。但是，实现起来确实很复杂。 - 我考虑过迭代算法——让我们保持不相交（或仅通过边相交）三角形的结构（它应该与 kd-tree 非常相似）。然后我们尝试添加下一个三角形
t：首先检查t' 的任何顶点是否已经在其中一个三角形中——然后我们得到了一个交点。否则，添加t到结构中。但是，如果我们想要O(log n)或O(sqrt(n))有时间进行搜索和添加查询，我们必须平衡这个结构的高度，这对于 kd-trees 来说也太难了。
那么，有没有人知道这个问题的任何简单解决方案？