voronoi图的算法编程实现

voronoi图的算法编程实现

悬赏分：10 | 解决时间：2010-4-9 10:19 | 提问者：craftboy000

给个代码，谢谢！

最佳答案

输入：点集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)<d，则取p1, p2, p3连成三角形。goto 2

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)。

或者

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典教育范文voronoi图的算法编程实现在线全文阅读。