【摘 要】
：
讨论在CAD/CAM、计算机图形学、机器人运动控制等领域都有着相当意义的图形的可移动性问题。我们研究下述典型问题,即:在平面内若多边形P沿曲线σ作定姿态刚体移动,P与障碍多边形Q相碰撞吗?在连通曲线σ关于交点判定正则,P与Q为简单多边形的情况下,本文给出-O(mn)时间的算法来判定上述典型问题中P与Q是否相碰撞。这里m与n分别为P与Q的顶点数。并且所给算法在最坏情形下是最优的。
【机 构】
：
中国科学院计算技术研究所CAD开放实验室!北京100080华中理工大学数学系武汉430074,武汉大学计算机系!武汉430070
论文部分内容阅读
讨论在CAD/CAM、计算机图形学、机器人运动控制等领域都有着相当意义的图形的可移动性问题。我们研究下述典型问题,即:在平面内若多边形P沿曲线σ作定姿态刚体移动,P与障碍多边形Q相碰撞吗?在连通曲线σ关于交点判定正则,P与Q为简单多边形的情况下,本文给出-O(mn)时间的算法来判定上述典型问题中P与Q是否相碰撞。这里m与n分别为P与Q的顶点数。并且所给算法在最坏情形下是最优的。
其他文献
<正> 韦君宜曾说:“注意到一个现象吗?女作家笔下的女人,尽管呆板的,庸俗的,鄙陋的……也都有,但是都很少那样完全离不开男子,从思想、人格到肉体都依附于男子的人物。有的话,那一般都不是被讴歌、赞美的对象。(这在男作家笔下是常出现的),而是被贬抑的对象。作家对于这样的同类,所能够赋予的,每每顶多是哀怜。”男作家笔下所赞美的,讴歌的形象,在女作家笔下却成了被贬抑或哀怜的对象,可见女作家除了一般意义上的创作情绪外,还有区别于男作家的特殊的情绪在创作过程中起作用。
协同多个网络访问服务器(NAS)的用户验证、授权及记帐服务是一个复杂的问题。文章在分析多NAS用户验证管理方法的基础上,给出了各种情况的实现方案,并通过详细的讨论提出自己
生态环境危机已成为21世纪不可回避的重要课题。马克思、恩格斯的唯物史观揭示了生态危机产生的真正原因，为社会主义制度下解决生态危机提供了科学的理论根据。社会主义初级阶
《计算机应用基础》课程已经成为中等职业学校的一门公共基础课程。为使学校能够紧跟时代的步伐,适应现代教育技术的发展,培养现代化的优秀人才,学校必须改革教学方法,提高教
针对场景分割中基于像素分类计算较为复杂,使用特征类别较少难以提高分类精度的缺点,提出一种新的基于超像素多种视觉特征来学习场景几何结构类别的模型.首先,在图像超像素基
司法鉴定是诉讼活动的基本要素,构成了案件的核心内容,体现了法院审判的客观公正,是社会正义伸张实现的根本途径。但是,司法鉴定工作,由于旧有的管理体制,不断发生负面问题,
让学生学会正确运用语言文字,为听、说、读、写打下良好基础是小学语文的教学目的,而阅读教学是小学语文教学的核心,是听、说、读、写教学中一个重要环节,是培养学生综合性语
利用５００ｈＰａ高度场资料和中国１６０个站的月降水资料，根据夏季各种降水型的特征，寻找环流型与降水型的同期及前期关系，确定降水分型的物理意义和前期环流型对降水预报的指示意义，对中国夏季降
文章从现在各大商家争先打折的现象入手，分析了商家进行打折促销的目的，阐述了商家打折促销的方法与手段，最后总结出了打折促销后的真正利益归属。
常住户口登记管理制度是我国人口管理的基本制度,它涉及到经济、社会、文化、人口等等众多方面,是一项关系到民生的、重要的社会法律制度。早在上古时代,我国就已开始探索构