无边Delaunay三角剖分中的矩形约束

Question

我正在使用一个三角剖分库来计算一组矩形在某个大边界内的约束Delaunay三角剖分。该算法返回所有边，但也在定义约束的矩形内部添加边。

我希望能够创建一个没有任何约束矩形内的边的图（当然，大边界除外），但在三角剖分中删除这些边至少需要超过O（nlog(n))的时间，这对我需要的是不好的。

我想问的是，有没有什么快速的方法来得到一个CDT来防止多边形中出现边缘？我希望矩形没有边，但我不知道如何快速做到这一点。

如果这有所帮助，我使用的库是Marcello Kallmann的TriPath，它是用C++编写的（http://graphics.ucmerced.edu/software/TriPath/）。我的应用程序是Java的，我使用的是JNI。

编辑：根据要求，这里有一些图像来帮助你将我试图描述的东西形象化。这个CDT是用作为约束的黑线构建的。如您所见，每个受约束的边都是矩形的一部分。蓝线是无约束的Delaunay边。我试图从黑色约束矩形中移除任何蓝色无约束Delaunay边。

Answer 1

如果受约束的矩形不能相互重叠或包含，我建议在每个原始矩形内放置一个稍微小一点的矩形。内部矩形和原始矩形之间的间隙应该足够小，以至于在不与较小的矩形相交的情况下，任何无约束的边缘都可能适合于原始矩形。然后，在三角剖分完成后，删除与那些较小矩形的任何顶点相邻的每条边。这样，你就可以在O(1)时间内找出一条边是否应该被删除，所以整个过程需要O(E)。

选择足够小的间隙的一种方法是在没有较小矩形的情况下评估三角剖分，找到最小长度的边，并将该长度的1/3作为间隙。