随着科技水平的不断提高,计算几何扮演着越来越重要的角色,并在计算机图形学、机器视觉、地理信息系统、车辆导航、工业设计和集成电路设计等领域具有广阔的应用前景。Voronoi图作为计算几何中一个十分重要的分支,也颇受广大学者的青睐。本文旨在针对传统的Voronoi图存在的一些局限性进行分析和拓展。一方面,传统点集Voronoi图是围绕平面每一个点进行最近领域的划分,Voronoi单元格的数量等同于点集的数量。当点集数量过于庞大时,Voronoi划分的单元格也会随之变多,平面空间也就会出现分割过度的情况,这个时候的平面划分意义减弱了很多。而且,当目标对象过多时,我们则需要考虑目标与目标之间的关系、目标群体与目标群体之间的关系,而不是类似传统Voronoi图只考虑单一点到点的距离关系。如果将Voronoi图应用于微生物空间划分、地表火点空间划分时,现有的方法就起不到很好的作用,对此,我们需要解决点集数量过大情况下的Voronoi图生成问题。另一方面,多边形的Voronoi图可以应用在前景检测、场景分割等领域。最原始的多边形的Voronoi图是针对平面上每一个多边形的顶点、边界来进行最近领域的划分。它将每一个多边形视作独立的个体。但是,当目标和目标之间出现了多对一的集体关系,那么原始的多边形的Voronoi图就不再适用了。实际情况中会出现更加复杂的情况,我们往往需要用多个多边形来表示某一类群体,从而进行群体和群体之间的空间划分。因此需要拓宽多边形的Voronoi图的应用范围,使得可以应用于多个多边形表示同一类群体时的分割问题。针对传统Voronoi图只考虑每个点之间是相互独立的而忽略了点集和点集之间的联系,本文提出了一种基于DBSCAN聚类的Voronoi图。首先对该聚类Voronoi图进行定义和证明,研究其性质。然后对点集进行DBSCAN聚类,DBSCAN聚类的两个参数采用自适应算法进行生成。其次,将原始点集划分为若干个子集,最后以每个子集为Voronoi核心作Voronoi图。针对传统多边形Voronoi图仅以单个多边形为Voronoi核心划分的局限性,本文提出一种多边形集合的Voronoi图。首先研究传统多边形的Voronoi图的定义和性质,然后对多边形集合的Voronoi图进行定义和证明,该Voronoi图涵盖了凸多边形集合、凹多边形集合及凸多边形和凹多边形共存的集合,并研究其性质。最后提出该Voronoi图的生成算法,并应用于前景检测等领域,证明了算法的可靠性。本文对上述的方法进行了实验,实验结果表明,本文的方法有效解决了大规模点集生成Voronoi图的问题和多个多边形表示同一目标群体的问题,为Voronoi图应用于微生物学和计算机视觉应用领域提供了理论基础。