问题标签 [delaunay]

我有大约 50,000 个 3D 数据点，我从新的 scipy 运行 scipy.spatial.Delaunay（我使用的是 0.10），这给了我一个非常有用的三角测量。

基于：http ://en.wikipedia.org/wiki/Delaunay_triangulation （“与 Voronoi 图的关系”部分）

...我想知道是否有一种简单的方法可以到达这个三角剖分的“双图”，即 Voronoi Tesselation。

有什么线索吗？我在这方面的搜索似乎没有显示预建的 scipy 函数，我觉得这几乎很奇怪！

谢谢，爱德华

我正在尝试实现一种主动外观模型（AMM），并且在我需要获得面部三角网格的步骤之一上，例如：

Delaunay 三角剖分似乎非常适合这项任务（如果有更好的选择，请纠正我），并且 OpenCV 有C API。但是有用于 Delaunay 三角测量的C++ API吗？当然，如果真的没有 C++ API，为 C 版本编写包装器并不是什么大不了的事，但这可能只是我对 API 的了解，而不是 API 本身。在这种情况下，我肯定会更喜欢原生 OpenCV 实现。

我想使用 Delaunay Triangulations 计算城市之间的距离。我有二十个城市的经度和纬度，我想计算它们之间的距离，但是我在弄清楚如何从三角测量中提取距离信息时遇到了一些麻烦。到目前为止，我已经使用了 deldir()（来自 deldir 库）。请参阅下面的代码。

我很确定在“尝试”的某个地方存储了由 deldir 计算的点之间的距离，但我只是不知道在哪里。我尝试通过计算距离并在 $ 元素中查找值来解决这个问题，但我找不到它们。对我来说，使用这些信息的最佳方法是，如果我可以将绘图上每条线的长度绘制到每条单独的线上，那么我可以手动计算所有城市之间的距离。

谢谢你的帮助！

我有一组带有（X，Y，Z）坐标的样本点。我使用 Delaunay Triangulation 从它们生成不规则网络，然后我使用线性插值以固定值（例如 90、95、100、105）绘制等高线。问题是我需要用另一种算法生成平滑的轮廓线。我已经搜索了一段时间，发现我需要使用像克里金这样的东西，但我不太擅长数学来从纯数学关系中实现算法。此外，我似乎无法在任何地方找到该算法的实现或解释。谁能帮我找一个？另外，我对所选算法是否正确？还有其他更容易实现的吗？请注意，我不关心精度。

https://dl.dropbox.com/u/15926260/ex.png

PS 我已经在 Surfer 中绘制了一个图，显示了我正在寻找的结果。右侧是我使用三角剖分和线性插值所做的，左侧是我需要使用不同算法绘制的（在 Surfer 中使用了克里金法）。抱歉拼写错误，但我不是母语人士。

谢谢！

我想知道在轮廓或凸包上使用 opencv C++ / C api 进行 CDT（约束延迟三角测量）的方法。

我的问题类似于

C++-ObjC OpenCV 约束 Delaunay

我想计算 Voronoi 及其对偶 Delaunay 三角剖分。我正在使用 Watson Bowyer 算法。之后我的目标是计算 alpha 形状（凹壳）。所以我需要快速访问给定点的voronoi单元，邻居......

你的 Voronoi/Delaunay 算法使用了哪些数据结构？我曾想过使用带有联合查找操作的不相交集数据结构，这样我就可以“绑定”到一个父节点，原始数据集中的点 p，Vp 中的点集。然而，Voronoi 图中的一个点“属于”几个 Voronoi 单元。

你有什么建议，或者你能暗示一些好的参考吗？

问候。

我正在用半边数据结构编写 Python delaunay 三角剖分。

此外，在三角测量算法中，我尝试只存储半边。我从边列表中检索三角形。

但是，这很多余，对吧？我有比描述三角形所需的更多的边，因为一个三角形由一个边定义，并且可以轻松通过，因为每个边都有指向下一个的指针。

1/ 是否可以为 delaunay 实现仅存储半边列表的 Watson 算法？以后会不会很难走过去？

在 Watson 确定腔内边缘的算法步骤中，我想在边缘上行走并找到位于三个以上不同半边末端的边缘顶点。

2/ 这个属性“多于两条边在这个顶点处结束”是否是在 Bowyer Watson 算法中丢弃边的正确标准？

为了穿过网格，我会在每个半边上进行迭代。所以，我是一个接一个地工作，而不是一个接一个三角形的工作。我在不使用“下一个”属性的情况下穿过网格，这听起来不太好。

3/ 遍历网格中的三角形的方式是什么，存储为边列表？或者如何更好地存储网格以便更轻松地通过它？

谢谢！

我一直在寻找这个问题的答案，但找不到任何有用的东西。

我正在使用 python 科学计算堆栈（scipy、numpy、matplotlib），我有一组二维点，我使用scipy.spatial.Delaunay.

我需要编写一个函数，给定任何点a，将返回所有其他点，这些点是任何单纯形（即三角形）a的顶点，也是（a三角剖分中的邻居）的顶点。但是，scipy.spatial.Delaunay（here）的文档非常糟糕，我一生都无法理解单纯形是如何指定的，否则我会继续这样做。即使只是解释 Delaunay 输出中的neighbors,vertices和vertex_to_simplex数组是如何组织的，也足以让我继续前进。

非常感谢您的帮助。

我需要计算多边形的三角形。多边形可以包含孔。而 Req 是一种有效的方式。所以我认为我需要约束德劳内三角测量。

我必须在 c# 中做到这一点，只需要计算而不是绘图什么的。

poly2tri看起来不错，但 idk 它对我不起作用：S

无论如何我需要帮助。我如何计算这些三角形？（如果你最好的报价是poly2tri，我可以解释我的问题）

I have a n:2 Matrix with points(x,y) found from dots in a rectangular calibration pattern. I like to sort these points row by row. I have sorted these points with lexsort but the distortion from the camera is too big so that y-coordinates will be overlap.

Is there a way to sort this with help of a delaunay pattern going a long the rows?