论文部分内容阅读
本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的.
平面上简单多边形平移时确定碰撞部位的最优算法
【摘 要】
：
本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰
【机 构】
：
浙江大学CAD＆CG重点实验室,山东大学计算机科学系
【出 处】
：
计算机学报
【发表日期】
：
1992年8期
【基金项目】
：
国家自然科学基金
其他文献
本文描述一个在微型计算机上实现的集成印制电路板设计系统IPBDS.在IPBDS的研制过程中,采用了支持分层设计的并行系统结构,将各种用于设计输入、设计检验和布图设计等CAD工具集中由一个设计数据库进行统一的组织和管理,实现了电路设计的一次性输入存储,供多个CAD工具共同使用,避免了各工具间复杂和重复的数据转换,减少了存储的冗余,保证了数据的一致性和设计的完整性,为印制电路板设计提供了一个集成和有效
为加快推广实用栽培技术．深入推进玉米、大豆高产创建活动．5月22日．农业部种植业管理司在吉林省长春市正式启动了2009年全国玉米大豆高产创建活动．并举办了全国玉米生产技术培训
1999年5月，《饲料和饲料添加刺管理条例》颁布，这是我国饲料工业发展史上的新起点和里程碑．标志着我国饲料工业纳入了法制管理的轨道．图为1999年6月，农业部在京举办《饲料和饲料添
本文用比较一般化的形式,综述我们近期的工作,并把它和国际近期发表的各种测试产生系统进行了比较,以发现它的优点和不足,以及具有的水平.
本文提出了结构程序和结构程序系统的严格定义.系统地论述了它们的层次结构.并在此基础上研究了它们的复杂程度的数学描述问题,给出了一些对软件设计具有指导意义的公式.
原油转势、衰退甚至恶化的经济环境．令农产品的金融与工业属性光环褪色．重归自身商品属性本色。面对需求放缓、供应增长的基本面，美豆以往供需偏紧的格局将获得扭转．同时2009年播
目的研究常压低氧性肺动脉高压大鼠肺内p53基因的表达及探讨肺血管重建（PVR）的分子机制。方法20只雄性SD大鼠随机分为对照组、低氧组,每组10只。采用常压间断低氧8h/d,连续21d
1.SP~2N~2S~2系统简介 SP~2N~2S~2系统是一个多指令多数据流(MIMD)并行处理系统,系统结构如图1所示,由图1可知,四个DSP芯片TMS320C25彼此通过双端口存储器(DPM)互连成环形结
本文提出了一个利用集合运算生成最小生成树的算法。研究了实现集合运算的数据结构及施加在这个结构上的算法。该算法利用公式分组排序。利用路径压缩的方法进行查找，并运算。