沃罗诺伊图

维基百科,自由的百科全书
跳转至: 导航搜索
沃罗诺伊图

沃罗诺伊图(Voronoi Diagram,也称作Dirichlet tessellation,狄利克雷镶嵌 )是由俄国数学家Georgy Fedoseevich Voronoi 建立的空间分割算法。灵感来源于笛卡尔用凸域分割空间的思想。在几何,晶体学建筑学,地理学,气象学,信息系统等许多领域有广泛的应用。

定义[编辑]

 \displaystyle{X} 表示一个距离函数为 d 的空间(一个非空集合)。 令 \displaystyle{K} 为一个指数集合,(P_k)_{k \in K} 为空间\displaystyle{X}的一个非空子集的有序元组。对应于\displaystyle{P_k} \displaystyle{R_k}, 称沃罗诺伊原胞,或称沃罗诺伊区域,是空间\displaystyle{X} 中所有到\displaystyle{P_k}的距离不大于到其他位置\displaystyle{P_j}(j≠k)的点集。或者说,如果定义 d(x,A)=\inf\{d(x,a) \,|\, a\in A\} 为点 x 和子集A 的距离,则

 R_k = \{x \in X\,\, | \,\,d(x,P_k) \leq d(x, P_j)\,\, \text{for all}\,\, j\neq k\}.

沃罗诺伊图即原胞(R_k)_{k \in K} 元组。 理论上有些位点能够交叉甚至重合,但事实上它们往往被设定为不相交的。另外,定义过程中允许位点数目无限(这在 几何数论结晶学有着重要应用),然而通常情况下,只考虑有限位点数。

对于某些特定情况,如有限维度的欧几里得空间,每一位点对应于一个点。这些点是有限且各异的,则沃罗诺伊原胞表现为凸多胞形,由它们的顶点、边、二维面等的组合方式加以描述。有时引入的组合结构被称为沃罗诺伊图。然而,沃罗诺伊原胞不一定是凸形,甚至不一定是连通的。


平面繪製[编辑]

在平面上,繪製沃罗诺伊图的過程,只要將胞點連起來構成許多三角形,利用中垂線找外心,再將所有外心相連即可。

参考资料[编辑]