Tag: 三角剖分

Delaunay三角剖分中没有边缘的矩形约束

我正在使用三角测量库来计算一些大边界内的一组矩形的约束Delaunay三角剖分。 该算法返回所有边，但也在定义约束的矩形内添加边。 我希望能够在任何作为约束的矩形内创建没有边的图形（当然除了大边界）但是在给予我的三角测量中删除这些边需要比O（nlog）更长的时间（n））时间至少，这对我需要的东西不好。 我要问的是，是否有任何快速方法可以让CDT保持边缘不会出现在某个多边形内？ 我希望矩形没有边缘，但我不知道如何快速做到这一点。 如果这有帮助，我使用的库是Marcello Kallmann的TriPath，它是用c ++（ http://graphics.ucmerced.edu/software/tripath/ ）编写的。 我的应用程序是Java，我正在使用JNI。 编辑：根据要求，这里有一些图像，以帮助您想象我想要描述的内容。 该CDT是以黑线为约束而构建的。 如您所见，每个约束边都是矩形的一部分。 蓝线是不受约束的Delaunay边缘。 我试图从黑色约束矩形中删除任何蓝色无约束Delaunay边。