Delaunay中的矩形约束无边的三角形 [英] Rectangular constraints in Delaunay Triangulation without edges within

问题描述

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

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside of the rectangles that define the constraints.

我想能够创建一个没有边作为约束的矩形（当然除了大边界之外），但是在给予我的三角剖分中去除这些边缘至少花费比O（nlog（n））时间更长的时间，并且对于我需要的时间不好。

I want to be able to create a graph without the edges within any of the rectangles that are the constraints (with the exception of the large boundary of course) but removing these edges in the triangulation that is given to me takes longer than O(nlog(n)) time at least and that's not good for what I need.

我要问的是，有没有任何快速的方法来获得一个CDT保持边缘出现在一个多边形？我想要的矩形是空的边缘，但我不知道如何快速这样做。

What I'm asking is, is there any quick way to get a CDT to keep edges from appearing within some polygon? I want the rectangles to be empty of edges but I'm not sure how to quickly do that.

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

In case this helps, the library I'm using is TriPath by Marcello Kallmann, and it is written in c++ (http://graphics.ucmerced.edu/software/tripath/). My application is in Java and I'm using JNI.

编辑：根据要求，这里有一些图像，以帮助您可视化我想描述。这个CDT是用黑线作为约束构建的。正如你所看到的，每个约束边是矩形的一部分。蓝色线是不受约束的Delaunay边缘。我尝试从黑色约束矩形内删除任何蓝色的不受约束的Delaunay边。

As requested, here's some images to help you visualize what I'm trying to describe. This CDT is built with the black lines being constraints. As you can see, each constrained edge is part of a rectangle. The blue lines are unconstrained Delaunay edges. I am trying to remove any blue unconstrained Delaunay edges from within the black constrained rectangles.

推荐答案

如果约束矩形不能重叠或包含彼此，建议在每个原始矩形内放一个稍小的矩形。内部和原始矩形之间的间隙应该足够小，使得没有未约束的边缘可能适合在原始矩形内而不与较小的矩形相交。然后，在进行三角测量之后，删除与这些较小矩形的任何顶点相邻的每个边。这样，你可以在O（1）的时间里找出边缘是否应该被删除，所以整个过程需要O（E）。

In case constrained rectangles cannot overlap or contain each other, I suggest putting a slightly smaller rectangle inside every original rectangle. The gap between inner and original rectangle should be small enough that no unconstrained edge could possibly fit inside an original rectangle without intersecting a smaller rectangle. Then, after triangulation is done, delete every edge that is adjacent to any of the vertices of those smaller rectangles. That way you'll be able to find out whether an edge should be deleted in O(1) time, and so the whole procedure will take O(E).

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

One way to choose a small enough gap is to evaluate the triangulation without smaller rectangles, find the edge of minimum length, and take, say, 1/3 of that length as a gap.

这篇关于Delaunay中的矩形约束无边的三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！