标签: delaunay

问题:从3D点生成网格(使用x,y和z坐标).

我所拥有的是3D空间中的点(使用x,y和z坐标),您可以在图像1中看到它.
输出的是图像2或图像3或图像4.简而言之,它将是网格.如果我有网格,可以提供它上面的材料.

我见过很多人都说Delaunay三角剖分或受约束的Delaunay三角剖分将帮助我进行网格生成,但我最常发现的是它在2D点(仅有x和Y坐标)中的实现.

但我的问题是:我从图像1中可以看到3D点.

Delaunay三角测量或受约束的Delaunay三角测量是否适用于3D点？如果是,那怎么样？或者我是否必须找到另一种从3D点生成网格的算法？

注意:这里可以找到关于2D点的Delaunay三角剖分的一个很好的解释

我正在寻找一个.NET实现,它从一组点构建Delaunay三角剖分.

我已经测试了几个实现,但它们都只适用于少量点(最多20,000个).

我需要能够在合理的时间内处理500,000点的东西.

我正在制作一个游戏,在那里我创建一个随机的省份地图(风险或外交).为了创建该地图,我首先生成一系列半随机点,然后计算这些点的Delaunay三角剖分.

完成后,我现在正在寻找创建点的Voronoi图表作为省边界的起点.此时我的数据(没有双关语)由原始的点系列和Delaunay三角形的集合组成.

我已经在网上看到过很多方法可以做到这一点,但是大多数方法都与Delaunay的衍生方式有关.我很想找到一些不需要集成到Delaunay的东西,但可以单独根据数据工作.如果做不到这一点,我正在寻找相对几何新手可以理解的东西,而不是最佳速度.谢谢!

我需要在一组点中找到"附近"的邻居.

上图中有10个点.红线是Delaunay三角剖分的边缘,黑色星标记边缘的中线,蓝线是Voronoi镶嵌.点1具有三个"近"邻居,即4,6和7,但不是2和3,它们几乎与边缘1-7一致,但距离更远.

识别近邻(或"好"边缘)的好方法是什么？看看这个图,在我看来,要么选择中点落在与Voronoi线交叉点的边缘,要么考虑作为"近"邻居那些触摸Voronoi单元的边缘可能是一个很好的解决方案(3-5的分类)可以去任何一种方式).有没有一种有效的方法来实现Matlab中的任何一个解决方案(我很乐意得到一个好的通用算法,然后我可以转换为Matlab,顺便说一下)？

我正在尝试使用CGAL做一些Delaunay三角测量.我使用其中一个CGAL样本来计算包含高度字段属性的三角测量.

我遇到的问题是我不知道如何得到最终的三角测量.我想出了如何获得face_iterator,但我不知道该怎么做.我希望得到的是每个三角形上3个点中每个点的点数组的索引.

我无法浏览所有嵌套模板:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_euclidean_traits_xy_3.h>
#include <CGAL/Delaunay_triangulation_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_euclidean_traits_xy_3<K> Gt;
typedef CGAL::Delaunay_triangulation_2<Gt> Delaunay;
typedef K::Point_3 Point;

int main()
{
    //initialize the points with some trivial data
    std::vector<Point> pts;
    pts.push_back(Point(1., 2., 3.));
    pts.push_back(Point(2., 2., 3.));
    pts.push_back(Point(1., 3., 3.));
    pts.push_back(Point(4., 2., 3.));    

    //create a delaunay triangulation
    Delaunay dt;
    dt.insert(pts.begin(), pts.end());

    //iterate through the faces
    Delaunay::Finite_faces_iterator it;
    for (it = dt.finite_faces_begin(); it != dt.finite_faces_end(); it++)
    {
        //What do I do here??
    }

    return 0;
}

我在3D中有大约50,000个数据点,我从新scipy运行scipy.spatial.Delaunay(我使用的是0.10),这给了我一个非常有用的三角测量.

基于:http://en.wikipedia.org/wiki/Delaunay_triangulation("与Voronoi图的关系"部分)

......我想知道是否有一种简单的方法来获得这种三角测量的"双重图形",即Voronoi Tesselation.

有线索吗？我在这里搜索似乎没有显示预制的scipy函数,我觉得这几乎很奇怪!

谢谢,爱德华

我想对带有孔的复杂(但不是自相交)多边形进行三角测量,以便生成的三角形全部位于多边形内部,完全覆盖该多边形,并遵守Delaunay三角形规则.

显然,我可以为所有点构建Delaunay三角剖分,但是我担心多边形的某些边缘不会被包含在生成的三角剖分中.

那么,这样的三角测量可能吗？如果是,我该怎么办？

以防万一 - 我需要它来构造多边形中轴的近似(我希望它可以通过连接所得三角形的所有圆周点来完成).

使用此程序中的voronoi/delaunay图生成库,该库基于Fortune 其算法的原始实现,使用随机点集作为输入数据,我能够获得以下输出数据:

1. Delaunay三角剖分的边缘列表,意味着对于每个输入点,我可以看到哪些输入点是它的邻居.它们似乎没有任何特定的顺序.
2. 来自Voronoi图的顶点对列表,我可以用它一次绘制一行Voronoi图.再次,显然没有特别的顺序.
3. 一个未命名的点对列表,它们似乎与2的列表相同,但顺序不同.
4. Voronoi图中形成的顶点列表,也显然没有特定的顺序.

以下是使用此库的程序测试运行的数据示例:

Input points:
0   (426.484, 175.16)
1   (282.004, 231.388)
2   (487.891, 353.996)
3   (50.8574, 5.02996)
4   (602.252, 288.418)

Vertex Pairs: 
0   (387.425, 288.533)  (277.142, 5.15565)
1   (387.425, 288.533)  (503.484, 248.682)
2   (277.142, 5.15565)  (0, 288.161)
3   (387.425, 288.533)  (272.213, 482)
4   (503.484, 248.682)  (637.275, 482)
5   (503.484, 248.682)  (642, 33.7153)
6   (277.142, 5.15565)  (279.477, 0)

Voronoi lines?: 
0   (279.477, 0)    (277.142, 5.15565) …

是否有一些方法可以在2D中获得更加有序的三角测量,就像Matlab Delaunay产生的那样？这是Matlab的2D Delaunay三角剖分的一个例子.

使用此代码:

xPoints = np.arange(0,11,1)
yPoints = np.arange(0,11,1)
gridPoints = np.array([[x,y] for y in yPoints for x in xPoints])
tri = Delaunay(gridPoints)
plt.triplot(gridPoints[:,0],gridPoints[:,1],tri.simplices.copy())
plt.plot(gridPoints[:,0],gridPoints[:,1],'bo')
plt.title("Triangulation Visualization")

我得到以下三角测量:

注意Matlab结果中的对角弧如何具有相同的斜率; 但那些在scipy结果中的人是变化的.由于Matlab和Scipy都在内部使用QHull,我认为有一些方法来模仿Matlab结果.

我一直在寻找这个问题的答案,但找不到任何有用的东西.

我正在使用python科学计算堆栈(scipy,numpy,matplotlib),我有一组2维点,我使用它来计算Delaunay traingulation(wiki)scipy.spatial.Delaunay.

我需要编写一个函数,给定任何一个点a,它将返回所有其他点,这些点是任何单形(即三角形)a的顶点,也是(a三角剖分中的邻居)的顶点.然而,scipy.spatial.Delaunay(这里)的文档非常糟糕,我不能为我的生活理解如何指定单纯形式,或者我会这样做.即使只是如何解释neighbors,vertices并vertex_to_simplex在德劳内输出数组被组织就足以让我去.

非常感谢任何帮助.