我正在使用一个三角剖分库来计算一些大边界内的一组矩形的约束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作为间隙。
关于java - Delaunay三角剖分中的矩形约束，其中没有边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21706947/