河南油田QC成果摘金夺银

5月19日，从南阳市2011年质量管理成果发布会上传来消息，河南油田选送的19项成果，全部获奖。     

简单多边形的最小外接矩形算法

针对钢板在数控切割过程中存在热变形,导致加工工件变形不可用的问题,采用对工件进行矩形切割,从而使热变形达到最小的方法,给出了一种求解简单多边形的最小外接矩形算法.并在此基础上分析了其具有的复杂度O(k2)(其中k是简单多边形的顶点个数).     

基于夹角符号序列的凸多边形直径优化算法

求凸多边形直径是计算几何中的一个基本问题,本文在夹角符号序列算法的基础上,提出并实现了采用对分查找的算法,使整个算法的时间复杂度降低到O(nlogn).该算法简单,运行效率高.     

计算机辅助管材排料算法及其实现

针对多数企业在机械加工中都是采用人工排料的现状，提出了基于线性规划的计算机辅助排料算法，并建立了管材下料的数学模型，给出了求解所有合理下料方案的高效算法，以及求解该数学模型适合生产实际的快速算法，根据此算法下料能得到最优的结果，即能最大限度地提高原料利用率，有效降低企业生产成本。     

由截面构造实体的造型方法

以有理Ｂｅｚｉｅｒ曲线为依据，给出了由截面构造实体的造型方法。用该方法生成的实体截面过渡自然、光滑，截面间的对应均匀。     

简单多边形凸包的算法

给出了一种求任意简单多边形凸包的算法.算法中采用了逐次删除凹顶点排除非凸包上的点直至没有凹顶点,从而求得凸包的思想.其几何意义明显,易于编程实现.该算法的时间复杂度为顶点个数的线性次乘法、线性次减法及顶点个数与其对数乘积次比较.给出了准确的时间复杂度的上界.     

关于第一类三次Hermite样条插值的误差

4‘文对C“分){产f计。〔a,b〕空间中的_,。索川第一类三次Hermitc样条进行抽位误片作了(部f(x)已C“〔a,d〕,则}!H3(x)一f(x)}(森一n“f}f,/ 】J(H、(x)一f(x))如果f(x)eC3〔a,l)〕, }}H。(x)一f(x)冲《一 }!(H3(x)一f(x))“,,}(-打*5石丁一(O、I”一n夕O则有 8护 .九匕}}《。     

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

基于多序的空间数据索引结构——MOIS-树

以提高查询效率为目标,运用数据空间分割技术、结合B-树和R-树思想,提出了一种空间数据索引结构——MOIS-树,给出了全新的区域查询处理方法和空间对象按其MBR进行排序的4种序关系定义,并以此为基础给出了MOIS-树的定义,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行查询时可以进行快速定位,明显地加快了查询的速度.此外,在查询算法中引入查询窗口包含中间节点MBR的检测,对于较大查询窗口的查询,有效地减少了常规查询算法中大量无效的相交性判断,从另一方面加快了查询速度.给出了MOIS-树的建立算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度分析,并给出区域查询算法及算法的性能分析.实验表明,索引结构区域查询速度有很大的提高.     

连续多方向区域查询的空间向量模型算法

针对判定空间对象间方向关系模型不能给出带有方向特征的定量分析,导致查询区域只是单方向开放区域的问题,结合向量运算和MB树,提出了一种能够解决连续开放区域的方向关系查询空间向量模型算法。该算法主要包括对查询目标进行过滤和提纯两个步骤。在过滤过程中,分析了查询区域与包含空间目标的最小边界矩形(MBR)顶点之间的位置关系,给出了相应的判断方法,利用MB树中MBR的有序性对被查询节点的MBR给出了有效的剪枝规则,从而使查询时能有效减少系统I/O;在提纯过程中,处理过滤步骤中筛选出来的与查询区域有交的MBR,从中找到位于查询区域中的目标点。实验结果表明,空间向量模型算法不仅可以解决单方向开放区域问题,而且能够有效地解决连续多方向区域查询问题,它在二维和三维空间都具有适用性。