问题标签 [delaunay]

构建三角剖分的代码：

之后，使用以下点之一进行查询：

获得结果后，您必须检查该点是否落在：

• 刻面
• 边缘
• 顶点
• 在定义的三角剖分/矩形之外

在这种情况下，它是一个顶点：

但是，我的两种方法都失败了。在前 3 行中，我尝试查看是否locate在参数上放置了正确的边缘。它没有，我遇到了分段错误。在第二个块上，我尝试访问结构first中的元素，CvSubdiv2DPoint但它也不起作用——分段错误。我找不到点，first也不能使用它迭代其他边缘。

原因CvSubdiv2DPoint是无用的，因为为了遍历结构并实际找到三角形，我需要 a CvSubdiv2DEdge，但由于我无法从点转换为边，因此函数的结果是无用的。

我可能忽略了一些东西，但对我来说它似乎被打破了。这是文档。有什么想法吗？

我正在寻找一个 .NET 实现，它从一组点构建 Delaunay 三角剖分。

我已经测试了几个实现，但它们都只适用于少量点（最多 20,000）。

我需要能在合理时间内处理 500,000 点的东西。

如何在 CGAL（C++）中获取/迭代 2D delaunay 图中的所有边？

例如，在 MATLAB 中，这只是边（dt）。

嗨，有人知道如何delaunay3()在 Octave 函数的输出中可视化四面体吗？

http://www.obihiro.ac.jp/~suzukim/masuda/octave/html3/octave_151.html

在 MATLAB 中，这个可视化是用tetramesh()函数完成的，但 Octave 没有内置这个函数！

该链接确实提到了triplotandtrimesh函数，但它们只创建三角形，而不是四面体。

我是 CGAL 的新手，我敢肯定我的问题很简单。

我正在尝试使用 CGAL 进行一些 Delaunay 三角测量。我在球体上有一个带有 N 3D 点的网格，我想使用这些点作为三角形的顶点对球体进行三角剖分。我只需要得到一个生成的三角形的顶点列表，如下所示：

id_triangle1 vertex_1 vertex_2 vertex_3 id_triangle2 vertex_1 vertex_2 vertex_3 ......

我这样做是为了执行三角测量：

我遇到的问题是我不知道如何得到三角测量结果。我想出了如何获得 face_iterator，但我不知道从那里做什么：

我不确定迭代三角形是否正确，如果是......三角形=面？？¿，我的意思是，每个迭代器位置只有一个三角形¿？如何正确获取每个三角形的 x、y 和 z？¿

我知道从 Voronoi 镶嵌计算 k 最近邻的集合相对容易。反过来的问题呢？我已经有了一组 k 最近邻（3D），我想计算 Voronoi 单元的体积和中心。直观地说，应该有一个 O(n) 算法可以做到这一点，对吧？

有没有人在某处看到过这样的事情？

提前致谢

PS：我假设没有 Voronoi 单元的边数超过 k （这种关于点位置的先验知识可能使计算 O(n) 中的图表成为可能，与维度无关）。

PPS：我进一步假设对于给定的点，Voronoi 单元的顶点属于 kNN 的集合（见下面的评论）。

在比较 scipy 的（0.9.0）和 matplotlib 的（1.0.1）Delaunay 三角测量例程时，我注意到一个无法解释的行为。我的点是存储在numpy.array([[easting, northing], [easting, northing], [easting, northing]]). Scipy 的边缘缺少我的一些观点，而 matplotlib 的都在那里。有解决办法，还是我做错了什么？

我在 OpenCV 2.3.1 中成功实现了轮廓的 Delaunay 三角剖分。

使用 cvPointPolygonTest 我可以得到凸包中的所有三角形，然后我尝试在三角形质心上执行另一个 cvPointPolygonTest 以了解它们是否在主轮廓中，这样我就可以对轮廓进行约束三角剖分。

但是，它不能很好地工作，因为一些三角形（例如，一个走路的人，他的两条腿很远）“越过”一个洞。

有谁知道执行约束三角测量的方法。我想到了convexityDefects，但无法理解如何从这个开始。

提前致谢 ！

本

实际上，这不是凸包缺陷问题，而是三角剖分问题。这张图片会告诉你麻烦：

特别是在三角包的底部，您可以看到三角剖分在轮廓之内和之外，因为 OpenCV 正在对凸包进行三角剖分。我想找到一种方法来对轮廓本身进行三角测量。

我发现了一些关于在轮廓本身中添加 Steiner Points 的想法，但找不到从 OpenCV 开始的地方。

我的想法是：

• 测试三角形是否在轮廓内和外；
• 如果为真：获取交点；
• 并将其添加到 cvSubdiv2D。

我说得对吗？

感谢您的耐心和您的回答！

我试图在给定的数据集中找到边缘相邻的 Voronoi 区域的点。我是计算几何的新手，但从网上阅读来看，使用 Delaunay 镶嵌似乎是一种简单的方法。这个 PDF甚至有一个引理指出

引理 2.4 S 的两个点由一条 Delaunay 边连接如果它们的 Voronoi 区域是边相邻的。

所以，我发现我的数据集的 delaunay 细分为

但是现在，当我将此与该数据集的 voronoi 图一起绘制时，我发现 delaunay 边返回的连接点的区域实际上并不相邻。

这是我用来将 Voronoi 和 Delaunay 绘制在一起的代码：

这是输出：

作为问题的一个例子，看图右端的点 X 连接到左下角附近的点 Y。

另一个例子是在这个 SO question - 点 1 连接到 2 和 3，即使它们不相邻，而且即使扩展到无穷大，1 和 2 似乎也没有任何方式可以共享一条边。这个问题实际上是促使我用上面的代码测试 delaunayn 输出的原因。

为什么会发生这种情况，我如何真正获得我需要的边缘相邻区域？

注意：要查看完整尺寸和清晰度的图像，请右键单击并选择“查看图像”或类似选项。

我有一个TriRep带有三角剖分的对象，我想pointLocation在对象上使用来查找这些点是否在三角形内。但是pointLocation是为类定义的方法，DelaunayTri它是 的子类TriRep。

所以我想问一下TriRep对象是否可以转换为DelaunayTri用于pointLocation？