New non-interference approach for convex polygons

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (1): 11-13.

• 博士论坛 • Previous Articles Next Articles

New non-interference approach for convex polygons

LI Zi-qiang^1,2,4,TENG Hong-fei^1,3

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

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-01 Published:2008-01-01
Contact: LI Zi-qiang

一种新的凸多边形不干涉算法

黎自强^1,2,4,滕弘飞^1,3

1.大连理工大学计算机科学与工程系，辽宁大连 116024
2.湘潭大学信息工程学院，湖南湘潭 411105
3.大连理工大学机械工程学院，辽宁大连 116024
4.精密与特种加工教育部重点实验室，辽宁大连 116024

通讯作者: 黎自强

Abstract

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）.

Key words: polygon, non-interference detection, no fit polygon

摘要： 求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念，通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形，进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷，其计算复杂度为O（n+m）。

关键词: 凸多边形, 不干涉检测, 不适合多边形

LI Zi-qiang^1,2,4,TENG Hong-fei^1,3. New non-interference approach for convex polygons[J]. Computer Engineering and Applications, 2008, 44(1): 11-13.

黎自强^1,2,4,滕弘飞^1,3. 一种新的凸多边形不干涉算法[J]. 计算机工程与应用, 2008, 44(1): 11-13.

[1]	ZHAO Fujuan, LI Ling, XIN Huamei . Research on segmentation algorithm of overlapping protein spots in two-dimensional gel electrophoresis images [J]. Computer Engineering and Applications, 2017, 53(5): 212-215.
[2]	ZHANG Hanping1, ZHANG Changsheng1, ZHOU Xiaolong2. Research on improved polygon inclusion judgments for Sn-Sb-Cu metallographic recognition [J]. Computer Engineering and Applications, 2017, 53(3): 253-257.
[3]	YANG Weibo1，2, WANG Wanliang1, ZHANG Jingling3, ZHAO Yanwei3. Packing optimization of rectangles based on improved genetic annealing algorithm [J]. Computer Engineering and Applications, 2016, 52(7): 259-263.
[4]	LIAO Zhifang, GAO Xingrui, CAI Fei, MA Xiaohui. Improved approximate algorithm of polygon [J]. Computer Engineering and Applications, 2016, 52(14): 167-171.
[5]	ZHANG Jian, ZHAO Lijun. Research on visualization by improved right regular polygon of even sides [J]. Computer Engineering and Applications, 2016, 52(14): 261-265.
[6]	LI Guangqiang, YIN Jian, ZHI Lu. Clustering based on buffer of polygon [J]. Computer Engineering and Applications, 2016, 52(12): 75-79.
[7]	XU Ming, CAO Han, TANG Duoyu. Generation and application of weighted Voronoi diagrams for polygons based on Hadoop [J]. Computer Engineering and Applications, 2015, 51(13): 59-62.
[8]	ZHU Qingwei, LI Yunfei. Research on 3D display of fast triangular polygon [J]. Computer Engineering and Applications, 2014, 50(5): 147-150.
[9]	XU Xu1，2, LIU Wei1. Research on vector-raster mixed algorithm of linear buffer generation [J]. Computer Engineering and Applications, 2014, 50(4): 152-156.
[10]	ZHOU Qing1, JI Feng2, BAI Ruilin1. Real-time location and matching method for workpiece based on circular geometric primitives [J]. Computer Engineering and Applications, 2014, 50(15): 125-128.
[11]	FAN Yuanyuan1, YANG Bin2. Triangulation mesh of implicit surfaces with curvature constraint [J]. Computer Engineering and Applications, 2013, 49(3): 182-185.
[12]	YANG Weibo1，2, WANG Wanliang2. Improved algorithm for No-Fit Polygon calculation [J]. Computer Engineering and Applications, 2013, 49(1): 32-35.
[13]	QIU Yonghong1，2, ZENG Yongnian2, QIN Jianxin1, ZOU Bin2. Improved algorithm for searching GIS topological polygonal chains [J]. Computer Engineering and Applications, 2012, 48(34): 23-27.
[14]	ZHENG Long, AO Yonghong, LIANG Yingying, SUN Yang. RPES: new approach of multi-dimensional information visualization [J]. Computer Engineering and Applications, 2012, 48(21): 107-111.
[15]	LIN Hui1，2，3, LIU Pei1, DU Peijun1, XIA Junshi1. Research on multi-scale segmentation algorithm of high-resolution remote sensing imagery based on improved statistical region merging [J]. Computer Engineering and Applications, 2012, 48(18): 159-163.

New non-interference approach for convex polygons

一种新的凸多边形不干涉算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics