定期间隔的正交网格德劳内三角剖分（计算抛物面系数）

Question

我正在尝试构建一个Delaunay三角剖分，其中输入的x和y坐标正交且相对等距。由于数据规模相对较大（1000 x 1200个三角剖分点），而Qhull算法不知道我的额外正交条件，所以三角剖分相对较慢（在我的机器上需要25秒）。因此，我想手动构建Delaunay三角剖分，其中每个已知的四边形都被细分为两个三角形。我知道这并不总是会产生有效的Delaunay三角剖分（例如当x和y步长差异显着时），但在我的情况下，我相当有信心细分方法将产生良好的三角剖分。在下面的图中，我用索引、初始顶点和顶点定义方向标记了每个三角形：

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

我目前正在使用SciPy包装器来Qhull，并已经能够构建顶点和适当的邻居信息，但是在定义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属性？
• 是否已经有工具可以为我完成这项工作？
• 在不通过Qhull的情况下，我能否计算出给定我的正交和几乎等距的情况下的equation参数值？

- pelson

Answer 1

要计算2D Delaunay三角剖分，qhull会将2D点在3D空间中映射到抛物面上，然后计算这些3D点的下凸壳，2D Delaunay三角剖分是该3D下凸壳在二维平面上的投影。请参考此处的图片。

对于2D Delaunay三角剖分的每个面，相应的3D超平面是通过三个映射后的3D点所组成的3D平面。如果三角剖分是Delaunay的，则该超平面对应于2D中的一个空圆。请参考此处的图片。

- lrineau