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

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

求解简单多边形间包含关系的扫描线算法

对于任意给定的一簇互不相交的简单多边形，本文提出一种旨在确定簇中多边形之间包含关系的扫描线法，并对其正确性和复杂性作出分析。实践表明此算法是很有效的     

简单多边形凸凹性自识别算法

提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性,凸凹性的算法,该算法在稳定性方面采取了有效的措施,避免因极值顶点的奇异性而导致多边形方向性,凸凹性的错误识别,具有良好的可靠性和稳定性,算法原理直观简单,效率高,时间复杂度为O（n).     

判定一点是否落在简单多边形内

判定一点是否落在一个简单多边形内,是计算几何领域内的一个基本问题,本文详细讨论了解决该问题的奇偶法,给出了一个自然、简明的编程方法。     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

一种多边形方向识别的新算法

针对传统经典叉积法在识别任意简单多边形方向时不能解决奇异情形的问题,提出了多边形方向识别的特征点比较法,用列举法作了几何证明。算法中的运算主要是整数之间的大小比较,因而速度较快。并且有效地解决了奇异情形下的方向识别问题。分析表明,该算法能对所有简单多边形作出正确的方向判断,具有较好的通用性和鲁棒性,可以发展成为独立的方向判断算法。实验表明,该算法比叉积法具有更高的执行效率。     

简单多边形核求解新算法

简单多边形的核是位于多边形内部的一个点集,而且这个点集中的任意一点与多边形边界上的任意点的连线都属于这个多边形的内部。核的这一性质在监视器安放等问题上得到了应用。考察了简单多边形的核在构成方面的性质,结合已有的成果,提出了一种求简单多边形核的新算法。该算法可以较快地对多边形的核为空的情况加以报告,而且在有核的情况下快速求解到核多边形的顶点序列。新的求核算法容易理解,而且易于实现,可以广泛地应用于实际问题。     

一种判定点和多边形包含关系的有效方法

在分析现有点与多边形包含关系的判定方法的基础上,提出了将判断点绕多边形的一个适当顶点为中心逆时针旋转,根据判断点依次旋转到该顶点前后两边时两个旋转角的大小关系来判定点的位置的思想,并以此为基础提出了一种判定点与多边形的包含关系的有效方法。     

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

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

线点包容检测算法

提出的算法是先以快速的方法判断线与多边形是否有交点,如有,则求出线与多边形的各个交点,将交点进行排序,将此线按交点顺序分为多段;如果无交点,则此线只有一段。检测各段中点是否位于多边形内,如果位于内部,则此段在内,否则此段在外。以倾斜射线法检测点的包容性,其特点是此射线不与多边形的顶点或边重合,无须作特殊情况的处理,计算区域小,因而计算量小,对自相交多边形及带孔多边形等多类情况同样适用。通过编写程序计算验证表明,此算法简单有效、稳定可靠,适用于多类情况。     

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

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

判断点与指定多边形区域的关系的改进算法

介绍了判断点与多边形关系的多种方法,详细给出射线法,并对该方法进行优化,并给出了算法。在实验过程中该算法排除了一些点的判断,只需执行少量的射线法函数,实验结果表明,该算法简便、可靠、执行速度快。     

基于轨迹计算的临界多边形求解算法

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题．该算法的基本原理是：1）求解多边形顶点相对于另一多边形的轨迹线;2）求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形．该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度．     

基于单调链的简单多边形距离算法

简单多边形的距离问题是计算机图形学中的一个研究难点,为了能快速地获得距离信息,提出一种基于单调链的简单多边形距离算法.算法先对多边形边界进行关于坐标轴的单调链分割,然后根据可见性原则确定候选链对,再结合层次树理论和分支限界策略计算链对距离以求解多边形的最近距离.试验结果表明,该算法性能优于其他同类算法.     

一种改进的点在多边形内外判断算法

为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。     

多边形中心点向量的二次插值变形算法

多不动点约束下的网格变形算法需要用户确定不动点和操作点,针对该问题,提出多边形中心点向量的二次插值变形算法。该算法根据源、目标多边形中心点向量间旋转经过的面积与2个向量间的差值建立相似度函数,在变形过程中采用二次贝塞尔插值方法,在对应过程中利用改进的动态规划算法。实验结果表明,该算法可减少变形过程中多边形内部扭曲的程度,且计算量小、对应时间短、变形效果自然。     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。