简单多边形可见点问题的快速求解算法

简单多边形可见点问题是计算几何的基本问题之一。在许多领域均有应用。本文在参考现有算法的基础上,提出了改进的方法,文中方法先用射线法求取第一个可见点,然后利用文中设定的规则搜索后续可见点。     

简单多边形可见核的扫描线填充算法

简单多边形的可见核是位于多边形内部的一个点集，可见核内的任意一点与多边形边界上的任意一点的连线都处于该多边形的内部。由于可见核具有这一性质，对简单多边形的可见核的计算在很多方面都有着适用。本文考察了简单多边形的核的性质与特点，在结合了其他相关的可见核顶点的算法之后，提出了一个对可见核进行填充的快速算法。这一算法由于通过避免在填充多边形的核之前进行计算可见核的顶点的过程，从而可以较快地对可见核进行填充。这一算法不仅容易理解，而且便于实现。     

面向快速制造扫描分区的凹多边形凸分解算法

提出了一个面向快速成型扫描路径规划的凹多边形凸分解算法。首先应用所提出的基于正负法搜索凹点对应的可见点的新算法来找出凹点的可见点串,然后结合所提出的适用于快速制造中扫描分区的剖分准则,利用权函数选择最佳剖分点,并合理使用辅助点,保证了剖分所得凸多边形的形态质量。该算法作为快速成形选区环形扫描路径规划软件的底层算法,在对待扫描的层面轮廓进行分区时得到了应用。     

基于象限划分的简单多边形方向与顶点凸凹性快速判别算法

文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系：不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘／除法”运算;算法利用“假设一检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O（n）。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。     

平面多边形顶点的凹凸性快速自动识别方法

本文介绍了一种通过运用矢量运算方法对平面多边形顶点的凹凸性进行快速自动识别的原理和方法。该方法自动识别准确、可靠性高,已成功地应用于快速成形技术的分层实体制造过程中激光光斑半径的自动实时补偿。     

多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.     

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

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

一个加权剖分简单多边形为凸多边形的算法

本文提出了可以为简单多边形中的可视点对建立一种权函数，这种权函数容易计算，可以反映在点时间加入剖分线时获得剖分在形态质量方面的性质，因此可以用来引导剖分，描述了一个利用这种权函数加权剖分简单多边形凸多边形的算法来实现步骤，讨论了所建立算法的生质，结果表明算法既能够使剖分得到凸多边形数目较少，又能够使得的部分有较好的形态质量，因此有很好的实用性。     

简单多边形凸单元剖分的编码算法

本文通过对凹对分类编码的研究，提出了一种复杂度为Ｏ（ｎ＋Ｎ＾２）的简单多边形的凸单元剖分算法。     

基于直线斜率的凸多边形线裁剪算法

凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,现在的许多领域均有很重要的应用。本文提出了一种非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较。结果表明：本算法更加简单、高效。     

A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON

ＡＮＥＷＣＯＮＶＥＸＨＵＬＬＡＬＧＯＲＩＴＨＭＦＯＲＡＮＹＰＯＬＹＧＯＮＨｕＺｈａｎｑｉＬｉＹｕｐｅｎｇＷａｎｇＪｕｎＱｉａｏＬｅｉＡｂｓｔｒａｃｔＡｎｅｗａｌｇｏｒｉｔｈｍｆｏｒｆｉｎｄｉｎｇｃｏｎｖｅｘｈｕｌｏｆａｐｏｌｙｇｏｎｉｓｐｒｏｐｏｓｅ...     

一种基于几何关系编码的高效凸多边形线裁剪算法

提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪.实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右.如果m的数值也较大时,该算法的速度还将大大提高.所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性.     

一种新的任意多边形的快速填充算法

本文在分析现有多边形填充算法基础上,提出了一处新的针对任意多边形的快速填充算法。引入了点三种转换方式概念,通过建立多这形的扫描转换点表和边表,利用动态的有效边表,用直接写屏 技术来实现任意多边形的实区域的快速填充。     

基于边界识别的多边形的布尔运算

多边形的布尔运算是图形学的一个重要问题，但目前的算法对线段的属性规定均较复杂，且对某些情况还不是很有效，这是因为没有利用运算的对象、结果都是多边形这一事实。本文试图将多边形的布尔运算建立在多边形识别的基础上，以简化线段的属性规定，使算法更有效，更具有一般性。     

基于多分辨率的快速迭代最近点配准算法

针对迭代最近点(Iterative Closest Point,ICP)算法计算时间长的问题,提出一种基于多分辨率配准点的ICP算法。使用自适应体素网格滤波器对原始点云进行多分辨率采样,利用低分辨率点云快速迭代获得两点云间初始变换矩阵;利用高分辨率点云在初始变换基础上做更精确配准。实验结果表明,该算法在配准精度基本不变的情况下,可以显著降低配准时间,且随着点云点数增加,速度提升效果越明显。