海量平面点集Voronoi图的构造算法

进一步发展平面点集Voronoi图的增量式外置算法.在对"海量"点组成的平面点集进行Voronoi划分时,设计"硬盘数据文件——内存结构体数组"之间动态的数据交互方案,避开计算机内存的限制,有效实现了数十万Voronoi晶胞集合体的构造,存储Voronoi图几何信息的数据最后以文本文件的形式输出,方便Voronoi图在工程实际中的应用与二次开发.     

空间点集Voronoi图的海量构造算法及可视化技术

设计空间点集Voronoi图的增量式外存算法以及空间点集Voronoi图的任意平面可视化剖分技术,以"点-线-面-体"的空间数据结构为基础,实现在指定空间区域内生成Voronoi图的新方法.提出的算法数据结构清晰合理,数据交互方案简单有效且无内存限制,发展的可视化技术可以对空间点集Voronoi图进行任意的平面剖分,实现了三维Voronoi晶胞集合体内部结构的可视化.     

关于Voronoi图的一个不等式

提出并证明了关于Ｖｏｒｏｎｏｉ图的一个新性质：设Ｓ是平面上任一有限点集，ｄｓ是Ｓ中最近两点之间的距离，ｐ是Ｓ中任一点，Ｖ（ｐ）是关联于ｐ的Ｖｏｒｏｎｏｉ多边形，Ａ（ｐ）是Ｖ（ｐ）的面积，则Ａ（ｐ）≥３１／２２ｄ２ｓ．     

离散平面Voronoi图的光栅图形算法

1　引言　　Voronoi图及其对偶Delaunay三角剖分,目前广泛应用于计算机图形生成、CAD/CAM和有限元方法等领域,特别是近十年来,随着计算机图形学的发展,三维图形生成技术的需求,受到了学术界的极大关注.此外,Voronoi图的几何特性,在气象、结晶材料,空中交通管制等领域都得到广泛应用.从目前发表的大量文献看,基本上是基于连续域计算几何出发进行的[1,2],其计算方法主要分成两个类型:一个是增量算法,通过每次增加一个点来计算Voronoi图;另一种是分合算法,通过将点划分成两部分,递归计算每一部分点的Voronoi图,然后再将它们合并.光栅图形…     

基于平面多边形Voronoi图的算法与快速成形应用

探讨了平面多边形的Voronoi图的性质,提出了一种新的求解平面多边形的Voronoi图的算法,其核心思想是单独考虑每个Voronoi图对象,分开计算其分治区,然后再构成一个具有拓扑关系的Voronoi图.这种计算方法较其他现有算法(比如二分法)大幅度提高了求解Voronoi图的成功率,在VC 平台上得到了实现,并应用于快速成形的等距线扫描工艺中.该算法求解平面切片的轮廓的Voronoi图和生成等距线速度快,可以实时生成切片轮廓的全部等距线.试验证明:算法可以减少制件特别是类似大平面制件的翘屈变形,提高制件整体质量.     

基于Voronoi图的无线传感器网络覆盖算法研究

网络覆盖技术决定了无线传感器网络对物理世界和目标区域的监测能力.对于给定的被监测区域,如何达到最大的覆盖率,提高布撒方的防御能力,是覆盖控制中必须考虑的问题.Voronoi图具有良好的邻近性、邻接性、最大圆、快速划分区域和增删节点的特性.本文提出了一种基于Voronoi图的无线传感器网络覆盖算法,来定位覆盖漏洞区域,将未被覆盖的Voronoi图顶点加入到监测点中以提高被监测区域的覆盖率,并且研究了不同感知半径下传感器节点数量和覆盖率的关系.仿真结果表明,基于Voronoi图的覆盖算法有效的提高了网络覆盖率,从35.41％提高到了100.02％,且网络覆盖率随着传感器节点的感知半径的增大而提高.该算法容易实现,复杂度低,实验结果验证了算法的正确性.     

基于Voronoi图的磁共振PROPELLER数据网格化算法

PROPELLER数据采集成像算法是磁共振成像中的一项新技术,由于其数据的网格化直接影响该成像算法的效果,因此提出一种基于Voronoi图的网格化算法．该算法对采样数据集进行网格分组查找,快速消除位置相同点;加入边缘闭包后进行Voronoi网格化,计算Voronoi网格面积并将其作为网格化的密度补偿权函数,提出基于网格分组的快速网格化算法并成像．实验表明,该算法运行速度快,成像清晰,图像对比度和细节较好,信噪比得到有效提高．     

生成元为一般图形的线段障碍Voronoi图离散构造法

讨论了计算几何中一类线段障碍Voronoi图的构造问题．提出了一种基于边界离散化的作图法,即先在各生成元边界上选取母点,再利用文献中的算法,进而得到生成元为任意平面几何图形的线段障碍voronoi图．结果表明该算法是有效的．这一算法改进并推广了文献提出的算法．     

基于Voronoi图和量子粒子群算法的无人机航路规划

 无人机(UCAV)是自主控制执行任务的无人驾驶飞机,其航路规划是一类复杂优化问题,因此难以在多项式时间内获取精确解,为此提出了一种基于Voronoi图和量子粒子群(QPSO)算法的UCAV航路规划方法。首先,在综合考虑航路的雷达威胁和燃油耗费的基础上定义了航路规划的代价模型;然后,根据已知的威胁源生成Voronoi图,通过连接起点、Voronoi图中顶点以及终点获得初始规划解集;最后,通过引入柯西变异随机数和扰动对QPSO算法进行改进,以增强其全局寻优能力和收敛速度,并定义了采用此改进的QPSO算法对UCAV进行最终航路规划的具体算法。仿真实验表明,该方法能求解出UCAV航路规划的最优解,且与经典的PSO算法和QPSO算法相比,具有全局寻优能力强和收敛速度快的优点。     

高阶Voronoi图的结晶生成

Voronoi图是计算几何的重要分支.高阶Voronoi图是Voronoi图在阶数方面的扩展,在许多领域有着重要应用.本文提出了生成高阶Voronoi图的结晶生长方法.该方法以生成元为初始生长点,使用4-连通模板、8-连通模板或二者交替使用进行结晶生长,最后对不同颜色的区域分别进行处理,就会得到基于城区距离、棋盘距离或欧氏距离的各种高阶Voronoi图.     

New Voronoi Diagram Algorithm of Multiply-Connected Planar Areas in the Selective Laser Melting

This paper studies the practical generation of Voronoi diagrams for multiply-connected planar areas bounded by line segments. The core of the algorithm was calculating Voronoi polygon of every Voronoi object in planar areas independently. The main approach had two steps. The first step was calculating all relevant bisectors of every Voronoi object. The second was combining obtained bisectors into completed Voronoi polygons individually. All code was implemented in Visual C++ platform. The resulting code was extensively tested in real-world data and its practical running time grew only linearly. Three statistical CPU-consumption charts had been drawn with the Voronoi diagrams computation data, and compared with other published codes for computing Voronoi diagrams. The algorithm was applied to compute offsetting of slice area consisting of large-scale line segments for the selective laser melting (SLM) trajectory scanning technology which is a kind of rapid prototyping (RP). The experimental results of offsetting for slice area based on Voronoi diagrams show that the approach is effective and simple for polygon offsetting problems. The method is helpful to those offsetting work and can provide more effective offsetting solution.     

基于ArcGIS环境下多类型数据的三角网和Voronoi图的生成

基于渐次插入算法,在ArcGIS环境下,提取居民地中心点和道路中心线上的点作为离散点,实现了对这些离散点的Delaunay三角网的构建和数据的有效组织,利用ArcGIS提供的接口生成了Voronoi图,实现了多类型数据Delaunay三角网和Voronoi图的生成。     

基于增量式遗传算法的粗糙集分类规则挖掘

从规则获取和优化两个方面研究了基于遗传算法(GA)的增量式粗糙集分类规则挖掘方法．通过研究决策表和决策规则系数，建立了基于粗糙集表示和度量的知识理论，将GA和粗糙集分类规则挖掘算法相结合，在保持原有知识完备的前提下，利用GA对以增量形式获得的分类规则进行优化，获取最优分类规则．试验结果表明，执行增量式GA所需时间较执行一般GA所需时间要少，可有效完成分类规则优化的任务，同时还可提高分类的精度，使分类结果具有更好的可理解性．     

基于Voronoi图的洛阳城市绿地系统分析与设计

城市绿地的空间布局和设计是建设生态城市,改善人居环境的重要环节.本文根据Voronoi图的空间分割和邻近查询原理,将城市绿地系统内的每个绿地斑块视作一个发生元,运用Voronoi图分析洛阳城市绿地系统位置分布与服务范围,并依据分析结果,提出洛阳城市绿地系统的空间布局设计方案.     

一种基于密度的增量式网格聚类算法

增量算法的要求是聚类特征一般是可加的、非迭代的。文中提出了一种基于密度的网格聚类算法GDCLUS，并在此基础上提出了增量式算法IGDCLUS，它可发现任意形状的聚类，具有高效、易实现的特点，适用于数据库周期性地增量环境下的数据批量更新。     

Delaunay三角剖分在线算法

本文提出一个构造平面有限点集Ｄｅｌａｕｎａｙ三角剖分的实时算法,并给出算法正确性的 严格的征明．该算法是文献［１］所预示的一个好算法．     

基于矩阵的关联规则增量式更新算法

关联规则的挖掘是数据挖掘中的一个重要课题.实际应用中事务数据库不断更新,而发现频繁项集代价较高,因此需要提出用于数据库中关联规则的维护算法.本文提出了基于矩阵的MFUP(matrix fast updata)算法,该算法充分利用原有挖掘结果中候选频繁项集的支持数,能有效减少对数据库的重复扫描次数.实验表明,MFUP算法是高效的.