用最小回路求两个简单多边形的交、并、差集

针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m 分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。     

参数曲面分割求交算法之改进

本文认为,在传统的参数曲面分割求交算法中,由于近似多边形存在厚度,因此不能用简单的方法计算近似多边形的交线。文章提出了一种改进的算法,该算法以整体的观点考察多边形的面、边、点之间的关系,把两多边形之间的求交放到全体多边形中去考虑,从而避免了两参数曲面的交线出现裂缝、丢失或增多的现象。实践证明,这种改进算法是可靠的。     

带孔洞多边形的求交算法

为简化已有任意简单多边形求交算法并提高算法效率,首先将交点分类并排序,然后采用不同的遍历方法得到多边形的交集、并集和差集,在该算法的基础上设计带孔洞多边形的求交算法．所有算法均被实现,且复杂度较低,鲁棒性较好．     

一种含有圆弧的曲线快速求交方法

二维曲线的求交是CAD&CG中的一个基本问题,论文提出了一种由圆弧和直线段组成的二维曲线快速求交方法。首先选择一个最优方向,根据最优方向把封闭曲线分割为一系列单调链,然后通过拓展Bentley-Ottman的扫描线算法对单调链进行求交。算法时间复杂度为O((n+k)logm),其中n为顶点个数,k为交点的个数,m为划分的单调链的个数。     

基于空间多边形三角剖分的曲面分割求交算法

针对传统曲面分割求交方法存在的平面片的选取、遗漏部分交线段以及交线间断 的问题,提出一种基于空间多边形三角剖分的曲面分割求交算法。以等深度分割方法为基础, 避免了交线不连续的问题,当分割达到一定层次时以空间多边形近似曲面片,并对空间多边形 进行三角剖分,以三角形对的交线近似空间多边形之间的交线,进而以空间多边形的交线近似 曲面片的交线,最终得到相交曲面之间的交线。利用曲面片轮廓构造出的空间多边形更加接近 曲面片的真实形状,提高了逼近精度,同时对空间多边形进行三角剖分,提高了求交精度,进 而降低了丢失交线的可能性。实验验证了该算法比传统的分割法更加精确。     

用VC++实现的任意多边形裁剪算法

提出了一个用VC++语言实现的凸多边形、凹多边形,也可以是带内环的多边形的裁剪算法,可以求上述多边形的"交"、"并"以及"差".首先,该算法使用VC++支持的CObList类和CArray类的对象存储数据,具有占用内存空间少及处理速度快的特点;再通过算法和数据结构的设计不仅使得多边形顶点可按顺时针方向或逆时针方向输入,而且减少了求解过程中对多边形顶点数据的遍历次数;基于判断和计算交点是裁剪算法的主要工作,文中引入了求交前的预处理,避免了大量不必要的求交,降低了算法的时间复杂度.最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理.     

光线与多边形的快速求交

本文提出了一种新的光线与多边形的快速求交算法，以用于加速光线跟踪过程中的求交计算，这种算法不仅对凸，凹多边形（无论有无内环）都适用，而且无中间数据的存取，无除法等复杂运算，算法简单，便于在一般软硬件环境下的实现。     

基于单调链的简单多边形距离算法

简单多边形的距离问题是计算机图形学中的一个研究难点,为了能快速地获得距离信息,提出一种基于单调链的简单多边形距离算法.算法先对多边形边界进行关于坐标轴的单调链分割,然后根据可见性原则确定候选链对,再结合层次树理论和分支限界策略计算链对距离以求解多边形的最近距离.试验结果表明,该算法性能优于其他同类算法.     

任意多功形单调链剖分算法

通过扩展计算几何中的“单调链”概念，提出了一种新的任意多边形剖分算法。首先利用新的概念将任意多边形分解为单调链，其后对单调链尖点排序，最后在相邻单调链间进行分割，从而完成任意多边形的剖分。算法的时间复杂度为Ｏ（ＮｌｏｇＮ）。本文最后给出了算法在用ＧＬ对实体模型进行光照中的应用。     

一种GIS拓扑多边形链搜索的改进算法

针对GIS拓扑多边形链搜索中悬挂弧段的处理问题,提出了一种改进算法。该算法利用在一趟搜索中,非悬挂弧段仅经过一次,而悬挂弧段会经过两次这一规律来识别并标记悬挂弧段;在进行多边形链搜索时,通过避让悬挂弧段以避免将其对应的关联弧段加入多边形链,从而保证搜索结果的正确性。测试结果表明,该算法能明显提高多边形链搜索的效率。     

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.     

A scanline algorithm for displaying trimmed surfaces by using Bézier clipping

Displaying objects with high accuracy is necessary for CAGD (computer-aided geometric design) and for the synthesis of photo-realistic images. Traditionally, polygonal approximation methods have been employed to display free-form surfaces. They bring on low accuracy of display not only in shape, but also in intensity of objects. In this paper, a scanline algorithm to directly display parametric surface patches, expressed by trimmed Bézier surfaces, without polygonal approximation is proposed. In the method proposed here, curved surfaces are subdivided into subpatches with curved edges intersecting with a scanline, and the intersections of every subpatch and the scanline are calculated. This method is extremely robust for calculating the intersections, which can be obtained with only a few iterations; the Bézier clipping method is used for the iteration. Anti-aliased images with shadows and texture mapping are given to show the effectiveness of the method proposed.     

Adaptive generation of surfaces in volume data

A widespread approach to generating polygonal approximations of iso-surfaces or contour surfaces in volume data is the socalled marching-cubes algorithm. This algorithm, however, has the disadvantage that the number of polygonal chains generated is considerable. The splitting-box algorithm presented here reduces the number of polygonal chains by adapting their size to the shape of the surface. The resulting polygonal chains offer a wide spectrum for representing the contour surface. An exact representation is achieved by a new type of generic patches calculated from the polygonal chains. Approximations of different quality may be obtained by combining the algorithm generating the patches with simple triangulations.     

A simple algorithm for detection of significant vertices for polygonal approximation of chain-coded curves

A simple but efficient method is proposed for detection of significant points of chain-coded curves. The polygonal approximation is achieved by joining successive significant vertices. The algorithm is based on manipulation with chain codes only.     

Geometric Restrictions on Producible Polygonal Protein Chains

Fixed-angle polygonal chains in three dimensions serve as an interesting model of protein backbones. Here we consider such chains produced inside a "machine" modeled crudely as a cone, and examine the constraints this model places on the producible chains. We call this notion producible, and prove as our main result that a chain whose maximum turn angle is α is producible in a cone of half-angle ≥ α if and only if the chain is flattenable, that is, the chain can be reconfigured without self-intersection to lie flat in a plane. This result establishes that two seemingly disparate classes of chains are in fact identical. Along the way, we discover that all producible configurations of a chain can be moved to a canonical configuration resembling a helix. One consequence is an algorithm that reconfigures between any two flat states of a "nonacute chain" in O(n) "moves," improving the O(n²)-move algorithm in [ADD+]. Finally, we prove that the producible chains are rare in the following technical sense. A random chain of n links is defined by drawing the lengths and angles from any "regular" (e.g., uniform) distribution on any subset of the possible values. A random configuration of a chain embeds into ℝ³ by in addition drawing the dihedral angles from any regular distribution. If a class of chains has a locked configuration (and no nontrivial class is known to avoid locked configurations), then the probability that a random configuration of a random chain is producible approaches zero geometrically as n → ∞.     

A method for calculating successive approximate solutions for a class of block banded M/G/1 type Markovian models

This paper presents an efficient equilibrium solution algorithm for a class of infinite block banded M/G/1 type Markov chains. By re-blocking the states, these are a class of the so-called quasi-birth-and-death (QBD) type chains. The proposed algorithm is not based on an iterative approach, so that the exact solution can be computed in a known finite number of steps. The key point on which the algorithm is based is the identification of a linear dependence among variables. This dependence is expressed in terms of a companion matrix. The equilibrium solution of the Markov chain is obtained operating on this matrix.

An attractive feature of the algorithm is that it allows the computation of a succession of approximate solutions with growing accuracy, until the exact solution is obtained in a finite number of steps. The class of block-banded M/G/1 type Markov chains we consider requires that the lower diagonal block is invertible and that the chain is ergodic. However, many models arising from telecommunication systems satisfy this restriction. Results for a case study show that the proposed algorithm is efficient and quite accurate, even when providing approximate solutions.     

Finding story chains in newswire articles using random walks

Massive amounts of information about news events are published on the Internet every day in online newspapers, blogs, and social network messages. While search engines like Google help retrieve information using keywords, the large volumes of unstructured search results returned by search engines make it hard to track the evolution of an event. A story chain is composed of a set of news articles that reveal hidden relationships among different events. Traditional keyword-based search engines provide limited support for finding story chains. In this paper, we propose a random walk based algorithm to find story chains. When breaking news happens, many media outlets report the same event. We have two pruning mechanisms in the algorithm to automatically exclude redundant articles from the story chain and to ensure efficiency of the algorithm. We further explore how named entities and word relevance can help find relevant news articles and improve algorithm efficiency by creating a co-clustering based correlation graph. Experimental results show that our proposed algorithm can generate coherent story chains without redundancy. The efficiency of the algorithm is significantly improved on the correlation graph.     

基于三链混合遗传算法的贴片机贴装过程优化

为提高贴片机的生产效率,对贴片机贴装过程中的元器件拾取贴放顺序进行优化,提出了一种改进的三链混 合遗传算法。该算法将传统遗传算法中的两条链增加为三条链,并采用了启发式改进遗传算子。实验结果表明,改进的三链 混合遗传算法能够减少种群数目,提高优化效率和优化效果,从而提高算法的全局搜索能力。该算法在多数情况下能够搜索 到优于传统遗传算法的解。