Delaunay剖分与平面欧几里得距离最小生成树

发布时间:2017-3-27 16:32:19 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Delaunay剖分与平面欧几里得距离最小生成树 ",主要涉及到Delaunay剖分与平面欧几里得距离最小生成树 方面的内容,对于Delaunay剖分与平面欧几里得距离最小生成树 感兴趣的同学可以参考一下。

这个东西代码我是对着Trinkle的写的,所以就不放代码了..

Delaunay剖分的定义: 一个三角剖分是Delaunay的当且仅当其中的每个三角形的外接圆内部(不包括边界)都没有点.

它的存在性是调整法可证的.

最小生成树的性质: 对于每个环c,它上面最长的边一定有一条不在MST上.

Delaunay剖分的性质: 如果有一条边的两个端点在一个内部(包括边界)没有其他点的圆上,那么这条边一定在Delaunay剖分内(反证).

那么如果有一条边u,v不在一个Delaunay剖分上,那么在任何一个u,v的外接圆内一定存在一个点c.我们考虑u,v为直径的那个圆,显然u--v,v--c,c--u成为一个环且u--v是最长边,那么u--v就可以被消去,从而不在MST上.

那么思路就比较明确了,我们先求出Delaunay剖分,再对Delaunay剖分上的边做MST. Delaunay剖分是一个平面图所以边数是与点数成线性关系的.

我们做Delaunay剖分的方法是: 对点按照x先的顺序排序,然后分治的做.那么我们现在需要考虑的就是合并两个不相交的Delaunay剖分.

我们可以先找到最低的边,以此为基准每次添加一个没有点在内部的三角形将这两个剖分连接.具体做法可以看这个 http://www.geom.uiuc.edu/~samuelp/del_project.html ,还是相当生动形象的.

复杂度的话,暴力就是O(n)一次的,因为每条遍历过的边要么不再碰了要么就删去了,然后也只会加O(n)条边.

所以保持总复杂度O(nlogn)是相对轻易的事情(虽然一点也不好写).



上一篇:简单工厂模式
下一篇:maxscript, 批量导出物体

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款