| 一种新的凸多边形不干涉算法 |
| |
| 引用本文： | 黎自强,滕弘飞. 一种新的凸多边形不干涉算法[J]. 计算机工程与应用, 2008, 44(1): 11-13. DOI: 10.3778/j.issn.1002-8331.2008.01.004 |
| |
| 作者姓名： | 黎自强 滕弘飞 |
| |
| 作者单位： | 1.大连理工大学 计算机科学与工程系，辽宁 大连 116024 2.湘潭大学 信息工程学院，湖南 湘潭 411105 3.大连理工大学 机械工程学院，辽宁 大连 116024 4.精密与特种加工教育部重点实验室，辽宁 大连 116024 |
| |
| 基金项目： | 国家自然科学基金 , 湖南省教育厅科研项目 |
| |
| 摘 要： | 求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念，通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形，进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷，其计算复杂度为O（n+m）。
|
| 关 键 词： | 凸多边形 不干涉检测 不适合多边形 |
| 文章编号： | 1002-8331（2008）01-0011-03 |
| 收稿时间： | 2007-09-01 |
| 修稿时间： | 2007-09-01 |
New non-interference approach for convex polygons |
| |
| LI Zi-qiang,TENG Hong-fei. New non-interference approach for convex polygons[J]. Computer Engineering and Applications, 2008, 44(1): 11-13. DOI: 10.3778/j.issn.1002-8331.2008.01.004 |
| |
| Authors: | LI Zi-qiang TENG Hong-fei |
| |
| Affiliation: | 1.Department of Computer Science and Engineering，Dalian University of Technology，Dalian，Liaoning 116024，China 2.School of Information & Engineering of Xiangtan University，Xiangtan，Hunan 411105，China 3.School of Mechanical Engineering of Dalian University of Technology，Dalian，Liaoning 116024，China 4.Key Laboratory for Precision & Non-traditional Machining of Ministry of Education，Dalian，Liaoning 116024，China |
| |
| Abstract: | When solving problems of interference such as packing,robot motion planning,virtual assembly and so on,non- interference algorithm for convex polygons is often used.According to concept of no-fit polygon,this paper computes of no-fit polygon for two convex polygons by controlling motion direction and displacement quantity.Further a new non-interference approach for two convex polygons is presented.Finally,this paper gives out an example to account for its application in complex layout solution.Approach in this paper overcomes shortcomings of algorithm of slope chart,its computation complexity is O(n m). |
| |
| Keywords: | polygon non-interference detection no fit polygon |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
