改进的基于mean value重心坐标的多边形变形

对平面多边形的变形,为了避免变形过程中边界的退化和自交现象,目前主要采用将初始多边形与目标多边形分别嵌入到具有凸边界的同构三角网格中去,转化成三角网格的变形问题。但该方法在进行同构三角剖分时,增加的额外点数目较多,复杂度高,且不能实现刚性变形。论文提出一种基于多边形星形分解的同构三角网格剖分算法,使用较少的额外点,降低了算法复杂度。此外,文中选择正多边形作为三角网格的边界,并采用刚体变形技术以保持初始多边形和目标多边形尽可能刚性地变形,取得了较好的变形效果。     

基于广义形态内插的非刚体运动描述方法

提出一种基于形态变换的非刚体运动的广义内插方法.通过对非刚体的凸剖分及凸子集全局优化匹配,与传统的线性内插方法相比,解决了任意非同拓扑结构(包括有孔及凹多边形)的内插问题.理论证明,此种内插方法是一种全局优化的内插方法,并证明了此方法的正确性,讨论了不同凸剖分对内插的影响,把非刚体的运动分解为非刚体的变形与刚体的旋转.实验证明,此内插方法效果自然,质量好,速度快,可用于非刚体运动描述及二维动画关键帧的内插.     

基于形状特征的可避免自交的平面多边形变形

给出了平面简单多边形的一种基于形状特征的可避免自交的变形方法。该方法将初始和目标多边形分别嵌入到以其放大的凸包边界为边界的同构平面三角网格中,通过采用对所嵌入的同构网格进行变形的方法,实现了平面多边形的变形。与已有的Surazhsky和Gotsman的方法相比,该方法考虑了初始和目标多边形的几何轮廓及其差异性,故变形过程更加自然,而且在网格剖分时使用了更少的额外顶点,因而提高了算法速度。     

求平面多边形集凸壳的方法

提出一种计算平面多边形集凸壳的快速算法。将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段,同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段,凸壳的每一段仅受多边形同一类点列段的影响。根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选,再按给定规则在矩形区域中进行初始找点,可求出四段凸壳初始点列,它们按顺序可确定一平面多边形,求出到此多边形的凸壳即为所求多边形集的凸壳。算法通过分段、分类、筛选等措施提高了计算效率,并且易于实现,其时间复杂度为O（N）。     

零阶连续曲线包络的计算*

包络理论中通常采用速度与法矢正交的条件来判断曲线族上的点是否为特征点,它要求曲线至少C1连续,而对于C0连续的曲线则无能为力。在此背景下,提出了扩展的包络条件来适应C0连续的曲线包络的计算,并证明了在C1连续条件下扩展包络条件是传统包络条件的充分非必要条件;在此基础上,提出了一种新的任意非凸平面多边形变形包络的计算方法。最后,通过实例验证了理论和方法的正确性。     

同构平面三角网格的保凸变形方法

对于具有不同凸边界的同构平面三角网格的变形,提出了一种简单、有效的方法．该方法结合了两种已有的算法．能够保证网格边界在变形过程中始终保持凸性,且任意时刻的中间网格与初末网格同构,即不产生自交现象;同时文中方法实现了两个凸多边形的保凸变形。     

寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选，使剩余顶点的角的大小排成递增序，然后用Graham扫描方法删去非凸壳顶点，最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点，最后得到凸壳顶点序列。这两种算法简单，易于实现，时间复杂性都是O（n)。     

基于三角形分解和重构的平面多边形变形方法

为解决较复杂的不同拓扑结构的二维形状渐变问题,提出一种基于三角形分解和重构的平面多边形变形方法.该方法将图形多层分解为三角形,保留分解过程中的各层边角信息;然后通过线性插值各层边长比例及角度,并结合刚性变换方法重构中间多边形的细节和框架,以达到变形的目的.该方法适用于任意点数的多边形,具有一般性.实验结果表明,文中方法能很好地解决变形序列中的萎缩问题,并且对较复杂的狭长图形也能避免自交现象,变形效果自然.     

一种基于条件骨架的拐点检测方法

把原始图像看成一个多边形,则形态条件骨架的延长线一定通过多边形的顶点,通过检测条件骨架中最大圆盘半径为零的点来获得凸点的拐点,并由它的补图来获得凹点的拐点.全部拐点由原图及补图的拐点进行逻辑异或操作获得并可去掉离散化后产生的网格拐点.此方法定位精度高、速度快,易于硬件实现和并行处理.由于先用较大圆盘做初步检测,可以降低噪声干扰.利用两种新的大圆盘,此方法可推广到灰度图像的拐点检测.     

一种快速的复杂多边形匹配算法

提出了一种能够快速进行复杂形状多边形匹配的算法，该算法基于正切空间表示，先对复杂多边形进行离散曲线演化，再将得到的简化多边形分为一系列最大凸/凹弧线，并选择每段最大凸弧线的起点作为匹配的起始点进行匹配。实验结果证明该算法不但能够对复杂多边形快速而精确的匹配，而且具有不受噪声影响的优点。     

基于夹边边对的凸多边形间快速相交检测算法

本文在对现有的相交检测算法进行研究的基础上，提出了基于夹边边对的空间平面凸多边形快速相交检测算法，为平面凸多边形间判交问题提供了一致的计算方法，并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步：第一步，确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对，如果至少一个凸多多边形中不存在相对于另一凸多边形所在平面的夹边边对，那么立即返回两个多边形不相交；第二步，根据前面计算得到的两个凸多边形中的夹边边对，计算两组边对间对应夹边的符号距离判断两个多边形是否相交     

Clamping a polygon

Aclamping hand has two opposing parallel edges; the distance between them can vary. We define what it means for the edges of a clamping hand and some edges of a polygon to form aclamp on the polygon. We conjecture that any polygon can be clamped by a hand if its edges are of positive length, but only provide proofs that clamps must exist for convex polygons and for certain polygons composed of two convex chains. The proofs involve extensive case analyses, and it is not obvious how to generalize them.     

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

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

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

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

一种新的凸多边形不干涉算法

求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O（n+m）。     

Optimal BSR Solutions to Several Convex Polygon Problems

This paper focuses on BSR (Broadcasting with Selective Reduction) implementation of algorithms solving basic convex polygon problems. More precisely, constant time solutions on a linear number, max(N, M) (where N and M are the number of edges of the two considered polygons), of processors for computing the maximum distance between two convex polygons, finding critical support lines of two convex polygons, computing the diameter, the width of a convex polygon and the vector sum of two convex polygons are described. These solutions are based on the merging slopes technique using one criterion BSR operations.     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

简单多边形分解成凸多边形差组合的算法

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。     

临近特征点类型匹配的多边形渐变表达模型

提出一种基于Morphing技术的多边形连续尺度地图表达模型。依据多边形的凸壳多叉树建立了多边形特征点的层次结构;基于临近性原则及特征点前后弧段形状的对照关系实现两个关键尺度的同一多边形要素各层次特征点的匹配;在多边形的对应特征点间利用Morphing内插技术得到两个关键尺度间任意尺度的多边形表达。实验表明,对于两个关键尺度下的同一多边形,使用该模型能获取任意中间尺度下的多边形表达,在尺度变化时,多边形图形的过渡自然平稳。