标签: delaunay

我需要从一组点创建一个三角形网格。该集合的点数很少，因此不需要快速或优化（我最多处理 100 点）。网格需要是受约束的“delaunay 三角剖分”。在下图中，我（在左侧）显示了我开始的一组点（蓝色和红色点）。我也知道这些点之间的联系（黑色轮廓）。网格需要看起来像右侧的示例（包括形成外部和内部三角形的灰色边缘）。

我不能使用图书馆。

我研究了许多不同的算法。它们很多，很容易混淆。我想知道是否有一种简单且希望更简单的算法可以用来生成右侧的网格？蛮力方法很好（ps：我可以进行 Delaunay 三角剖分）。

我正在阅读有关Delaunay (scipy)的内容的文章并发现了代码：

import numpy as np\npoints = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])\n\nfrom scipy.spatial import Delaunay\ntri = Delaunay(points)\n\nimport matplotlib.pyplot as plt\nplt.triplot(points[:,0], points[:,1], tri.simplices.copy())\nplt.plot(points[:,0], points[:,1], \'o\')\nplt.show()\n

据我了解，单纯形是三角形到更高维度的推广。

我不明白下面代码的含义，希望帮助理解它：

# Point indices and coordinates for the two triangles forming the triangulation:\n\ntri.simplices\narray([[3, 2, 0],\n       [3, 1, 0]], dtype=int32)\n\npoints[tri.simplices]\narray([[[ 1. ,  1. ],\n        [ 1. ,  0. ],\n        [ 0. ,  0. ]],\n       [[ 1. ,  1. ],\n        [ 0. ,  1.1],\n        [ 0. ,  0. …

大多数迭代算法需要一个初始的空三角形来让球滚动。似乎一个常用的技巧就是将超级三角形与点集相比变得非常大。

但根据“数值食谱：科学计算的艺术”：

“...如果距离仅仅是有限的（到边界点），则构造的三角剖分可能不太符合德劳内。例如，在不寻常的情况下，它的外边界可能会略微凹入，具有直径数量级的小负角的“真实”点集除以到“虚构”（边界）点的距离。

那么有哪些选项可以用无穷远处的点来增强笛卡尔坐标，而不必将所有输入转换为不同的坐标系，例如齐次坐标？这些点如何与通常的几何谓词 CCW 和 Incircle 相吻合？

内圆 (a,b,c) 无穷大 -> 假。假设 a,b,c 是有限的。

但是当 a,b,c 之一是无穷远点时呢？圆会变成半平面，然后测试变成逆时针检查吗？如果外接圆上有 2 个或更多点是无限的怎么办？圆是否扩展成一个完整的平面导致测试总是产生真？CCW呢？你如何根据一条在无穷远处有一个或多个点的线对一个点进行分类？

我已经绘制了n随机点（黑点）并使用了 delaunay 三角剖分，现在我想插入m随机评估点（红点），所以我需要计算评估点位于哪个三角形内。

计算三角形每个点的顶点的方法是什么？

我正在尝试使用scipy.spatial.Delaunay函数复制由Python中的Matlab delaunayn函数执行的N维Delaunay三角剖分.然而,虽然Matlab函数给了我想要和期望的结果,但是scipy给了我不同的东西.考虑到两者都是QHull库的包装器,我发现这很奇怪.我假设Matlab在其调用中隐式设置了不同的参数.我试图在两者之间复制的情况可以在Matlab的文档中找到.

设置是在中心有一个点,如下所示.我提供的蓝线有助于形象化,但它们没有任何目的或意义.

我期望的三角测量结果是12个单纯形式(在Matlab示例中列出),如下所示.

然而,这个python等效产生"额外"的单纯形.

x = np.array([[-1,-1,-1],[-1,-1,1],[-1,1,-1],[1,-1,-1],[1,1,1],[1,1,-1],[1,-1,1],[-1,1,1],[0,0,0]])
simp = scipy.spatial.Delaunay(x).simplices

返回的变量simp应该是一个M×N数组,其中M是找到的单纯数(对于我的情况应该是12),N是单数中的点数.在这种情况下,每个单形都应该是四面体,意味着N是4.

我发现的是,M实际上是18,额外的6个单纯形不是四面体,而是立方体的6个面.

这里发生了什么？如何将返回的单纯形式限制为仅仅是四面体？我用这个简单的案例来证明这个问题,所以我想要一个不适合这个问题的解决方案.

编辑

感谢Amro的回答,我能够解决这个问题,我可以在Matlab和Scipy之间找到一个简单的匹配.有两个因素在起作用.首先,正如所指出的,Matlab和Scipy使用不同的QHull选项.其次,QHull返回零容量的单纯形.Matlab删除了这些,Scipy没有.这在上面的例子中很明显,因为所有6个额外的单纯形都是立方体的零体积共面面.可以使用以下代码在N维中删除它们.

N = 3 # The dimensions of our points
options = 'Qt Qbb Qc' if N <= 3 else 'Qt Qbb Qc Qx' # Set the QHull options
tri = scipy.spatial.Delaunay(points, qhull_options = options).simplices
keep = np.ones(len(tri), dtype = bool)
for i, t in enumerate(tri):
    if abs(np.linalg.det(np.hstack((points[t], np.ones([1,N+1]).T)))) < 1E-15:
        keep[i] = False # Point is coplanar, we don't want …

我正在尝试使用该对象处理一些数据集scipy.spatial.Delaunay。但问题是我无法设置最大三角形边长。我想做一些类似如何在德劳内三角剖分中设置三角形边的最大长度？，但是在Python中

无论如何，是否可以使用 Delaunay 三角剖分中的某个点来获取所有单纯形/三角形scipy.spatial.Delaunay？

我知道有一个find_simplex()函数，它只返回一个点所属的 1 个三角形，但我想获取它所属的所有三角形。

所以在这个例子中，当我find_simplex()对点 6 执行操作时，它只返回三角形 2，但我希望它返回三角形 1、2、3、4、10 和 9，因为点 6 是所有这些三角形的一部分三角形。

任何帮助，将不胜感激！

我了解如何在 2d 点中使用 delaunay 三角剖分？
但是如何在 3d 点中使用 delaunay 三角剖分呢？
我的意思是我想生成表面三角形网格而不是四面体网格，那么如何使用 delaunay 三角剖分来生成 3d 表面网格？
请给我一些提示。

spatial导入的包Scipy可以测量指定点之间的欧几里德距离。是否可以使用Delaunay包装返回相同的测量值？使用df下面的方法，按 分组测量所有点之间的平均距离Time。但是，我希望使用 Delaunay 三角测量来测量平均距离。

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay

df = pd.DataFrame({
    'Time' : [1,1,1,1,2,2,2,2],                  
    'A_X' : [5, 5, 6, 6, 4, 3, 3, 4], 
    'A_Y' : [5, 6, 6, 5, 5, 6, 5, 6],                         
        })

def make_points(x):
    return np.array(list(zip(x['A_X'], x['A_Y'])))

points = df.groupby("Time").apply(make_points)

for p in points:
    tri = Delaunay(p)
    ax.triplot(*p.T, tri.simplices)

可以使用下面的方法测量所有点之间的平均距离，但我希望包含 Delaunay。

 avg_dist = (df.groupby(['Time']) …

我有一个多面体，面点（对于每个面）基本上是共面的，但 CGAL 说它们不是，这是有道理的，因为这些点是从文件中读取的，并且只有 14 个有效数字，因此它们不会完全共面. 有没有办法考虑假设面点共面的容差，以便不具有某些 1e-17 阶的体积的镶嵌？例如，如何告诉 CGAL 说 (0, 0.0000) 和 (1, 0.0001) 在同一行？甚至有可能吗？

目前，我只是在计算体积后忽略了条子，并得到了一个不错的非退化 tets 的三角剖分（当然，根据 CGAL 标准，所得的船体不会是凸面的），我将其用作分区来集成多面体上的函数。如果这是最快的方法，我很高兴，是吗？我正在使用 EPIC 内核。

感谢任何提示或参考，因为我对 CGAL 还很陌生。谢谢。