基于斜率的多边形内外点快速判别算法

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。     

多边形的简单性、方向及内外点的判别算法

本文用三维空间来解决二维平面问题，从而得出一个简单的点与有向线段之间关系的判别式，并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用于计算三角函数的判定平面多边形的简单性，方向及内外点的简单，强健而高效的算法。     

有向回路法和网格法:多边形内外点判别的新算法

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。     

平面多边形内外点判定算法评估

以前的算法评估主要是基于“时间复杂度”和“空间复杂度”进行分析的,评估结果往往是一个含有多个参数的代数式。随着计算机软硬件技术的发展,算法评估指标也应该相应发展或创新。同时,随着评估技术的发展,算法评估应尽量给出一个明确的定量评估值。提出了包含便捷性、实用性、快速性、适用性、复杂性、正确性六个因素的一套算法评估指标体系,解释了每个指标的含义以及定量化表述方法。以平面多边形内外点的判定问题为背景,对于其中7个有代表性的算法,依据前面提及的评价指标体系进行了定量化的评估。数据实例显示,提出的方法是合理的、正确的、可行的。     

映射相关边概念的多边形内外点判别算法

提出映射相关边、密切边的概念,将点在多边形内外的判别转化为点与密切边关系的判别．通过X方向的一次映射快速求取判别点的相关边,对相关边的二次映射可得到判别点的密切边．证明了根据密切边的矢量方向就可以判别点在多边形内外．在运算效率上对射线法进行改进,当多边形的边数较多时,更能体现文中算法优越性．     

判断点与多边形拓扑关系的改进算法

为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法。通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系。4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的。     

基于单调性与相关边的多边形内外点判断算法

为了充分挖掘多边形边的基本性质——单调性，基于检测点与多边形边之间的坐标关系，提出了相关边的概念及一种判断点在多边形内外的新算法。综合运用单调性与相关边技术，将点与我边形之间的位置关系转化为点与茯相关边之间的位置关系，从而尽可能地避免了叉积运算，且无需求交运算，从根本上提高了算法的效率，同时新算法还简单有效地解决了射线法中的临界位置问题。程序验证表明，新算法易于实现，适用于简单多边形，具有运行速度快、稳定性高等优点。     

再论映射相关边概念的多边形内外点判别算法

证明了文献[1](张宁宁,张树有,谭建荣.映射相关边概念的多边形内外点判别算法.计算机辅助设计与图形学学报, 2004, 16(7): 935-938)中密切边(定义3)是不正确的.在此基础上重新定义了密切边的概念,改进了文献[1]的算法,并增加了检测点在特殊位置时的判定,增强了算法的稳定性和可靠性.     

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。     

基于拓扑映射的多边形顶点凸凹判别算法

通过拓扑映射，多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题。首先求得相邻边在两条射影直线上的映射点，基于一般映射点归纳得到顶点凸凹判别的4条规则，然后将两条射影直线上的映射点归结为一条射影直线，从而得到更有效的映射点求取方法，顶点凸凹判别规则统一为两条；进一步考虑非固有映射点的求取方法，提高了算法的稳定性，实验结果表明，该算法实现简单、速度快、稳定可靠。     

判断点与简单多边形位置关系的新算法

基于射线法提出了一种新的判断点与简单多边形位置关系的算法。该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点。此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度。     

基于顶点间距离性质的凸多边形直径算法

平面点集的直径问题在计算机图形学、模式识别、图像处理、cAD,CAM等众多领域中均有广泛应用,该问题可转化为求凸多边形直径问题.研究得出了凸多边形顶点间距离关系的4条性质,利用这些性质提出一种基于顶点间距离性质的凸多边形直径算法.理论分析和实验结果表明,该算法计算速度快、存储效率高,实用性较强.     

基于斯坦纳树和泰森多边形的连通恢复算法

针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法（CRAST）。首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后,用关键节点构建Delaunay三角网,通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性。     

采用差分进化算法的点扩展函数估计

在图像处理的非盲复原算法中,对点扩散函数PSF（Point Spread Function）的估计是否准确,将直接影响图像复原质量的好坏。传统的估计方法有直接测量法和间接估计法,但往往数据量大,计算繁琐,针对这一问题,从全局寻优的角度出发,提出利用差分进化算法来估计点扩散函数。实验结果表明差分进化方法可以取得很好的效果,为下一步设计恢复滤波器奠定了基础。     

一个快速有效的凹多边形分解算法

文中在简述了传统的矢量法分解凹多边形算法之后,提出了一个快速有效的凹多边形分解算法,该算法避免了矢量法所需的大量,复杂的求交计算,因此该算法在时间及计算复杂性方面远远优于矢量法,而且该算法在三维环境中同样适用,该算法除了在多边形裁剪中有广泛的应用外,在多面体的消隐中也经常用到,并用Visual C 语言实现。     

基于关联函数的动态聚类算法及应用

根据时序立体数据的特点,提出了基于关联函数一致性矩阵的动态聚类算法。给出了适用于时序立体数据关联函数的改进标准关联函数计算公式,并将该算法应用于乙烯裂解炉报警系统,结合流程的时序立体数据,得到了裂解炉报警系统的动态聚类分类结果,并验证了提出算法的有效性。本文算法对于时序数据的聚类具有较强的鲁棒性。     

基于骨干多边形的传感器网络分区双连通恢复算法

针对现有算法恢复分区连通性存在容错性差的问题,提出了分区双连通性恢复算法DCRA。该算法旨在网络中心区域构建骨干多边形,分区以两条互不相交的路径与多边形连接,从而实现分区间的双连通。仿真实验表明,与现有一些双连通算法相比,所提算法不仅减少了部署中继节点的数量,而且算法的运行时间能够减少60%左右,可以快速确定部署的中继节点位置,从而快速恢复分区连通性。     

无人机DEM测点插值算法的矿区沉陷测绘技术

为实现对矿区沉陷深度的精准测量,完善测绘技术的具体实施方案,针对无人机DEM测点插值算法的矿区沉陷测绘技术展开研究;根据DEM测点获取结果,实施分维值测定处理,再以此为基础,确定插值拐点所处区域,实现对无人机DEM测点插值算法应用流程的完善;联合像控点布设原则,定义空中三角区域,并通过推导径向插值基函数的方式,建立矿区沉陷区域的地理模型;在空间坐标系转换条件的基础上,确定矢量数据叠加的处理结果,再结合像片倾角与旋偏角的实际取值,求解测量精度评价指标,完成无人机DEM测点插值算法的矿区沉陷测绘技术实施方法的设计;实验结果表明,上述测绘技术方法作用下,沉陷深度测量结果与矿区真实沉陷深度之间的差值不超过1 m,符合精准测量的应用需求,对于测绘实施方案的完善可以起到一定的促进性影响作用。     

基于YOLO v3算法改进的交通标志识别算法

针对目前交通标志识别任务在使用深度学习算法时存在模型参数量大、实时性较差和准确率较低的问题,提出了基于YOLO v3改进的交通标志识别算法。该算法首先将深度可分离卷积引入YOLO v3算法的特征提取层,将卷积过程分解为深度卷积、逐点卷积两部分,实现通道内卷积与通道间卷积之间的分离,从而保证了在较高识别准确率的基础上极大地减少了算法模型参数数量以及计算量。其次,在损失函数设计上使用广义交并比（GIoU）损失替换均方误差（MSE）损失,将评测标准量化为损失,解决了MSE损失存在的优化不一致和尺度敏感的问题,同时将Focal损失加入到损失函数以解决正负样本严重不均衡的问题,通过降低大量简单背景类的权重使得算法更专注于检测前景类。将该算法应用于交通标志任务中的结果表明,在TT100K数据集上,该算法的平均精度均值（mAP）指标达到了89%,相较于YOLO v3算法提升了6.6个百分点,且其参数量仅为原始YOLO v3算法的1/5左右,每秒帧数（FPS）亦比YOLO v3算法提升了60%。该算法在极大地减少模型参数量和计算量的同时,提高了检测速度和检测精度。     

基于贪心算法与多边形剖分的印鉴匹配算法

将计算几何中平面点集的三角剖分方法之一贪心算法与多边形三角剖分方法引入印鉴匹配,研究了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的印鉴匹配方法.用贪心算法对基于线条的细节点集进行三角剖分,而对于基于多边形的细节点直接进行多边形的三角剖分.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅印鉴图像进行姿势调整.最后使用获得的参考点时实现基于点模式的印鉴匹配,经分析该方法是一种行之有效的印鉴识别方法.