问题标签 [delaunay]

我希望计算与点集的 Delaunay 三角剖分相关的 Voronoi 单元的面积，而无需将 Delaunay 三角剖分明确转换为 Voronoi 图。因为我只关心 Voronoi 单元的区域，所以我想避免显式构建 Voronoi 数据结构的成本。这可能吗？Delaunay三角剖分/圆与双Voronoi单元区域之间是否存在任何关系？谢谢，

菲利普

我正在尝试实现 Bowyer-Watson 算法以生成平面中一组点的 Delaunay 三角剖分。该算法假设存在边界超三角形，但也提到了一些替代方案，例如保持点集的凸包。

因此，当我们决定通过在增量算法中假设凸包来产生点的 delaunay 三角剖分时，如果点位于凸包之外，我们应该从该点绘制顶点到凸包上包含面的所有顶点从该点可见的船体。

我想知道我该如何解决这个问题？我是否应该最初生成所有点的凸包，或者像在增量方法中一次添加一个点一样，我是否应该以 DCEL 的形式维护一个凸包？

编辑：在上图中，如果我的点 P 位于平面中一组点的凸包之外，我需要计算从该点可见的包的边缘。[船体的绿色边缘]

我希望这张图片有助于澄清这个问题。

提前致谢

我在 Ubuntu 11.04 上使用 NetBeans 7.1，并希望使用 OpenCV 从一组点中获取三角形。我按如下方式构建 Delaunay 三角剖分。

那部分似乎工作正常。它运行并且生成的存储看起来像这样。

storage 0xb287a90
signature 1116274688
bottom 0x2a2d57a0
prev 0x0 next 0x2a2e5730
top 0x2cc947d0
prev 0x2cc84840
next 0x0 parent 0x0 signature
bottom
top
parent
block_size
free_space
block_size 65408
free_space 0

我在这里查看了这些函数的文档，但找不到任何用于提取三角形的函数。

如果有人能告诉我如何提取三角形，我将不胜感激。

彼得。

使用这个程序中找到的voronoi/delaunay图生成库，它基于Fortune的算法的原始实现，以一组随机点作为输入数据，我能够得到以下输出数据：

1. 来自Delaunay Triangulation的边列表，这意味着对于每个输入点，我可以看到哪些输入点是它的邻居。它们似乎没有任何特定的顺序。
2. 来自Voronoi 图的顶点对列表，我可以用它一次绘制一条线的 Voronoi 图。同样，显然没有特定的顺序。
3. 一个未命名的点对列表，似乎与 2 相同，但顺序不同。
4. 在 Voronoi 图中形成的顶点列表，显然也没有特定的顺序。

这是使用此库对我的程序进行测试运行的数据示例：

虽然如果我只需要绘制 Voronoi 和 Delaunay 图，上述数据就足够了，但对于我尝试使用这些图进行的实际工作来说，这些信息还不够。我需要的是一个由 Voronoi 顶点形成的多边形字典，由每个多边形围绕的输入点索引。优选地，对于每个多边形，这些点将按顺时针顺序排序。

有了上述信息，我可以隐式地将数据分配给每个区域，必要时将数据分配给角点，告诉哪些区域共享边（使用 Delaunay 边），并进行相应的分析。

简而言之，我如何使用可用的数据来组合一个字典，其中键是输入点之一，由该键索引的数据是形成周围多边形的 Voronoi 顶点的列表？或者，这些信息是否隐含在我获得的数据中？

我知道 MST 是 delauny 三角剖分的一个子集，但它如何帮助找到最小生成树？当我对 MST 使用 delauny 三角剖分的边缘时，这意味着什么？这与在找到 MST 之前不对一组点进行三角测量有何不同？

我有一组 2D 点，每个点都有一个关联的 id。（例如，如果点存储在数组中，则 id 是每个点的索引 0,....,n-1 ）。

现在，我创建了这些点的 Delaunay 三角剖分，并希望列出所有有限边。对于每条边，我希望得到由相应的 2 个顶点表示的点的 id。示例：如果点 0 和点 2 之间有一条边，则为 (0,2)。这可能吗？

我想在 MATLAB 中使用二维的 delaunay 函数生成三角形网格。所以我声明了 X- 和 Y- 值并设置 tri=delaunay(X,Y)。然后我使用 triplot 来绘制它。然而，tri 给了我什么？它会给我的每个三角形一个特殊的编号吗？在阅读了一些 MATLAB 教程后，我仍然不明白。

我已经实现了 Domiter 和 Zalik 使用的扫描线方法，以在 Java 中为 2D 空间中的一组点生成约束 Delaunay 三角剖分。我想确保我开发的代码真正适用于n随机生成的点和k其中的约束边。

现在使用通用策略，我想从一组n顶点中选择一个随机点，然后选择第二个随机点并在它们之间有一条边可能不起作用，因为我从受约束的 Delaunay 三角剖分的定义中了解到约束边是平面直线图的边。因此它们是不相交的。如果这些点是随机选择的，则可能必须执行检查以确定它们不会产生相交约束。这种方法可能根本没有效率。

因此，我想知道是否有人知道随机生成约束的有效策略。

提前致谢。

我需要编写一些关于计算几何的代码并使用openMP将它们并行化。到目前为止，我已经完成了凸包和最近的一对点。我需要编写delaunay三角剖分和征服代码。但我没有太多时间。我读了如果可以计算凸包，则可以轻松实现delaunay三角剖分。因此，如果有人可以为我提供DT的串行代码或至少让我知道如何从凸包生成delaunay三角剖分，我可以编写代码并并行化尽快。

给定一个任意点 P，并假设我可以查找按距离排序的附近（未划分网格）点，是否有可能有效地确定形成包含 P 的德劳内三角形的三个附近点？如果是这样，怎么做？