二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

一个快速的多边形凸包求取算法

多边形凸包算法是计算机图形学中的基础算法。本文提出一个时间复杂性为O(nlog_2n)的凸包算法:先通过极角坐标转化一般多边形为一种特殊多边形——点可见多边形,然后利用比较斜率和回溯来完成点可见多边形的凸包解。该算法将在三维立体造形系统中采用。     

基于凸片段分解和格网的点在多边形中的可见边检测

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.     

两元指纹向量聚类问题的复杂性与改进启发式算法

证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard,并给出Figueroa等人指纹向量聚类启发式算法的改进算法.主要改进了算法的实现方法.以链表存储相容顶点集合,并以逐位扫描指纹向量的方法产生相容点集链表,可将产生相容点集的时间复杂性由O(m·n·2p)减小为O(m·(n·p 1)·2p),可使划分一个唯一极大团或最大团的时间复杂性由O(m·p·2p)减小为O(m·2p).实际测试显示,改进算法的空间复杂性平均减少为原算法的49%以下,平均可用原算法20%的时间求解与原算法相同的实例.当丢失值位数超过6时,改进算法几乎总可用不超过原算法11%的时间计算与原算法相同的实例.     

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

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

确定任意简单多边形平移时碰撞部位的扫描算法

设Ｐ和Ｑ为平面内任意两个互不相交的简单多边形,若Ｐ沿方向ｄ平移时与Ｑ碰撞,采用平面扫描法,通过提取多边形的单调链,给出了求其碰撞部位的算法,最坏情况下,算法的时间复杂性为Ｏ（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ）,其中ｎ和ｍ分别为多边形Ｐ与Ｑ的边数,与现有的算法相比,降低了时间复杂性。     

大幅面地图的三维地形重建

研究完成了一个实用的可用于大幅面像素地图的三维地形重建系统.提出一个实用的 等高线内插算法,算法克服了网格绘制等值线方法和三角网绘制等值线方法因只考虑了点的位 置属性、未考虑等高线的线属性而使插出的等高线常常会与母线相交的弱点;同时提出了一个 实用的等高线高程识别算法和一个可用于大幅面地图的三维规则数据场建立算法,算法充分利 用了等高线的先验知识,不仅建立的数据场的质量很高,而且算法的时间复杂性与数据点数 (m)和网格点数(n)成线性关系O(m+n),因此计算速度很快.最后利用三维规则数据场生成真 实感图形.     

最近点问题的三角不等式算法

本文用树结构存贮有限空间的点.然后,设计了一个查找针对已知查询点的最近点的算法——三角不等式算法.整个算法的空间复杂性为O(n);预处理和查询时间复杂性分别为O(n·logn)和O(c·logn), c<相似文献   

并行递归筛选选择算法

本文提出了一个基于动态分治和递归筛选方法求解选择问题的并行算法,描述了其在无存取冲突SIMD-SMC机器上的实现.所给出的算法对于在n台处理器上求解从n个数中选取前m个或第m个最小(或最大)者的问题(m相似文献   

确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

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

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

带有给定切线多边形的C-Bézier闭曲线和B-型样条闭曲线

§1.引 言 Bézier曲线和B样条曲线已广泛应用到汽车、航空、造船等许多领域中.Hering讨论了与凸多边形每边相切的分段三(四)次 Bézier闭曲线和三(四)次B样条闭曲线.它的所有Bézier点必须通过求解大型方程组得到,计算量大,且曲线易出现拐点,而B样条闭曲线的控制点要通过反算得到[1].方逵改进了Hering的方法,构造了G2连续的分段三次曲线[2],基本上克服了Hering方法的两个缺点,但局部修改仍然是比较复杂的.方逵等再次研究了与任意多边形相切的分段四次和五次Bézier曲线[3],但五次Béier曲线不能作局部修改.本文的第二节研究了与任意多边形相切的分段C-Bézier曲线,该曲线C1连续的,且对切线多边形具有保形性,每段C-Bézier曲线上的控制点由切线多边形的顶点计算     

A Fast Hidden-line Removal Algorithm for 3-Dimensional Buildings

ＡＦＡＳＴＨＩＤＤＥＮ－ＬＩＮＥＲＥＭＯＶＡＬＡＬＧＯＲＩＴＨＭＦＯＲ３－ＤＩＭＥＮＳＩＯＮＡＬＢＵＩＬＤＩＮＧＳＱｉｎＫａｉｈｕａｉ；ＴｏｎｇＧｅｌｉａｎｇ；ＺｈａｎｇＮａｎ；ＣｈｅｎＤａｉｌｉｎ；ＬｉＹｕｎｇｕｉ；ＳｈｅｎＷｅｎｄｕＡＦＡＳＴＨＩ...     

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

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

一种新的基于中心线的双线巷道自动生成算法

针对目前双线巷道自动生成算法存在的问题,提出了一种新的基于中心线的双线巷道自动生成算法。该算法实现原理:由巷道中心线分别向两侧偏移巷道宽度的1/2距离,生成不等宽的双线巷道,双线首尾相接再生成多边形区域;任取两条巷道,求一条巷道的多边形区域与另一条巷道的双线的交点,并判断相邻两交点之间的双线是否在多边形区域内,若在多边形区域内,且一条巷道在另一条巷道的上方或相互贯通,则裁剪掉这部分双线巷道;遍历所有巷道使两两之间都经过这种方法处理,最终生成相互贯通或交叉的双线巷道图。     

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

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。     

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

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

一种改进的扫描线多边形填充算法

典型的多边形填充算法主要包括扫描线填充算法和轮廓标志域填充算法,适用于矢量多边形文件的填充算法为扫描线填充算法。论文对原有的多边形扫描线填充算法中的最常用的活性边表和传统扫描线算法进行了分析,结合活性边表和传统的扫描线填充算法的特点,针对复杂的大数据量的多边形填充时间效率较低的问题,提出了一种改进的扫描线多边形填充算法—混合填充算法。该算法采用链表和数组结合的数据结构,形成连续的填充轨迹,有效地提高了时间效率。