基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

关于求平面点集凸包的一个O(n)时间算法的商榷

王志强等于1998年提出了一个计算平面点集凸包的新算法，并且声称该算法的最坏时间复杂度为O(n)，从而为张性时间排序提供了可能性，该文对王志强等提出的求平面点集凸包算法的时间分析提出了不同观点，进一步明确了平面集凸包算法和排序算法的时间下界为Ω(nlogn).     

一个通用的快速三角化算法

提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法。当算法应用于多边形区域时,首先对各个顶点和区域内部的散乱点按扫描方式排序,然后依次扫描各点,扩展生成新的三角形,从而获得局部已剖分区域,并最终完成整个区域的三角化。将上述过程作适当改动后,可被用于平面散乱点集的三角网格化,该通用算法除了具有快速三角化的特点之外,还采用局部域的优化组合来体现最优化准则,因此算法更具有可操作性和实用性。     

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

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

任意多边形窗口的矢量圆裁剪算法

已有的矢量圆裁剪算法存在效率低和内存占用率高等问题,将会影响到图形处理和分析的速度,为此提出一种具有线性复杂度的任意多边形窗口的矢量圆裁剪算法.首先采用投影法对矢量圆线性映射,构造一个线性的射线函数,快速而准确地对圆与多边形进行相交性检测,同时通过线截断法,运用线性方程精确地求出圆与多边形的实交点;然后根据三点之间的叉积按照规定的方向对交点进行排序;最后采用中点检测法确定可见性的圆弧或圆绘制到内存,并输出绘制好的图像和统计的图形复杂度.实验结果表明,该算法可有效地避免虚交点的产生,降低裁剪显示过程中的时间和空间复杂度,提高矢量圆裁剪准确性.     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边，其内部在边的同一侧。本文依据凸多边形的这一特性，提出求解简单多边形凸包的新算法，进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点，得到极值点间的候选点子集，再求得相邻极值点间的有序凸包点列，最后顺序连接极值点间的有序凸包点列，得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h），其中，n为平面点集的点数，h为平面点集凸包的顶点数。相比相同复杂度的凸包算法，新算法简单、易于实现。又由于是顺序求得凸包上的点，新算法还具有更易于实现基于其上的有效空间算法的优点。     

钣金冲孔中直角多边形快速干涉检验算法

针对钣金冲孔中的直角多边形孔的刀具匹配中涉检验提出了一种高效的算法.该算法先对直角多边形的顶点按逆时针方向排序,然后建立起基于空间分区思想的四向辅助图,利用四向辅助图中的规律判断待加工边的可能干涉情况,从而确定刀具的允许最大宽度.算法分析表明:该算法对直角多边形刀具涉检验具有线性的时间复杂度,有效地提高了板材加工中直角多边形孔自动刀具匹配的效率.     

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

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

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

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

STIGMERGY-BASED SYNCHRONIZATION OF A SEQUENCE OF TASKS IN A NETWORK OF ASYNCHRONOUS NODES

Social insects are able to build complex architectural structures in spite of their limited capabilities and simple behaviors. The coordination of various activities within a colony of such insects is performed stigmergically through indirect communication. This article describes a stigmergy-based technique by which a set of mobile agents trigger the execution of a sequence of tasks at every node in a network, in a near synchronous manner. These agents use a concept of an innate task-specific potential, which guides them to initiate the execution of a task at various asynchronously operating nodes of a network, in a synchronous manner. This innate potential maintained within the agent also assists in self-healing. The technique is oblivious to both the number of agents and nodes in the network and, hence, is scalable. The proposed technique was emulated on various real static and dynamic topologies by varying different parameters. The results obtained validate the efficacy of the concept of potential. An implementation using real robots has also been presented to portray the practical viability of the proposed technique.     

一类Neuman型故障源的特性的研究

针对故障源作用下的系统可靠性的评估问题,建立了一种具有实输入数组的新的 Neuman型故障源(实故障源)的模型,并应用概率分析的方法评估了在这种故障源作用下由 函数元构成的系统的可靠性,给出了系统可靠性的下界估计,阐明了在实故障源作用下的基 底上不可能建立任意可靠的系统.最后研究了满足实故障源条件的函数元基在所有函数元基 中所占的比例,并给出了它的渐近估计.     

确定平面点集凸包的一类最优算法

确定平面点集的凸包问题在计算机图形学、图象处理、ＶＬＳＩ设计与ＣＡＤ／ＣＡＭ等众多领域中有广泛的应用，多年来人们一直在寻找此问题的决策算法。     

MIs系统的程序生成方法*

随着计算机技术的迅猛发展，MIs系统被广泛地应用于各行各业．本文提出一种程序生成技术，旨在提高MIs系统的开发效率和开发质量．本方法是基于构件库设计思想，首先设计出各种构件类脚本描述，用此可自动生成各种程序模块．用这种方法和技术，已成功开发出多个MIS系统，通常只需在2个月内就可完成大型信息系统的设计和生成工作．     

垂直壁面行走机器人系统研制

本文对能在高层全封闭玻璃结构外墙上行走的垂直壁面行走机器人系统的总体组成，基本功能，实施方案和技术指标等作一介绍，并对系统中的关键技术进行了分析。     

一类非线性系统的能控性条件

本文讨论非线性系统?=Ax Bu g(x,u)的完全能控性条件,并举例说明。     

CONTROLLABILITY OF A CLASS OF SINGULAR SYSTEMS

In this paper, several different concepts of controllability are investigated for a class of linear singular systems which system parameters are piecewise constant. Necessary and sufficient geometric criteria for C‐controllability and R‐controllability of such systems are established, respectively. These conditions can be easily transformed into algebraic form. By applying the principle of duality, C‐observability is discussed as well. Furthermore, the intrinsic relationship between these results and existing results are also discussed. Then, a novel necessary, and sufficient criterion for C‐controllability of linear time‐invariant singular systems is derived as a byproduct.     

一类非线性系统的可逆性

本文讨论定义在实解析流形上的如下形状的非线性系统的可逆性 本文主要结果是分别得到了如上系统具有可逆性的必要条件和充分条件。充分条件的证明是构造性的,因而可用来具体构造由系统的输出信息重现输入信息的逆系统。     

从笔画的表示到区域的表示

把空心汉字的笔画表示模型化，并用此模型来表示一般的有界连通区域。文中还指出有界连通区域用笔画表示的实用价值，同时给出从笔画表示中提取规范表示的算法。