矩形约束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（n日志（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由马塞罗卡尔曼，它是用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是建立与黑线是限制。正如你所看到的，每个约束边是长方形的一部分。蓝线是无约束的德劳内边缘。我想，以消除任何蓝色的约束德劳内从黑约束矩形内的边缘。

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).

要选择一个足够小的间隙的一种方法是，以评估不小的矩形的三角测量，找到最小长度的边缘，并采取，比方说，该长度作为间隙的三分之一。

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屋！