等距正交网格Delaunay三角剖分（计算抛物面系数） [英] Regularly spaced orthogonal grid Delaunay triangulation (Computing the paraboloid coeficients)

问题描述

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

鉴于数据大小相对较大（1000x1200三角剖分点），并且Qhull算法不知道我的额外正交条件，因此三角剖分相对较慢（25秒

因此，我想手动构造一个Delaunay三角剖分，并将每个已知的四边形细分为两个三角形。我知道这并不总是会导致有效的Delaunay三角剖分（例如，当x和y步长显着不同时），但是就我而言，我非常有信心细分方法会产生良好的三角剖分。

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

在这种情况下，我有x和 [-1、1.33、3.67、6] 和 [2、4.5、7、9.5、12]



我目前正在将SciPy包装器用于Qhull，并且能够构造顶点和适当的邻居信息，但是很难定义 equations 属性（如：

$ b拍摄的图片
$ b

I'm trying to construct a Delaunay triangulation for the very specific case where the input x and y coordinates are orthogonal and relatively equidistant.

Given the data size is relatively large (1000x1200 triangulation points) and that the Qhull algorithm doesn't know about my extra orthogonal condition, the triangulation is relatively slow (25 seconds on my machine).

As such, I'd like to manually construct a Delaunay triangulation with each of my known quads subdivided into two triangles. I appreciate that this won't always result in a valid Delaunay triangulation (e.g. when the x and y step are significantly different), but in my case I'm fairly confident that the subdivision approach will produce a good triangulation.

In the following plot, I have labelled each of the triangles with an index, the initial vertex and vertex definition direction:

In this case I have and x and y coordinates of [-1, 1.33, 3.67, 6] and [2, 4.5, 7, 9.5, 12] respectively.

I'm currently using the SciPy wrappers to Qhull, and have been able to construct vertices and appropriate neighbor information, but am having difficulty defining the equations attribute (as briefly mentioned at http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.ConvexHull.html).

Essentially, I believe these values are parameters of each triangle's normal to the paraboloid defined by the paraboloid_scale and paraboloid_shift attributes, but cannot come up with the magic numbers suitable for interpretation by Qhull. There should be n_dimensions + 1 values per vertex and there is code in SciPy which computes the distance of each vertex from a given point:

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]

So my questions are:

• Have I interpreted the equation attribute correctly?
• Is there a tool out there already which does this for me?
• Can I compute the equation parameter values given my orthogonal and mostly-equidistant case without going through Qhull?

解决方案

To compute a 2D Delaunay triangulation, qhull lifts the 2D points in 3D, onto a paraboloid, then compute the lower convex hull of those 3D points, and the 2D Delaunay triangulation is the projection in the 2D plane of that 3D lower convex hull.

See that image taken from here:

For each face of the 2D Delaunay triangulation, the corresponding 3D hyperplane is the 3D plane that passes through the three lifted 3D points. If the triangulation is Delaunay, that hyperplane corresponds to an empty circle in 2D. See that image taken from here:

这篇关于等距正交网格Delaunay三角剖分（计算抛物面系数）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！