Delaunay三角剖分中没有边缘的矩形约束
我正在使用三角测量库来计算一些大边界内的一组矩形的约束Delaunay三角剖分。 该算法返回所有边，但也在定义约束的矩形内添加边。
我希望能够在任何作为约束的矩形内创建没有边的图形（当然除了大边界）但是在给予我的三角测量中删除这些边需要比O（nlog）更长的时间（n））时间至少，这对我需要的东西不好。
我要问的是，是否有任何快速方法可以让CDT保持边缘不会出现在某个多边形内？ 我希望矩形没有边缘，但我不知道如何快速做到这一点。
如果这有帮助，我使用的库是Marcello Kallmann的TriPath，它是用c ++（ http://graphics.ucmerced.edu/software/tripath/ ）编写的。 我的应用程序是Java，我正在使用JNI。
编辑：根据要求，这里有一些图像，以帮助您想象我想要描述的内容。 该CDT是以黑线为约束而构建的。 如您所见，每个约束边都是矩形的一部分。 蓝线是不受约束的Delaunay边缘。 我试图从黑色约束矩形中删除任何蓝色无约束Delaunay边。
如果受约束的矩形不能重叠或相互包含，我建议在每个原始矩形内放一个稍小的矩形。 内部矩形和原始矩形之间的间隙应该足够小，使得没有无约束的边缘可能适合原始矩形而不与较小的矩形相交。 然后，在完成三角测量之后，删除与那些较小矩形的任何顶点相邻的每个边。 这样你就能够找出是否应该在O（1）时间内删除边缘，因此整个过程将采用O（E）。
选择足够小的间隙的一种方法是在没有较小矩形的情况下评估三角测量，找到最小长度的边缘，并将该长度的1/3作为间隙。