精华内容
下载资源
问答
  • delaunay

    千次阅读 2015-03-18 21:32:56
    近期论坛上有不少讨论delaunay函数的帖子。似乎主要有以下问题: 1、delaunay函数各参数的意义 2、知道几何边界时,用delaunay函数划分三角形网格由于区域内部没有点,质量很差,怎么改进 3、怎样避免产生过于...
    近期论坛上有不少讨论delaunay函数的帖子。似乎主要有以下问题:
    1、delaunay函数各参数的意义
    2、知道几何边界时,用delaunay函数划分三角形网格由于区域
    内部没有点,质量很差,怎么改进
    3、怎样避免产生过于狭长的delaunay 三角形

    4、 凹多边形的情况怎么处理
    第1个问题,看看帮助应该能解决。第2个问题,delaunay本来是用来对离散点进行三角剖分,内部没有点时并不合适。除非特别处理。第3个问题,估计是利用delaunay和meshgrid来划网格,边界附近会产生狭长的delaunay 三角形,这个也可以做特别处理。第4个问题,可以用在划分好网格后删掉域外的三角形即可。

    由于我也经常使用delaunay来处理背景积分问题,因此仔细琢磨了一下用delaunay来划分已知边界的几何区域的可行方案,在此和大家分享一下,也是抛砖引玉,希望大家有更好的方法。

    方案一:先对区域delaunay剖分,删掉域外的三角形,然后将剩下的三角形的边细分,得到新的离散点,然后再次delaunay剖分,然后再次细分边,这样循环下去,直到达到一定的尺寸为止

    方案二:利用delaunay和meshgrid函数。将边界细分得到相比原区域边界更加密集边界点,用meshgrid得到包含整个区域的点,将域内的点和边界点一起delaunay 剖分。

    讨论:
    方案一对于一开始就有很小边界段的情况情况较差,容易出现狭长单元(比如边界有圆弧的话属于这种情况)。还有就是前一步的边界轮廓很清楚,看着别扭。方案二中间的网格能搞保证形状较好。对于边界附近的内部点,容易导致边界单元畸变,可以将离边界太近的点进行删除,这样得到的形状比较好

    综合来说,方案二较好,尤其是当删掉离边界太近的内部点。贴出程序,望大家多多指点,共同进步。

    P.S. 当然,matlab自身也有很好的网格划分函数,在pdetool中有用到,不过关于几何描述那块比较难以理解(我不是很理解)。另外matlab语言写的划分网格的程序很多,网上可以找到不少很优秀的。这里仅限于简单的使用delaunay来划分。



    也就是约束Delaunay三角形
    X = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
    C = [1 2; 2 3; 3 4; 4 5; 5 6; 6 7; 7 8; 8 1];
    dt = DelaunayTri(X, C);
    subplot(3,1,1);
    io=dt.inOutStatus();
    triplot(dt(io,:),X(:,1),X(:,2));
    axis([-1 17 -1 6]);
    xlabel('Constrained Delaunay triangulation(inside)', 'fontweight','b');
    hold on;
    plot(X(C'),X(C'+size(X,1)),'-r', 'LineWidth', 2);
    hold off;
    subplot(3,1,2)
    triplot(dt(~io,:),X(:,1),X(:,2));
    axis([-1 17 -1 6]);
    xlabel('Constrained Delaunay triangulation(outside)', 'fontweight','b');
    hold on;
    plot(X(C'),X(C'+size(X,1)),'-r', 'LineWidth', 2);
    hold off;
    dt.Constraints = [];
    subplot(3,1,3);
    triplot(dt);
    axis([-1 17 -1 6]);
    xlabel('Unconstrained Delaunay triangulation', 'fontweight','b');

    展开全文
  • Delaunay performance

    2021-01-08 13:39:19
    s Delaunay triangulator may be a good alternative. He's able to triangulate either in 2d and 3d. <p>scipy is available as python wheels for linux, osx and windows. <pre><code> import bmesh from ...
  • Delaunay.rar

    2020-03-17 16:31:24
    Delaunay三角剖分由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关。这是自己写的常用的delaunay三角剖分算法,用C语言实现,简洁明了,是非常实用的小工具。
  • Delaunay Triangulations

    2016-02-26 09:48:09
    卡耐基梅隆的Delaunay Triangulations讲义,讲的非常不错。
  • Delaunay2D.cs

    2021-02-01 09:03:21
    根据散点信息剖分三角形的算法,有详细的中文注释。...使用Delaunay2D delaunay=Delaunay2D.Triangulate(List<Vertex> vertices) 方法计算。 使用delaunay.Edges和delaunay.Triangles获得边和三角形的信息。
  • delaunay三角剖分:C ++版本的delaunay三角剖分
  • Delaunay3D.cs

    2021-02-01 09:07:07
    使用Delaunay3D delaunay=Delaunay3D.Triangulate(List<Vertex> vertices) 方法计算。 使用delaunay.Edges和delaunay.Triangles获得边和三角形的信息。 使用delaunay.Tetrahedra获得剖分的四面体的信息。
  • Delaunay三角网算法

    2021-01-07 20:53:20
    Delaunay三角网算法
  • Delaunay三角剖分给出了一个“好的”三角网格的定义,它的优秀特性是空圆特性和最大化最小角特性,这两个特性避免了狭长三角形的产生,也使得Delaunay三角剖分应用广泛。 空圆特性:点集合p内任意一个点都不在???...

    三角网格是最常用的三维模型表述方式,基本结构为:

    1. 顶点 (Vertex),决定空间位置
    2. 面片 (Facet),描述拓扑结构
    3. 边 (Edge)。

    三角剖分就是将离散的点连入三角网格中。也可以说是把曲面剖开成一块块三角形。

    下图为非delaunay三角剖分:
    在这里插入图片描述

    而Delaunay三角剖分给出了一个“好的”三角网格的定义,它的优秀特性是空圆特性和最大化最小角特性,这两个特性避免了狭长三角形的产生,也使得Delaunay三角剖分应用广泛。

    • 空圆特性:点集合p内任意一个点都不在𝑃 内任意一个三角面片的外接圆内。
    • 最大化最小角特性:找到每个三角形内最小的锐角,并将其最大化。

    空圆特性,任意3个点的外接圆不包含第4个点,即任意3个点(三角形)的外接圆是空的。这种形式的剖分产生的最小角比不满足空圆特性的最小角大。在这里插入图片描述
    下图为delaunay三角剖分:
    在这里插入图片描述

    Lawson Flip Algorithm:将非delaunay剖分转化为delaunay剖分。

    如下图,该翻转即去掉左图对角线,连接右图对角线。两条对角线即两种不同的剖分方法。每次flip都是在增大三角剖分的最小角
    在这里插入图片描述
    增量delaunay三角剖分算法,在已Delaunay三角化的网格中加入一点P,只需要删除所有外接圆包含此点的三角形,并连接P与所有可见的点(即连接后不会与其他边相交),则形成的网格仍然满足Delaunay三角剖分的条件。时间复杂度为O(nlogn)

    1. 添加两个足够远的点𝑝−1, 𝑝−2,以保证𝑝−1, 𝑝−2 位于所有三角形的外接圆外。三角形𝑝0 𝑝−1 𝑝−2 包含所有的点。初始的时候仅有一个空的三角形。
    2. 依次添加新的点𝑝𝑟,检测相关三角形的空圆特性。(插入一个点会影响到周围的一块区域)

    对于𝑝𝑟存在以下两种情况:
    在这里插入图片描述

    • 情况1: 分别连接 𝑝𝑟𝑝𝑖,𝑝𝑟𝑝𝑗, 𝑝𝑟𝑝𝑘,分别检查与三角形𝑝𝑟𝑝𝑖𝑝𝑘, 𝑝𝑟𝑝𝑗𝑝𝑘, 𝑝𝑟𝑝𝑖𝑝𝑘相邻的3个三角形的空圆特性
    • 情况2: 分别连接 𝑝𝑟𝑝𝑙,𝑝𝑟𝑝𝑘,分别检查与三角形𝑝𝑟𝑝𝑗𝑝𝑘, 𝑝𝑟𝑝𝑗𝑝𝑙, 𝑝𝑟𝑝𝑙𝑝𝑖, 𝑝𝑟𝑝𝑘𝑝𝑖 相邻的4个三角形的空圆特性

    将delaunay三角剖分应用在三维上即delaunay四面体剖分。首先我们由点云构建Delaunay四面体,然后将其标记为目标物体的的内部和外部,这里得到的是体数据,无法直接得到面片。

    delaunay四面体剖分+马尔可夫优化->三维网格

    Delaunay四面体剖分的基本理论—边界一致,设Σ是一个三围区域W边界的离散化-曲面网格。边界一致的问题是要求生成一个符合Σ的四面体网格T,即Σ是一个由Γ元素组成的组合体。T中可以有额外的点(Steiner点),但是这种点的数目应该被限制得越少越好。

    展开全文
  • Delaunay Triangulation

    2021-01-07 04:54:41
    <div><p>Is there an example of Delaunay triangulation working? I was not able to get a list of faces here, whereas Scipy Delaunay triangulation does generate one. The following is the list of vertices...
  • Delaunay三角剖分(Delaunay Triangulation) 1.Delaunay边: 假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边: 存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何...

    Delaunay三角剖分(Delaunay Triangulation)
    1.Delaunay边: 假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边: 存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。
    2.Delaunay三角剖分:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。
    3.假设T为V的任一三角剖分,则T是V的一个Delaunay三角剖分,当且仅当T中的每个三角形的外接圆(circumcircle)的内部不包含V中任何的点。

    https://mathworld.wolfram.com/DelaunayTriangulation.html

    Delaunay三角剖分所具备的优异特性:
    1) 最接近:以最近临的三点形成三角形,且各线段(三角形的边)皆不相交。
    2) 唯一性:不论从区域何处开始构建,最终都将得到一致的结果。
    3) 最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。
    4) 最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。
    5) 区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。
    6) 具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。


    Voronoi diagram(泰森多边形又叫冯洛诺伊图),得名于Georgy Voronoi,是一组由连接两邻点线段的垂直平分线组成的连续多边形组成。
    一个泰森多边形内的任一点到构成该多边形的控制点的距离小于到其他多边形控制点的距离。
    Voronoi Diagram
    The partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. The cells are called Dirichlet regions, Thiessen polytopes, or Voronoi polygons.
    Voronoi diagrams were considered as early at 1644 by René Descartes and were used by Dirichlet (1850) in the investigation of positive quadratic forms. They were also studied by Voronoi (1907), who extended the investigation of Voronoi diagrams to higher dimensions. They find widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street.

    展开全文
  • Delaunay/TIN

    2019-05-25 18:08:43
    bowyer-watson算法实现的delaunay三角生成,python编写,可以用于TIN的生成
  • 该项目显示了如何根据一组随机点计算凸包,Delaunay三角剖分或Voronoi图。 该项目基于代码,但我对其进行了一些重组,并扩展了Delaunay和Voronoi部分。 赫尔(Hull),德劳内(Delaunay)和沃罗诺伊(Voronoi)的3...
  • Delaunay生长算法C#

    2019-02-21 17:55:44
    Delaunay生长算法C#。 看到网上好像没有C#写的这个算法,写的也大多乱七八糟,自己写了一下,加了一些东西,例如两种方式加载数据,还有算法运行时间,这样子方便大家对Delaunay算法的比较 Delaunay 生长 C#
  • Delaunay三角网

    千次阅读 2019-09-11 15:53:39
    Delaunay三角网生成Delaunay三角网算法Delaunay三角剖分的重要准则不规则三角网(TIN)的建立分割合并算法逐点插入算法递归生长算法 生成Delaunay三角网算法 由一系列相连的但不重叠的三角形的集合, 而且这些三角形...

    Delaunay三角网定义

    由一系列相连的但不重叠的三角形的集合, 而且这些三角形的外接圆不包含这个面域的其他任何点。
    总结一句话就是生成的三角网中的任意一个三角形不能包含其他的三角形的顶点。
    在这里插入图片描述

    Delaunay三角剖分的重要准则

    在这里插入图片描述
    在这里插入图片描述
    其中,空外接圆准则和张角最大准则是最常用的两种准则

    Lawson的局部优化算法(LOP)

    对于生成三角网的过程,在已经生成的三角网中插入新的点,会导致新三角网不再符合三角形剖分准则。基于最大最小角规则,Lawson也给出了局部优化算法(LOP),交换凸四边形的对角线,保留短的那条对角线,使三角网中所有三角形的最小角度最大化。

    因此,在构网过程中,或者在原有的三角网中插入新的点集不需要每次都遍历整个三角网查找不符合三角剖分的三角形,并进行优化,因为除了新插入的点外的三角网都是符合三角剖分的。因此,LOP只需检测新三角形及其临近三角形,使其符合三角剖面即可,这样大大的节约了时间消耗。
    在这里插入图片描述

    不规则三角网(TIN)的建立

    三角网构建方法:
    在这里插入图片描述

    分割合并算法

    采用分而治之策略,将复杂问题简单化:

    先将数据点分割成易于三角化的点子集(如每子集3、4个点),后对每个子集分别三角化,并由LOP优化成D_三角网;之后对每个子集的三角网进行合并,形成最终的D_三角网。

    分割合并三角化算法如图所示:
    在这里插入图片描述
    STEP1

    将数据集以横坐标为主、纵坐标为辅按升序排序。

    STEP2

    如数据集中点数大于阀值,则继续将数据集化为点个数近似相等的两个子集,并对每个子集做如下工作:

    ① 获取每子集的凸壳;

    ② 以凸壳为数据边界进行三角化,并用LOP优化成D三角网;

    ③ 找出连接左右子集两个凸壳的底线和顶线;

    ④ 由底线到顶线合并两个三角网。

    STEP3

    如数据集中点数不大于阀值,则直接输出三角剖分结果。

    数据点集采用递归分割快速排序法;子集凸壳的生成可采用格雷厄姆算法(见后);子集三角化可采用任意方法,如子集最小到3或4个点则可直接三角剖分之;子网合并则需先找出左右子集凸壳的底线和顶线(算法见后),然后逐步合并三角剖分得到最终D三角网。

    逐点插入算法

    在这里插入图片描述

    递归生长算法

    在这里插入图片描述

    展开全文
  • Dev delaunay tests

    2021-01-07 05:52:06
    <div><p>This adds unit tests for the Delaunay triangulation function and exposes the <code>is_delaunay</code> function, with an overload that computes "Delaunay-ness" per (half-)edge. Along ...
  • Delaunay三角剖分

    千次阅读 2020-09-22 20:43:18
    三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种...
  • 在泰森多边形的构建中,首先要将离散点(sample,样点)构成三角网。这种三角网称为Delaunay三角网。
  • Delaunay voronoi dual

    2020-12-09 00:33:23
    <div><p>A class that creates duel Delaunay and Voronoi networks, and connects them to each other to allow interaction. </p><p>该提问来源于开源项目:PMEAL/OpenPNM</p></div>
  • Delaunay.update

    2020-12-26 08:31:21
    <div><p>fixes #68. ~~I don't like the list of all properties in the code, there's probably a more elegant solution?~~</p><p>该提问来源于开源项目:d3/d3-delaunay</p></div>
  • <p>Implementation of avoid-crossing-perimeters using Constrained Delaunay Triangulation with refinement. Code is still unfinished, but quick review would be nice.</p><p>该提问来源于开源项目:...
  • Delaunay三角网程序

    2016-12-27 22:05:01
    控制网课程,Delaunay三角网程序,可运行,可直接生成Delaunay三角网程序。
  • <div><p>This PR implements the insertion using the hierarchical delaunay algorithm. <p>The benchmark numbers are significantly worse than the version in the first PR without the predicates. The cpu ...
  • <div><p>Net benefit is approximately 20% for Delaunay, 2-3% for Voronoi. <ul><li>Avoid copying all triangles after construction</li><li>Avoid inFrame checks if result will be ignored</li><li>Avoid ...
  • Delaunay三角化

    千次阅读 2017-02-17 23:13:23
    尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。 Delaunay剖分所具备的优异特性: 1.最接近:以最近的三点形成三角形,且各线段...
  • Delaunay三角剖分演示

    2018-08-15 20:18:57
    可显示四种结果:离散点、凸包、凸包剖分、Delaunay三角形 改变点数的数目:可以演示每次加点的过程 点击重置:打乱离散点,重新生成
  • in the form of the Delaunay Triangulation code. This code is now included and maintained in Matplotlib. We should remove ours and rely on the upstream version. <p>Additionally, in service of removing...
  • [1] [1] Delaunay 三角剖分算法 点集的三角剖分Triangulation对数值分析比如有限元分析以及图形学来说都是 极为重要的一项预处理技术尤其是 Delaunay 三角剖分由于其独特性关于点集的很 多种几何图都和 Delaunay ...
  • <em>Conforming</em> would introduce new points in order to be true delaunay triangles (steiner points) while <em>constrained</em> is not always truely delaunay but doesn't introduce extra points....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,357
精华内容 542
关键字:

delaunay