java - 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 作为间隙。