一种判定简单多边形可视顶点的算法

简单多边形可视顶点的判断是计算几何的一个基本问题,广泛应用于许多领域。尤其是在凹多边形凸分解问题中。而作为其基础的判断顶点可视性的算法却极少,既有算法本身过于复杂,不利于实际应用。本文参考有关判断点在多边形内外的算法,提出了解决判定简单多边形可视顶点对的新算法,应用于软件CSforecast,实践证明该算法具有简洁,可靠、运行速度快等特点。     

基于顶点凸凹性多边形的核的算法

简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。     

求解简单多边形核的新算法

利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对多边形的核为空集的情况加以报告.在多边形有核的情况下,裁剪过程不断更新包含核的多边形,快速求解得到包含核的凸多边形,从而可以采用凸多边形的线裁剪算法来加速求核计算.新的求核算法在快速判断出空核和提高求核速度方面都有较大改进.     

一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只用加、减运算就能求水平线与凹多边形边界交点的方法。并根据顶点类型定义,将凹多边形顶点分成“水平顶点”、“极点”、“拐点”三类,设计了基于三类顶点的边界存贮结构,建立了凹多边形水平扫描填色算法,解决了当交点为顶点时可能产生的“交点对”不配对的问题。     

一种处理交点退化现象的高效多边形裁剪算法

针对复杂多边形裁剪中出现的多边形彼此间重点和重边现象,提出了一种能够处理交点退化现象的高效多边形裁剪算法.该算法利用单向链表实现多边形的存储,同时基于单调链的平面扫描法求解多边形间的交点,减少了多边形顶点的遍历次数和求交次数;对于重点和重边现象,通过交点关联的线段间的方向关系判别交点的进出性;最后更新多边形顶点序列,获取裁剪结果.实验结果表明,该算法能够完成对含内环多边形的裁剪,在交点退化情况下也能获得准确的裁剪结果.且该算法裁剪效率较Greiner-Hormann算法大幅提高,具有很高的执行效率和实用性.     

带岛屿多边形Delaunay三角剖分算法

提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值.     

基于二分法判定点集是否在多边形内部的算法

提出一种基于二分法判定点集是否在多边形内部的算法,根据多边形L的顶点和边分布的情况,分割平面的一组平面区域的有序集合R,判定R中每个区域是否在多边形L内部;对于点集S中的点p,用二分法搜索R,找到点p所属的平面区域,从而判定出点p是否在多边形内部。该算法在最坏情况下的时间复杂性为max(O(n log m),O(tm log m),其中n为点集S的点数,m为多边形L的顶点数,t为多边形L所有顶点的X坐标的不同取值个数,在一般情况下该算法比已有的算法效率更高。     

简单凹多面体的Minkowski和

在欧几里德三维空间中,求两个多面体的Minkowski和是一项重要的几何操作,它等同于求两个多面体中所有点的矢量和。本文在之前提出的简单凹多边形的凸剖分算法基础上,给出了基于多面体剖分的简单凹多面体的Minkowski和算法。分析表明,该算法由于减少了计算Minkowski子和的数目,从而能够提高整个求和算法的速度。     

基于简单凹多面体的凸剖分算法

本文依据凹多边形的特征,把其分为梳状多边形和普通凹多边形,并采取不同的剖分策略。对于梳状多边形,依据其特征采用角平分线划分,能够得到最少数目的凸多边形;而对于普通多边形以对角线划分为主,角平分线划分为辅,每次能够划分出包含顶点个数尽可能多的凸多边形,最终能够得到次最少数目的凸多边形。从而减少计算Minkowski子和的数目,提高了整个Minkowski和求和算法的速度。     

一种简单多边形凸包的快速算法及程序设计

给出了一种求简单多边形凸包的快速算法，此算法采取将各个点按与X轴的夹角顺次排列，然后逐渐地删除凹顶点，求得简单多边形的凸包，并给出了算法的数据结构．算法达到了O(nlogn)的理论时间复杂度下限．     

确定任意多边形顶点凸凹性的快速算法

给出了一种确定任意多边形顶点凸凹性的快速算法．该算法的时间复杂度是多边形顶点数目的线性函数     

任意多边形三角剖分的算法

提出了将任意多边形三角剖分的算法．其方法是，首先确定多边形各顶点的凸凹性，然后不断切割多边形的不规则部分，使其成为凸多边形，最后对凸多边形进行三角剖分．证明了算法的正确性，并对该算法的复杂性进行了分析．     

多边形内点集的三角剖分算法

提出了一种多边形内点集的三角剖分算法，该算法采用逐层求凸壳，对不在凸壳边界上的多边形顶点给予特殊处理，然后逐层分割环域成三角形序列，最后优化各三角形的边长，改变分割方式，使之能得到最短长度或接近最短长度的三角剖分．     

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

提出判定点是否在多边形内部的一种算法，其方法是判定射线与多边形边的交点数目以及必要时移动该点的位置，再判定交点的数目，该算法的时间复杂性为Ｏ（ｎ）次四则运算和Ｏ（ｎ）次比较，其中ｎ为多边形的顶点数。     

铺砌中椭圆上D-点数的研究

阿基米德平面铺砌是指用一种或多种正多边形铺砌全平面,且要求铺砌的每个顶点的顶点特征相同。阿基米德平面铺砌共有11种,针对其中的[4.8.8]铺砌,即每个铺砌顶点连接边长相同的一个正方形,两个正八边形,研究[4.8.8]铺砌上的椭圆所包含铺砌顶点数的特性,通过对椭圆内半弦上顶点列的分析,采用数的几何及数论中同余的方法给出顶点数的取值算法,并获得顶点数与椭圆短半轴长平方的比值的极限公式,证明极限值与对应铺砌的中心多边形的面积有关。所得算法及极限公式对其他阿基米德铺砌中相关问题的研究有借鉴作用。     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

冲裁件优化排样的多边形顶点射线算法

研究冲裁工件优化排样问题.在普通单排多边形顶点算法的基础上,针对对头单排、普通双排、对头双排3种排样方式的特点,提出一种多边形顶点射线算法.经实际测试证明,该算法克服了多边形顶点算法通用性差的局限,可高效准确地得出常规单件排样方式的最优解.应用改进算法,在AutoCAD2000上,通过ObjectARX2000开发出了冲裁模优化排样系统.应用结果表明,与原手工排样方案相比,节省材料率约10%.