24小时热门版块排行榜

返回列表

当前主题已经存档。

【有奖交流】积极回复本帖子，参与交流，就有机会分得作者 malei123 的 4 个金币

malei123

新虫 (小有名气)

应助: 0 (幼儿园)
金币: 352.4
散金: 15
帖子: 134
在线: 62.2小时
虫号: 740151
注册: 2009-04-04
性别: GG
专业: 固体力学

[交流] 【求助】求一个Voronoi图形程序

求一个Voronoi图形程序

回复此楼

» 猜你喜欢

参与限项已经有3人回复
假如你的研究生提出不合理要求已经有7人回复
实验室接单子已经有4人回复
全日制（定向）博士已经有4人回复
对氯苯硼酸纯化已经有3人回复
求助:我三月中下旬出站，青基依托单位怎么办？已经有12人回复
不自信的我已经有12人回复
所感已经有4人回复
要不要辞职读博？已经有7人回复
北核录用已经有3人回复

jisuan

1楼 2009-07-08 18:33:52

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

r123ed

金虫 (著名写手)

应助: 130 (高中生)
金币: 859.9
散金: 559
红花: 21
帖子: 1536
在线: 284.1小时
虫号: 601346
注册: 2008-09-13
专业: 数理统计

★ ★ ★
malei123(金币+1,VIP+0):好 7-9 20:06
wangen994(金币+2,VIP+0):感谢你参与交流，欢迎常来 7-9 20:31

输入：点集S = {p1, p2, …, pn}。
1. 任取pi, pj, pk三点连成三角形
2. 求出此三角形的外心v和半径d
3. 对图中点计算距离d(pr, v)，r=1…n并据此将各点排序，得到p1, p2, …, pn-3。l←1。
4. if d(pl, v)>d then goto 6
5. 改取pl, pi, pj组成三角形。若有多点满足d(pl, v) 6. 判定pl在已有哪条有向边或哪两条有向边右侧
7. 修改pl所在多边形的边界及顶点
8. l←l+1，goto 6 直到l>n-3
步骤1，2，4，5，7时间为常数；步骤3要求n-3次计算距离及nlogn次比较；步骤5到步骤2的循环为常数次，步骤6需要O(n)次计算，步骤8循环n-3次，代价3+4+…+n-1 = O(n2)，总时间复杂性为O(n2)。

或者

1. 划分S为规模近似相等的子集S1, S2
2. 递归地构造Vor (S1)和Vor(S2)
3. 构造折线B分开S1, S2，使得对B上任一点v及S1中的点a和S2中的点b，有d(a, v)=d(b, v)。
4. 删去B左侧的Vor(S2)的所有边和位于B右侧的Vor (S1)的所有边，得到Vor(S)

例子就不举了，太麻烦。。。。。。

赞一下(11人)

回复此楼

shape memory

2楼2009-07-09 18:38:11

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 malei123 的主题更新

返回列表