3

我正在尝试为输入 x 和 y 坐标正交且相对等距的非常特殊的情况构建 Delaunay 三角剖分。

鉴于数据量相对较大（1000x1200 三角剖分点）并且 Qhull 算法不知道我的额外正交条件，三角剖分相对较慢（在我的机器上为 25 秒）。

因此，我想手动构建一个 Delaunay 三角剖分，将我已知的每个四边形细分为两个三角形。我明白这并不总是会导致有效的 Delaunay 三角剖分（例如，当 x 和 y 步长明显不同时），但在我的情况下，我相当有信心细分方法会产生良好的三角剖分。

在下图中，我用索引、初始顶点和顶点定义方向标记了每个三角形：

细分图

[-1, 1.33, 3.67, 6]在这种情况下，我分别拥有 和 的 x和y 坐标[2, 4.5, 7, 9.5, 12]。

我目前正在使用 Qhull 的 SciPy 包装器，并且已经能够构造顶点和适当的邻居信息，但是在定义equations属性时遇到了困难（如在http://docs.scipy.org/doc/scipy-dev /reference/generated/scipy.spatial.ConvexHull.html）。

从本质上讲，我相信这些值是每个三角形与paraboloid_scale和paraboloid_shift属性定义的抛物面法线的参数，但无法得出适合 Qhull 解释的神奇数字。每个顶点应该有n_dimensions + 1值，并且 SciPy 中有代码计算每个顶点到给定点的距离：

dist = d.equations[isimplex*(d.ndim+2) + d.ndim+1]
for k in xrange(d.ndim+1):
    dist += d.equations[isimplex*(d.ndim+2) + k] * point[k]

所以我的问题是：

  • 我equation是否正确解释了该属性？
  • 是否已经有一个工具可以为我做到这一点？
  • 我可以在equation不经过 Qhull 的情况下计算给定正交和大部分等距情况的参数值吗？
4

1 回答 1

3

为了计算 2D Delaunay 三角剖分，qhull 将 3D 中的 2D 点提升到抛物面上，然后计算这些 3D 点的下凸包，2D Delaunay 三角剖分是该 3D 下凸包在 2D 平面中的投影。

查看从此处拍摄的图像：

吊装图

对于 2D Delaunay 三角剖分的每个面，对应的 3D 超平面是通过三个提升的 3D 点的 3D 平面。如果三角剖分是 Delaunay，则该超平面对应于 2D 中的空圆。查看从此处拍摄的图像：

空圆和超平面

于 2014-02-20T16:21:39.260 回答