确定简单多边形旋转时碰撞部位的扫描算法

给定平面内任意两个互不相交的简单多边形Ｐ是Ｑ。若Ｐ在平面内绕０点旋转时与ＡＱ碰撞,讨论其碰撞部位的判定问题,通过分析多边形关于０点的单调边,在平面扫描算法的榧耻提出了曲线扫描法,给这一总理２的Ｏ（（ｍ＋ｎ）ｌｏｇ（ｍ＋ｎ））算法,与现有的算法相比,降低了时间复杂性,这一方法在计算几何和计算机图形学等领域具有一定的理论和实吓价值。     

一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

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

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

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

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

基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

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

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

最长公共子充列问题的改进快速算法

现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ）,Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度,Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ））,空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比,不管在Ｐ〈〈ｍ的情况下,还是在Ｐ接近Ｍ时,这种算法都有更快的速度。     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

Voronoi图算法及其在混合电路的衬底耦合研究中？…

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行２,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图。在 计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题。算法时间复杂度为Ｏ（ｎｌｏｇｎ）空间复杂度为Ｏ（ｎ）。     

二维模式近似匹配的快速算法

给定一个大小为ｎ×ｎ的文本Ｔ和一个大小为ｍ×ｍ的模板Ｐ，如果文本Ｔ中存在一个ｍ×ｍ的子块与模板Ｐ能够逐点匹配，称为精确匹配。如果最多有ｋ个元素不同，称为带有最多ｋ个误差的近似匹配。对于精确匹配，本文给出了一个时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜）的算法，∑＝｛ａ１，２，…，ａ｜∑｜｝，是模板的字符集。对于近似匹配，快速算法分为两步：（１）预选。利用精确匹配算法找出能精确匹配的ｓ×ｓ（０≤ｓ≤ｍ）子块，得到ｈ个候选的对准点；（２）验证。把模板对准候选点，逐点比较，以确定不相同的元素是否不超过ｋ个。近似匹配的时间复杂性为Ｏ（ｎ２ｌｏｇ｜∑｜＋ｈｍ２）。     

论两条直线段的求交

本文给出一种用计算机求两和直线段交点的算法，较之常用算法，本算法针对计算机的计算误差和几何元素在计算机内的表示误差，构造交点模糊判断树，使求两条直线段交点的正确性和可靠性有较大改进，并用于几何造型系统ＧＥＭＳ４．０，取得了较好的效果。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

Efficient algorithms for common transversals

Suppose we are given a set S of n (possibly intersecting) simple objects in the plane such that, for every pair of objects in S, the intersection of the boundaries of these two objects has O(1) connected components. We consider the problem of determining whether there exists a straight line that goes through every object in S. We give an O(n log n γ (n)) time algorithm for this problem, where γ(n) is a very slowly growing function of n. In many cases, our algorithm runs in O(n log n) time. Previously, only special cases of this problem were considered: the case when every object is a straight-line segment (Edelsbrunner et al., 1982), the case when the objects are equal-radius circles (Bajaj and Li, 1983), and the case when objects all maintain the same orientation (Edelsbrunner, 1985). All these cases follow from our general approach, which places no constraints on the size and/or configuration of the objects in S.     

TUM.GeoFrame: automated high-order hexahedral mesh generation for shell-like structures

This paper presents a fully automated high-order hexahedral mesh generation algorithm for shell-like structures based on enhanced sweeping methods. Traditional sweeping techniques create all-hexahedral element meshes for solid structures by projecting an initial single surface mesh along a specified trajectory to a specified target surface. The work reported here enhances the traditional method for thin solids by creating conforming high-order all-hexahedral finite element meshes on an enhanced surface model with surfaces intersecting in parallel, perpendicular and skew-angled directions. The new algorithm is based on cheap projection rules separating the original surface model into a set of disjoint single surfaces and a so-called interface skeleton. The core of this process is reshaping the boundary representations of the initial surfaces, generating new sweeping templates along the intersection curves and joining the single swept hex meshes in an independently generated interface mesh.     

Fast dynamic intersection searching in a set of isothetic line segments

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log² n) space requirements and O(log³ n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(logN + t) query time, O(n log² N) space and O(log² N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique.     

基于空间扫描策略的3维相交检测算法

针对复杂虚拟场景中碰撞检测和空间分析等操作实时性差的问题,提出一种适用于3维空间对象间的快速相交检测算法——Space Sweep。该算法首先根据场景内空间对象分布特征,构建事件点及其列表;利用空间扫描策略,自适应地构建一系列假想的空间扫描面;在扫描面移动的过程中,将空间对象的状态分为死亡态、激活态和休眠态,通过只对当前处于激活态的空间对象进行相交测试,有效地减少了空间对象间不必要的相交计算。该算法提高了虚拟场景中3维空间对象间相交检测的效率,为3D GIS中实时空间分析提供了有力的技术支持。最后,通过对比测试验证了本文算法的实用性。     

关联交叉口子区的信号优化控制方法

在交叉口群的信号优化控制过程中,针对遗传算法早熟收敛且对相邻交叉口关联性考虑较少的问题,提出一种关联交叉口子区的信号优化控制方法。利用软集合理论将关联性强的交叉口划分在同一个子区;采用基于共享函数的小生境技术调整群体中个体的适应度并自适应地调整算法的交叉概率[Pc]和变异概率[Pm]对遗传算法进行改进;使用改进的遗传算法对关联交叉口子区的平均延误时间[D]进行优化。路网实测数据的仿真实验表明本文方法对交叉口群进行了合理的子区划分,且改进的遗传算法在子区信号优化控制中迭代次数减少,使得交叉口的平均延误时间更短。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段．在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度,使其在O（logN）～O（N）之间自适应地变化,且大部分情况下时间复杂度小于O（N）．     

一种基于拓扑搜索的三角网求交算法

在地质构模以及各种地下工程设计等三维表达、分析领域,大规模的复杂三角形网的求交计算是三维表面模型建模的一个关键算法。根据三角形网中相邻三角形之间的拓扑邻接关系以及交线的连续性,提出了一种基于拓扑搜索的三角网求交算法。该算法引入空间辅助网格对原始三角网中的三角形进行筛选,并在候选三角形集合中依次追踪、计算构成交线的交线线段,在获得每个交线线段的同时完成了线段之间的连接。实验表明,该算法不仅效率高而且可靠性好。