C++如何绘制Voronoi图

1、Voronoi图广泛应用在几何学、地理学、晶体学、信息系统等学科之中。Voronoi图是由图中各个相邻点连线的中垂线组成的连续多边形组成。图中的各个点归属于该点最邻近的多边形。

2、Voronoi图特点：每个多边形内仅含有一个中心点；每个多边形区域内的点到相应中心点的距离最近；位于多边形边上的点到其两边的中心的距离相等。  边e的起点和终点是给定点集中的两个点，边e是Deluanary三角形某个三角形的边，eRot是边e对应Voronoi图中的一条边

3、。一个四方边缘结构包含点集中某两点的Delauanry三角形边信息和Voronoi图边信息，eLnext、eDnext，eOnext、eRnext是属于其他边缘四方结构的Delauanry边和Voronoi边，

4、  每个QE单元存储四条有向边，其中两条为主边（Primal Edge）：e0和e2，描述当前的二维平面剖分S；另外两条为对偶边（Dual Edge）：e1和e3，描述S的对偶图。

5、每条Edge定义有三个基本行为：Org：返回当前有向边的起点。Rot：返回当前QE单元中逆时针旋转90度后的有向边，也即当前Edge的对偶边。     

6、Onext：返回S中以当前有向边Org为基点逆时针旋转到的下一条Edge。可以选取QE单元的任意一条Edge作为起始边来表示QE中的四条Edge。设起始边为e0。，则任意的有向边可以表示为(e, r)，