求平面点集凸壳的一个最优算法

本文提出了一个求平面点集凸壳的格雷厄姆方法的一个改进算法。算法首先按照格雷厄姆方法将点集中的点进行分类，将分类后的点连成一个特殊的简单多边形，然后删去简单多边形的单个凹点、连续凹点，产生新的简单多边形，再删去新简单多边形的单个凹点及连续凹点，循环往复，最后得到的凸多边形即为点集凸壳的边界。本算法理论严密，易于理解，易于实现，时间复杂性也是。     

平面点集凸壳的快速算法

提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算（除最坏情况外）,从而节省计算时间。     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法。该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳。由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率。在最坏情况下该算法的时间复杂度为O(NlogN)。     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法.该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳.由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率.在最坏情况下该算法的时间复杂度为O(NlogN).     

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。     

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题，并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH（S）中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先农层计算线段集S的凸壳，并将这些凸壳改变为简单多边形；然后计算各多边形之间的交点，进而删去这些交点；最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时，用分治思想设计分治算法，较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。     

求平面点集凸壳的一种新算法

在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点,构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束。这样就得到四个简单多边形单调链,然后对单调链求凸点,时间复杂度为O（n）,最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过O（n log n）。     

计算多边形交集、并集面积的算法

平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表，在遍历链表时遇到交点就改变跟踪方向，这样可以求出并集顶点表，求交集时只要从入点开始跟踪遇到交点再改变跟踪方向；最后，通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

任意多边形顶点凸凹性判别的简便算法

给出了一种确定任意多边形顶点凸、凹性的简便算法.该算法只需要n+4次乘除法,平均3n次加减法及4n+3次比较即可完成(n是多边形顶点的个数).     

Finding the convex hull of a simple polygon

We describe a new algorithm for finding the convex hull of any simple polygon specified by a sequence of m vertices.An earlier convex hull finder of ours is limited to polygons which remain simple (i.e., nonselfintersecting) when locally non-convex vertices are removed. In this paper we amend our earlier algorithm so that it finds with complexity O(m) the convex hull of any simple polygon, while retaining much of the simplicity of the earlier algorithm.     

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

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

基于凹凸顶点判定的简单多边形Delaunay三角剖分

提出一种基于凹凸顶点判定的简单多边形Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出简单多边形的凹凸顶点,然后,逐次割去一个权值最大的三角形构造三角形网络,修改多边形顶点链表,并重新计算受影响的顶点的凹凸性。重复这个过程,直到边界顶点链表空为止。     

平面轮廓的螺旋填充轨迹生成算法

在快速成型和数控领域中对平面轮廓区域的填充是比较繁琐复杂的步骤。为充分扬弃顶点偏置和线段偏置的优缺点,提出了顶点线段混合偏置算法,即在凹点处采用线段偏置,而在凸点处则采用顶点偏置或插入线段方式;为优化起落刀次数,提出用对角曲线连接偏置曲线形成螺旋轨迹的算法,即在归类相同的相邻两条偏置曲线中,以顶点较多的作为主偏置曲线,利用K-D树在相邻多边形查找主偏置曲线每个顶点的最近点,依次求出对角曲线的离散点并且连接获得螺旋轨迹。     

基于方向包围盒投影转换的轮廓线拼接算法

基于轮廓线拼接算法重构三维模型时,由于拼接对象的复杂性,任何一种拼接方法都不能完全涵盖所有情况。为此,提出一种基于方向包围盒(OBB)投影转换的轮廓线拼接算法：首先判断多边形的顶点凹凸性,对于凹顶点,将其转换到对应的凸包上;然后计算凸包的方向包围盒,旋转平移矩形包围盒,并求包围盒内接椭圆,将每个顶点都按比例投影此椭圆上;基于投影后的点进行轮廓线拼接,寻找相邻轮廓线顶点之间的对应关系;最后还原实际坐标,进行原始模型的三维重构。     

一个有效的多边形窗口的线裁剪算法

已有的线剪裁算法都是针对矩形窗口或凸多边形窗口的,对于一的多边形窗口（包括凹多边形）的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义。该文提出一个对于一般多边形窗口的线剪裁算法。该算法在被裁剪直线的延长线上取一固定点,然后求多边形窗口的每一顶点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间,就可判定直线与边是否相交,因此,每处理一     

遗传算法在曲线多边形近似中的应用

在平面数字曲线的多边形近似中,为克服顶点的检测只依靠部区域,缺 乏全局信息的弱点,文中把多边形近似问题作了寻找在满足一定的近似误差下使顶点数最少,或者使顶点数和近似误差都尽可能少的最优化问题来处理。     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。