任意多边形的非结构网格快速生成算法研究

对于包含大尺度运动边界的CFD数值模拟,网格重构是其中的关键,快速稳定的网格生成技术是其中的重要组成部分。建立了基于有向边的适用于任意多边形的快速三角初始化算法;证明了最长边剖分网格细化算法在一定条件下发散,并结合Delaunay边交换技术使细化算法封闭;建立了基于顶点弹簧理论的网格优化方法,以提高网格生成的质量。结果表明,算法具有较好的鲁棒性和高效性。     

二维约束点集Delaunay三角剖分算法研究

在已有算法基础上,提出了任意二维约束点集Delaunay三角剖分的新算法,算法仅在局部产生少量新点,并在局部对三角剖分进行修改,便可保证整体三角剖分符合Delaunay性质.     

基因遗传算法在三维数据场造型中的应用

将基因遗传算法应用于三维数据场的造型研究之中,提出了遗传三角剖分算法.针对三维三角剖分的特殊性,提出了虚拟交叉算子和三角变异算子,能够确保在遗传进化过程中,解群中的每一个串始终代表一个合法的三角剖分.     

最优Hamilton圈的一种新算法

提出了一种行之有效的执行算法——换顶算法，对无向图权值矩阵的数据进行有效处理，通过交换顶点来寻找一条较优Hamilton圈。在整个过程中，权值矩阵的上三角数据为有效数据，只需要按一定的顶点交换规则对这部分数据进行调整就可以达到优化Hamilton圈的目的。提出了交换规则的思想，且通过选择适当的规则，先判定可行性再执行交换算法，节省了大量的运算时间，降低了算法的时间复杂性。该算法也适用于Hamilton链的情况。     

复杂平面区域的三角网格生成算法

为生成复杂平面区域的有限元网格,提出了基于网格细化的三角网格生成算法.该算法首先采用耳尖移除法对区域边界做三角划分,得到粗略的初始网格.提出Delaunay优化平分方法,根据网格密度细化初始网格,该网格细化方法结合最长边平分技术与Delaunay边交换技术,可有效提高内点生成与单元细分的质量.实验表明,基于Delaunay 优化平分的三角网格生成算法可对任意平面域进行网格剖分,生成符合有限元计算要求的高质量三角网格.     

地形生成算法

提出了通过读取单色BMP格式的等高线图产生三维地形的方法和使用OpenFlight API和分形算法生成三维地形的方法.第一种方法对应每一个高程生成一个或多个多边形,再把代表不同高度的多边形放置到对应的高度上,并从最低端的多边形开始,逐层向上一层多边形采用沿各顶点法线放样的方法生成地形三角形,这种方法适用于生成锥形山、丘陵等小面积地区的地形模型;第二种方法使用分形算法生成三维地形,这种算法生成地形速度快、逼真度高,适用于生成大面积的三维地形.     

基于多边形布尔运算的卫星区域覆盖分析算法

传统网格点法计算卫星区域覆盖性能的精度受网格大小影响且效率低,为此提出了一种基于多边形布尔运算的新算法。算法在计算卫星覆盖带与待分析区域相交多边形的基础上,基于多边形交、差运算,将覆盖多边形分解为具有单一覆盖属性的组成部分;将分解结果三角化后利用球面三角形面积公式计算面积;最后统计面积以计算覆盖率,并设计实现了分类统计方式和可视化表现方法。与传统网格点法相比,该算法覆盖率计算结果稳定,不受类似网格大小之类因素影响,在接近精度情况下效率比网格点法提高约20倍。     

任意三角域上的光滑插值法

本文讨论了三角域和多边形域上的光滑函数在边界的法向导数和沿边界的方向导数的关系,得到了三角域和多边形域上C~1(C~2)插值的简化判别条件。提出了三角域上的一种C~2插值方法。最后,我们给出了误差估计和计算实例。     

基于平均度的树分解启发式算法

很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。     

囿于控制多边形的NURBS拐点分析与控制

从变形的观点出发,首先研究了一般平面参数曲线变形过程中产生拐点的充分必要条件以及判定拐点的一个泛函方程。在此基础上,给出了研究非凸控制多边形NURBS曲线拐点的方法,特别研究了正则单拐、双拐多边形NURBS曲线拐点的分布问题,得到了分析与控制相应曲线拐点的条件和判据。本文的结果可应用于调节与控制曲线形状的算法设计,也可指导CAD造型工程师的交互设计。     

Concave minimization over a convex polyhedron

A general algorithm is developed for minimizing a well defined concave function over a convex polyhedron. The algorithm is basically a branch and bound technique which utilizes a special cutting plane procedure to' identify the global minimum extreme point of the convex polyhedron. The indicated cutting plane method is based on Glover's general theory for constructing legitimate cuts to identify certain points in a given convex polyhedron. It is shown that the crux of the algorithm is the development of a linear undrestimator for the constrained concave objective function. Applications of the algorithm to the fixed-charge problem, the separable concave programming problem, the quadratic problem, and the 0-1 mixed integer problem are discussed. Computer results for the fixed-charge problem are also presented.     

利用几何结构求解欧氏平面TSP的改进遗传算法

TSP是经典的组合优化问题。根据欧氏平面TSP最优环路的性质提出了子路径及相关的概念,利用点集凸壳设计了环路构造算法,并以点集Delaunay三角剖分图为启发信息设计了改进的遗传算法,通过中国144城市TSP等验证了算法的有效性。     

复杂空、海域的一种简洁管理算法

根据复变函数理论 ,首次提出了一种可对任何复杂空 /海域进行管理的简洁算法 ,解决了以往系统中不能解决或很难解决的复连通区域和凹多边形区域的管理问题     

多整转副平面连杆机构屏幕模拟的连续性算法

提出一种多整转副平面连杆机构在屏幕上连续运动的简便算法,这种算法的分析策略是把整个机构逐步分解为单构件和二杆组这样一些基本单元,通过对这些基本单元的求解得到整个机构在任意瞬时的位置,具体方法是建立相对坐标系,通过坐标变换求出结果,与通常采用的解矢量方程或极坐标方程的方法相比,新算法既不受杌构复杂程度的限制,又可避免求解结果的多值性和由此引起的繁杂的象限判断过程,从而可提高运算效率和模拟效果。     

Optimal location of a single service center of certain types

Hakimi has considered the problem of finding an optimal location for a single service center, such as a hospital or a police station. He used a graph theoretic model to represent the region being serviced. The communities are represented by the nodes while the road network is represented by the ares of the graph. In his work, the objective is one of minimizing the maximum of the shortest distances between the vertices and the service center. In the present work, the region being serviced is represented by a convex polygon and communities are spread over the entire region. The objective is to minimize the maximum of Euclidian distances between the service center and any point in the polygon. Two methods of solution presented are (i) a geometric method, and (ii) a quadratic programming formulation. Of these, the geometric method is simpler and more efficient. It is seen that for a class of problems, the geometric method is well suited and very efficient while the graph theoretic method, in general, will give only approximate solutions in spite of the increased efforts involved. But, for a different class of problems, the graph theoretic approach will be more appropriate while the geometric method will provide only approximate solutions though with ease. Finally, some feasible applications of importance are outlined and a few meaningful extensions are indicated.     

全局仿射变换条件下图像不变量提取新方法

从仿射几何理论出发,提出了一种全局仿射变换条件下图像特征不变量构造的新方法.利用仿射区域划分获取一组扩展质心集合作为图像特征点集;求解特征点集的凸包,根据扩展质心的性质将凸包顶点均匀组合成若干特征区域;利用仿射几何性质构造了有效的仿射不变量.实验对该方法进行了全面的比较分析,以验证所构造的不变量更具稳定性和高时效性.     

Variations on a cutting plane method for solving concave minimization problems with linear constraints

A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates the question of finiteness of Tui's method to the so-called generalized lattice point problem of mathematical programming and gives a sufficient condition for terminating Tui's method. The paper then presents several branch-and-bound algorithms for solving concave minimization problems with linear constraints with the Tui cut as the basis for the algorithm. Finally, some computational experience is reported for the fixed-charge transportation problem.     

多视图三角化中特征点噪声尺度的自适应估算

鲁棒性多视图三角化方法通常借助重投影误差经验阈值来剔除图像对应中的错误匹配,该经验阈值的选取直接影响三维重构场景点的数量和精度。在分析图像特征点定位噪声及对极传递几何原理的基础上,建立对极传递过程不确定性的传递模型,提出一种基于核密度估计的最优噪声尺度估算方法,并将该噪声尺度作为多视图三角化中错误匹配筛选的依据。实验结果表明,该方法可以获得准确的噪声尺度估计,从而有效提升多视图三角化方法的三维重构质量。     

Concave envelopes of monomial functions over rectangles

The construction of convex and concave envelopes of real‐valued functions has been of interest in mathematical programming for over 3 decades. Much of this interest stems from the fact that convex and concave envelopes can play important roles in algorithms for solving various discrete and continuous global optimization problems. In this article, we use a simplicial subdivision tool to present and validate the formula for the concave envelope of a monomial function over a rectangle. Potential algorithmic applications of this formula are briefly indicated. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004