cgex

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 ，进行下一步迭代。