混合型分区加权Voronoi图的生成算法研究

来源 :中国人民公安大学 | 被引量 : 3次 | 上传用户:sdiansean
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Voronoi图作为计算机几何中一个非常重要的研究方向,在许多应用领域都发挥着重要的作用,是一项基础性的研究工作。而分区加权Voronoi图是其中最复杂和具有代表性的Voronoi图。由于分区加权Voronoi图是一种新型图形,所以其生成算法是研究的重点和难点。经典的分区加权Voronoi图生成算法包括逐点扫描法、离散构造法和圆扩张扫描法等三种方法。本文对这三种方法进行分析和实验对比,发现这三种算法都存在着一些缺陷。逐点扫描法的优点是生成结果准确,但缺点是计算量大;离散构造法的优点是可动态模拟生成过程,但无法生成连续多块的分区加权Voronoi区域;圆扩张扫描法将逐点扫描法和离散构造法相结合,虽然提高了算法的速度和准确性,但该算法的效率依赖于Delaunay三角网的构建速度,存在一定的不稳定性。同时,该算法使用逐点扫描法判断重叠区域点隶属的方法虽然正确,但存在一定的冗余,影响了算法的效率。针对上述问题,本文开展了一系列的研究工作,提出了一种混合型分区加权Voronoi图生成算法。该算法的核心步骤是如下两个方面:第一,在生成元扇区预处理阶段,设计了一种针对扇区的填充算法,取代了圆扩张扫描法中构建Delaunay三角网的步骤,从而提高了对生成元扇区一步扩张区域的填涂速率;第二,通过实验发现,对于重叠区域内的栅格,其实不需要利用逐点扫描法来确定其隶属于哪一生成元扇区,而仅需在曾覆盖过该栅格的生成元扇区之间比较即可,通过这一发现,大幅度减少了逐点扫描的计算量。本文的最后通过大量的实验证实了该算法的正确性,并与已有的分区加权Voronoi图生成算法相比,效率得到了大幅提高。
其他文献
近些年来,电子制造业发展一日千里,作为载体的印刷电路板产量激增,其焊点的质量检测备受关注。传统方法一般依赖人工,精度低、耗时长,目前已经无法满足自动化、高速、高精的生产诉求,亟待改进。本文所开发的在线焊锡质量检测系统通过运动平台带动基恩士超高速轮廓测量仪进行检测,与传统方式相比,具有高速度高精度的优点,系统从三维角度对焊点点云进行特征提取有效的降低焊点处理的复杂程度。本文通过对焊锡质量检测相关工作
自由空间光通信(FSO)系统具有频带宽、速率高、保密性好、抗干扰能力强和设备体积轻小等突出优点,相比于微波通信系统,FSO更适合星地链路通信,由此引发了FSO系统研究热潮。然而光信号通过大气信道时,湍流效应会导致光信号的光强随机起伏,造成FSO系统误码率增大,最终破坏通信。为了改善FSO通信性能,寻求能抑制大气湍流影响和提高传输速率的调制方式是目前FSO系统的研究关键。本文以此为背景,分析对比了基
微滴喷射技术是一种在近年来得到广泛关注的新型技术,其主要用于形成微型液滴或者施加少量样品。其主要应用的领域有3D打印、微电子封装、基因工程和生物医药工程等。传统的微滴喷射技术有压电法、热泡法。近年来,气动法和电流体动力学(Electrohydrodynamic,EHD)法等非传统微滴喷射技术也广受关注。本文分析了气动法和EHD法的主要优缺点:气动法的优点为按需喷射较为稳定,缺点为微滴尺寸较大;EH
本文考虑平面上具有边长限制的斯坦纳树问题,其具体描述如下:在欧氏平面上给定n个终端点集合X= {r1,r2...,rn}及长度为L的材料若干,非负常数l及构建一个斯坦纳点费用c1,单位
随着智能电表厂商、电表种类越来越多,分散式的本地测试不利于对测试数据进行整合分析和系统管理。因此如何整合分布式的测试资源和方案,提高测试效率,降低成本,是当前智能电
当前时代,经过长期的业务经验及众多的研究得出,一个公司如果想发展,且在日益激烈的竞争中始终处于优势地位,其问题的核心在于要充分发挥人员的能动作用,把公司的人才优势转
由于噪声和混响等因素的存在,各种人机语音交互系统中的语音质量会受到严重影响。为了减少这种影响,需要对采集的语音信号进行增强。传统的单通道语音增强方法往往只对带噪语音幅度谱进行增强而忽略相位谱的增强,使得其在低信噪比等复杂声场景时的语音增强性能受到限制。传统的多通道语音增强方法还未充分利用声源的空间信息和语音的相位信息,其声源估计的准确性还不够高,抑制外来干扰和噪声的能力有待提升。为解决上述问题,本
度量次正则(metric subregularity)是优化与数学规划中的重要概念.本文主要在有限维空间中研究广义方程的度量次正则性,利用极限法锥和余导数(coderivatives),给出了广义方程
乳腺癌是当前严重威胁女性健康的主要恶性肿瘤,对它的治疗越来越多的受到人们的关注。目前,临床上治疗乳腺癌的方法有多种,主要有手术、放疗、化疗、内分泌治疗及生物治疗等,
位于黄土高原中部的泾河流域是中国农牧业文明的发祥地之一,随着人口增长与社会经济发展,泾河流域的社会系统与自然环境以水资源为纽带,在长时期里发生了紧密的耦合与共同进化,也伴生出了流域生态退化、水质恶化、水资源缩减等诸多水与生态环境问题。当前,国家正在构建生态文明体系,大力推进生态文明建设,如何在既保障流域社会系统经济发展与兼顾生态保护与修复的夹缝中寻找出一条绿色可持续的流域高质量发展道路意义重大。然