A method for detecting structure in polyhedra

A construction is given for associating a finite state automaton with a 3-dimensional polyhedron. It has the property that if a polyhedral segment is encoded as a string and used as input to the automaton, the automaton state which is reached contains information about all congruences of the segment with parts of the polyhedral surface. An application is retrieval from a polyhedral database, given as key a partial 3D view.     

Characterizing and recognizing the visibility graph of a funnel-shaped polygon

A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph.We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM.We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures.This work was supported in part by the Korea Science and Engineering Foundation under Grant 91-01-01.     

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON

ＡＮＥＷＣＯＮＶＥＸＨＵＬＬＡＬＧＯＲＩＴＨＭＦＯＲＡＮＹＰＯＬＹＧＯＮＨｕＺｈａｎｑｉＬｉＹｕｐｅｎｇＷａｎｇＪｕｎＱｉａｏＬｅｉＡｂｓｔｒａｃｔＡｎｅｗａｌｇｏｒｉｔｈｍｆｏｒｆｉｎｄｉｎｇｃｏｎｖｅｘｈｕｌｏｆａｐｏｌｙｇｏｎｉｓｐｒｏｐｏｓｅ...     

虚拟数控车削加工碰撞和干涉检验技术

通过对虚拟数控车削加工中碰撞和干涉检验技术的研究,提出了基于多边形重叠检验的碰撞检验算法及干涉检验算法.为验证其有效性,在Visual C+ +6.0平台上结合OpenGL图形库开发了测试平台对算法进行了实例分析,结果表明该算法可以有效地对碰撞和干涉现象进行检验,且效率较高,直观性较好.     

三指手抓取力封闭性的简单判别算法

根据力封闭抓取的定义建立了利用严格内力的存在条件进行三指灵巧手力封闭抓取判别的研究方法,构建了三指灵巧手力封闭抓取的等价判别算法。在手指指端与物体构成有摩擦的固定点接触模型的前提下,三指灵巧手力封闭抓取条件等价于抓取矩阵满秩并存在严格内力。首先,基于对物体表面接触位置的几何特性分析,建立了摩擦扇存在条件,每个指端接触点的内法矢与接触平面所成夹角小于接触点摩擦圆锥角;其次,通过研究接触点摩擦扇边界线及其交点的相互位置关系,推导了内力汇交多边形的存在条件,任意两个摩擦扇的边界线交点中,至少有一个位于第3个摩擦扇的严格内部,或者至少有3个边界线交点位于第3个摩擦扇边界线上;最后,在考虑内力平衡关系的基础上,建立了基于矢量计算的三指灵巧手力封闭抓取的快速判别算法。     

多棱镜扫描分光多头激光毛化圆形毛化点分析

为了得到圆形的毛化点以改善传统单头激光毛化技术椭圆毛化点对轧制钢板的均匀性和力学性能的影响,提出了一种采用多棱镜扫描分光技术的多头激光毛化设备.在一定离焦量下,使得扫描过程中扫描光束所带来聚焦点非均匀移动可以与轧辊同步运行,理论上可以获得椭圆度(长短轴比)最小为1.0010957的近似圆形毛化点,并进行了生产实践.结果表明,理论分析计算与实际结果较为符合.通过对离焦量、扫描速度等毛化参量的控制,可以获得椭圆度根据特殊要求任意调整的毛化点,这为多头激光毛化技术的应用提供了指导.     

面向区域目标的遥感卫星任务规划算法

面向区域目标的遥感任务规划问题主要解决如何在多遥感卫星条件下,对区域目标进行合理的任务分解和分配。提出了一种动态划分方法,通过加入卫星观测范围因素,改进了现有的静态划分方法。该方法划分生成的候选条带数量大大增加,使算法求解难度增大。基于邻域搜索思想,综合贪婪规则、随机模式和变邻域等因素提出了快速求解区域目标任务规划问题的贪婪随机变邻域搜索算法。最后通过实例进行了验证,结果证明应用该算法能较快得到比较好的解。     

数字城市中建筑物模型与地形的拼接算法研究

约束边的嵌入是实现数字城市建筑物和地形拼接的算法基础,总结了约束边嵌入算法的特点和优缺点,提出改进的多边形嵌入算法,即一次性将多边形嵌入三角网中,在进行基础重构的基础上,进行优化处理.该算法能够适应多种情况,易于理解和实现,能够很好地符合工程要求.