定期間隔的正交網格Delaunay三角測量（計算拋物面係數）

Question

我想爲輸入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]。

我目前正在使用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屬性？
• 有沒有工具可以幫我嗎？
• 我可以計算equation參數值給定我的正交和大部分等距的情況下沒有通過Qhull？

Answer 1

爲了計算二維Delaunay三角測量，qhull升降機在3D 2D點，到拋物面，然後計算這些3D點的下凸包，並且2D Delaunay三角剖分是在所述二維平面上的投影3D更低的凸包。

查看來自here採取圖像：

對於2D Delaunay三角剖分的每個面，對應的三維超平面是3D平面通過三個提升3D點通過。如果三角剖分是Delaunay，則該超平面對應於2D中的空圓。看到here採取圖片：