资 源 简 介
CGex is a computational geometry library in c++ to implemente the algorithms we encountered in the CG lesson in Tsinghua University, Beijing.
Now CGex is implemeting the algorithm:
* voronoi diagram
CGex是中国北京清华大学的一组同学在学习计算几何这门课程时用c++实现的一个作品。现在它包含了Voronoi图的生成和算法过程演示，重心Voronoi图迭代演示。
Voronoi图生成原理
本作品利用Beach-Line Voronoi图生成算法(详细情况请见参考文献1)，该算法的具体原理参考邓俊辉老师讲义第四章Voronoi Diagram中的04.vd.f.Plane Sweep。
重心Voronoi图简介
简介
使用Voronoi图对平面区域进行分割(如下图：左)，如果每个区域中包含的site都与这个区域的重心重合(如下图：右)，就称这个划分为重心Voronoi划分。（具体和严格定义请参考文献3）
http://cgex.googlecode.com/files/cvt.PNG
算法
本实验采用通用的Lloyd"s算法来迭代，产生最终的重心Vronoi图。
* Step0 ：生成由k个点组成的初始点集{zi}。
* Step1 ：在当前区域Ω中，根据点集{zi}初始Voronoi划分{Vi}。
* Step2 ：针对 Step1 中生成的Voronoi区域{Vi}，计算产生每一个区域的中心点，将这些中心点设置为新点集{zi}。
* Step3 ：如果新点集中的点满足收敛条件，则算法终止；否则转 Step1 ，进行下一步迭代。
