Rhino(犀牛)中国技术支持与推广中心

标题: Voronoi2D小改进 [打印本页]

作者: 游泳的狼 时间: 2009-5-7 22:07
标题: Voronoi2D小改进
最近研究了一下VORONOI2D,发现如果手工输入的话会很麻烦，于是我就做成了像现在这样可以自动区分边缘点和内部点，内部点再在XY平面上随机移动。

原理是通过获得一个平面，然后等分，把端点输出到一个数组，
通过数列的方法吧特定项抽取出来分成两个数组，一个是边缘点的，一个是中间点的，把这两个分别输入到VORONOI2D里面。
做数列的时候GH实在是麻烦，就用了点VB的脚本，很简单，就是一个嵌套的循环，大家有兴趣的话看看代码，就几行。

输入项：
1，有两条直线，生成平面；
2，分格的大小；
3，中间点随机偏移的幅度；
4，VORONOI网格偏移大小。

3DM和GHX在压缩包里面。上次WUDI说我没发图，这次我真的发了^_^

voronoi2d实验.rar

34.49 KB, 下载次数: 479

作者: 游泳的狼 时间: 2009-5-7 22:08
而且，因为是方块，很容易就可以MORPH到一个曲面上：）

作者: du563217 时间: 2009-5-7 22:52
没有过呀 VORONOI2D有什么好的功能

作者: lxaaron 时间: 2009-5-8 00:07
:bumpAgain ...孤陋寡闻了我！！

作者: 游泳的狼 时间: 2009-5-8 00:24
科普一下：）版面上也有不少相关的帖子，大家可以搜索一下
例如：
http://bbs.rhino3d.asia/thread-6067-1-1.html

http://baike.baidu.com/view/501103.htm
voronoi
　　一、基本概念
　　Voronoi图，又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻 Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。 Voronoi三角形是Delaunay图的偶图；
　　对于给定的初始点集P，有多种三角网剖分方式，其中Delaunay三角网具有以下特征：
　　1、Delaunay三角网是唯一的；
　　2、三角网的外边界构成了点集P的凸多边形“外壳”；
　　3、没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网。
　　4、如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。
　　Delaunay三角形网的特征又可以表达为以下特性：
　　1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；
　　2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；
　　3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；
　　4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。
　　Delaunay三角形产生的基本准则：任何一个Delaunay三角形的外接圆的内部不能包含其他任何点[Delaunay 1934]。Lawson[1972]提出了最大化最小角原则，每两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。 Lawson[1977提出了一个局部优化过程（LOP, local Optimization Procedure）方法。
　　二、Delaunay三角形网的通用算法－逐点插入算法
　　基于散点建立数字地面模型，常采用在d维的欧几里得空间Ed中构造Delaunay三角形网的通用算法—逐点插入算法，具体算法过程如下：
　　1、遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三角形并放入三角形链表。
　　2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
　　3、根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。
　　4、循环执行上述第2步，直到所有散点插入完毕。
　　上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
　　为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于边的构网方法，其算法简述如下：
　　1、根据已有的地性线和特征线，形成控制边链表。
　　2、以控制边链表中一线段为基边，从点集中找出同该基边两端点距离和最小的点，以该点为顶点，以该基边为边，向外扩展一个三角形（仅满足空椭圆特性）并放入三角形链表。
　　3、按照上述第2步，对控制边链表所有的线段进行循环，分别向外扩展。
　　4、依次将新形成的三角形的边作为基边，形成新的控制边链表，按照上述第2步，对控制边链表所有的线段进行循环，再次向外扩展，直到所有三角形不能再向外扩展为止。

[ 本帖最后由游泳的狼于 2009-5-8 00:25 编辑 ]

作者: wudi1212 时间: 2009-5-8 01:39
是通过改写code实现的么？？

作者: 游泳的狼 时间: 2009-5-8 01:49

原帖由 wudi1212 于 2009-5-8 01:39 发表
是通过改写code实现的么？？

没有改写CODE，我看了一下，其实他代码里面就是一个标准算法，不算太复杂，关键是他要求输入的POINT有两种，一种是内部点，一种是边界点

我是用GRASSHOPPER在前面做了个小处理，这样只需要输入一个面就可以自动把边界点和内部点分别输入到源程序去了。

你看一下我那个RAR文件就明白了。不过区分内部点的时候还是用了下VB,发现用VB做起来很简单的东西用GH就会超级复杂。。
-。-

作者: 单身贵族 时间: 2009-5-8 09:55
有点小深奥。。。。。。

作者: panhao1 时间: 2009-5-29 01:15
有没有好一点的2d voronoi代码输入边界和内部点的代码还是有bug
点太近会出现错线

作者: hymnist 时间: 2009-5-29 16:33
我顶你的肺啊

作者: 游泳的狼 时间: 2009-5-29 19:53
9# panhao1

边界线出错是因为内部点随机偏移的时候超出边界了，哈哈

作者: 游泳的狼 时间: 2009-5-29 19:56
边界线出错是因为内部点随机偏移的时候超出边界了，哈哈

作者: panhao1 时间: 2009-5-29 23:37
其实是某些curve无法offset :start

作者: panhao1 时间: 2009-5-29 23:38
12# 游泳的狼
其实是某些curve无法offset而已

不知道哪里出错了

作者: veronique 时间: 2009-5-30 09:30
学习~学习

作者: 游泳的狼 时间: 2009-5-30 14:21
说实话，OFFSET那个代码我没看懂

作者: 发现档案 时间: 2009-7-1 10:20
选择点模式大概清楚
关键是以后各步骤如何构建,以及之间的关系
如:垂直平分线,各个区域与垂直平分线关系等
'Draws the boundary rectangle
'VORONOI VERTEX CLASS'
'VORONOI CELL CLASS'
'calculates teh perpendicular bisector between two points
'Intersects two lines 9th grade math style
这几步到底什么关系
请高手解答

作者: ssean 时间: 2010-8-20 10:56
不错学习了

欢迎光临 Rhino(犀牛)中国技术支持与推广中心 (http://bbs.rhino3d.asia/)