简单多边形凸单元剖分算法的设计及实现

简单多边形凸单元剖分是计算几何的基本问题之一，剖分算法在许多领域均有较广泛的应用。本文给出了一个利用剖分线的特征性质，剖分简单多边形为凸多边形的剖分算法。算法消除了剖分后存在部分凸多边形可以合并的现象，既能使剖分得到的凸多边形数目较少，能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率，因此有很好的实用性。     

改进的加权部分简单多边形为凸多边形的算法

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

一个简单多边形凸单元剖分的算法

通过分析剖分得到的凸多边形的结构特点，发现了剖分线的特征性质，并引入可视链及可视度的概念加以描述。在此基础上，给出了一个利用剖分线的特征性质剖分简单多边形为凸多边形的剖分算法，算法消除了剖分后存在部分凸多边形可以合并的现象，既能使剖分得到的凸多边形数目较少，又能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率，因此有很好的实用性。     

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

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

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

在计算几何中简单多边形剖分是一类基本问题。剖分算法在许多领域均有较广泛的应用。本文通过引入的扩张中心点及扩张基点的概念,描述了多边形各顶点间的位置关系。在此基础上,给出了一个剖分算法。算法具有较高的运动效率,并使剖分得到的凸多边形数目较少,形态质量较好。     

Visual C++实现单调多边形三角剖分

多边形三角剖分是计算几何的一个几何基元，它可以简化问题规模，在计算机图形学，模型识别和地理数据库方面有重要应用，低时间复杂度是设计多边形三角剖分算法的基本要求，针对现有单调多边形算法的不足，提出一个复杂度为O（N）的算法，并在VisualC^ 环境下实现这个算法。     

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

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

剖分凹多边形算法在RP扫描路径生成中的应用研究

本文对快速成型中扫描路径生成算法进行了研究,针对由分层得到的二维轮廓直接进行OFFSET扫描带来的自相交等复杂问题,提出把剖分凹多边形为几个凸多边形的算法运用其中,对轮廓进行分区域,最后在各个区域内部进行OFFSET扫描,并给出了详细的算法描述。     

基于凸剖分的点在多边形内的高效判定

提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.     

单调多边形三角剖分贪婪算法的分析与实现

分析了复杂度为 O(n)的单调多边形三角剖分贪婪算法,并用 VB 6.0实现.     

一种凸多边形直径算法

在研究凸多边形性质的基础上,构建一种新的凸多边形直径算法.该算法首先计算凸多边形顶点x坐标、y坐标的极值点,然后通过极值点将凸多边形分为几个区域,最后计算这些不同区域中顶点的距离可得凸多边形的直径.该算法简单,运行效率高.     

多边形的三角剖分及应用

文章讨论了一种简捷、实用的多边形三角剖分算法，及其在基于ＡｕｔｏＣＡＤ的图形系统开发中的应用     

圆与凸多边形重叠区域的判断及确定

通过引入进、出边交点的概念，深入研究了圆与凸多边形区域的重叠判断及重叠区域的确定问题，提出了一种新颖而实用的区域重叠判断与确定的快速算法，并给出了作出重叠区域的定理．     

判定凸多边形可移动性算法的推广

文［１］研究了两个凸多边形可移动性问题的最优判定算法，讨论了简单多边形Ｐ和凸多边形Ｑ的可移动性问题。提出了一种与［１］具有相同时间复杂度的最优算法。     

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

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

可形变简单多边形重建算法

构造了一个多边形边的形变模型，利用格雷厄姆快速算法得到平面点集凸包，通过添加点的方法有选择地修正凸包的一些边界，使得经过形变后的多边形在形状上更加接近平面点集的外形轮廓，分析了形变过程中边界附近点集的疏密对插入新点的影响，提出了2种插入新点的方法，该算法与点集中的点次序独立并且能够在一定程度上控制多边形的精度，实验表明该算法结果良好。     

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

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