【摘 要】
：
设P与Q为平面上两个互不相交的凸多边形,其顶点个数分别为m与n.本文给出确定P相对Q的所有可移动方向范围的一个最优算法,其时间复杂度为O(logm+logn).本文算法虽然与文献[3]算法具有相同的渐进时间复杂度,但是由于本文算法在初始化过程中不必先求出两凸多边形的一条分离直线,所以在实际运行速度上比文献[3]算法要快.
【机 构】
：
抚顺石油学院计算机科学与技术系,抚顺,113001
论文部分内容阅读
设P与Q为平面上两个互不相交的凸多边形,其顶点个数分别为m与n.本文给出确定P相对Q的所有可移动方向范围的一个最优算法,其时间复杂度为O(logm+logn).本文算法虽然与文献[3]算法具有相同的渐进时间复杂度,但是由于本文算法在初始化过程中不必先求出两凸多边形的一条分离直线,所以在实际运行速度上比文献[3]算法要快.
其他文献
本文利用球面网壳的控制方程和布置参数,得到网壳上各个节点的坐标位置,针对K系列网壳的结构特点设计了杆件与节点的连接算法,从而可以快速生成该系列的空间球面网壳模型,为网壳的设计和计算提供了一种简便快速的建模途径.同时利用ANSYS的建模语言将该模型直接输出为有限元分析系统ANSYS环境下模型.
变形技术由于在动画、工业设计等领域广泛应用,近十多年来倍受关注.本文根据多边形内在量插值的思想给出了一个新颖的二维形状插值算法.该算法以平面对象的骨架模型为基础,由源物体骨架向目标物体骨架变动来驱动两者距离场的光滑过渡.为了指导骨架的变动顺利完成,我们引入骨架特征图的概念;当源物体与目标物体拓扑结构不一致时,特征图会根据特征顶点的对应函数(由用户定义)自动扩充为具有相同结构的扩展特征图;然后我们采
在RPM激光快速成型软件中,利用面向对象的编程思想,构造了相应的数据结构.利用布尔运算对无孔实体和有孔实体进行合并处理并根据特定的判断原则得到了首尾相连的多义轮廓线,给出了一种实用高效的优化分层算法.并采用自适应插补技术来提高RPM制件的精度.
本文在分析多坐标NC加工原理的基础上,系统地研究了刀身的优化分割模型,提出了一种将刀身离散分割,并用平面三角片近似的常用刀具的分割模型.
本文描述了不需要增加额外存储空间的指针表示的平面细分的遍历算法,只使用了O(1)的辅助内存空间.本算法是对Berg等(1997年)和Bose等(2000年)提出的算法的进一步改进,利用点对边的可见性,使面集为F的平面细分的遍历算法最多进行∑f∈F4·|f|·ln|f|/2次边比较.理论分析和实际运行结果都表明,此算法比以前的遍历算法要快的多.
本文研究了一种应用自适应神经元网络控制随机IFS概率分布的方法.在随机IFS的变换中,设计一个虚拟变换,对随机IFS的概率分布进行全反馈、部份反馈和无反馈的自动调节,由此控制拼帖图形的图像效果.
本文研究构造平行截面上两个多边形之间合法三角剖分的一些基本问题,给出了合法三角剖分与准合法三角剖分的定义,从而得出:一个多边形沿截面法向平移、在截面内平移和在截面内等比例放缩都不影响三角剖分的合法性;任意两个简单多边形之间必存在一个准合法三角剖分.该结论对于彻底解决这个在可视化和几何造型领域具有重要实用价值的三维重构问题具有很大意义.
本文提出了一种自动的四边形有限元网格生成法,其实质是把被划分区域无限地分割,直到整个区域全部由四边形单元组成.文中详细阐述了边界偏移、最优分割线确定和简易环的划分等关键技术.几个网格划分实例表明该网格生成法能有效地把被划分域离散为高质量的网格.
本文讨论了构造C2连续的四次Bézier插值曲线问题.把四次样条曲线降为C2连续可提供额外的自由度,用于控制曲线的形状.自由度由极小化插值曲线和辅助曲线的一阶导数差的平方的积分确定.讨论了C2连续的四次Bézier曲线需满足的连续性方程.新方法的优点是曲线须满足的连续性方程是三对角占优势的,曲线的不连续点在给定的数据点处,具有额外的自由度调整曲线的形状.最后以具体实例对新方法和现有三、四次样条函数
图像骨架在模式识别等领域有着广泛的应用,但被骨架化的文字、指纹、工程图等图像都具有一定规律,较为简单.本文针对任意复杂带状图像,提出基于有向图的边界多边形的计算及其骨架化算法.很好地解决了图像边界表示以及复杂多边形到简单多边形的快速转化问题,并通过边界多边形的Delaunay三角化,实现了图像的骨架计算.算法具有速度快、效果好等优点.文章最后给出了一些应用实例以及与其他方法的比较结果.