| 查看: 319 | 回复: 1 | |||
| 当前主题已经存档。 | |||
| 【有奖交流】积极回复本帖子，参与交流，就有机会分得作者 malei123 的 4 个金币 | |||
malei123新虫 (小有名气)
|
[交流]
【求助】求一个Voronoi图形程序
|
||
| 求一个Voronoi图形程序 |
回复此楼» 猜你喜欢
哈尔滨工业大学韩晓军教授课题组招收2027年硕士推免生及博士研究生
已经有3人回复
-
售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急
已经有8人回复
-
售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急
已经有8人回复
-
售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急
已经有9人回复
-
找导师
已经有8人回复
-
售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急
已经有5人回复
-
售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急
已经有9人回复
-
面上没中，邀请各位路过的虫友分析一下分数
已经有3人回复
-
售一区SCI文章T0P，我:8O.551.O54,科目全,可十急
已经有8人回复
-
售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急
已经有11人回复
★ ★ ★
malei123(金币+1,VIP+0):好 7-9 20:06
wangen994(金币+2,VIP+0):感谢你参与交流，欢迎常来 7-9 20:31
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) 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) 例子就不举了，太麻烦。。。。。。 |
2楼2009-07-09 18:38:11
20