文章基本信息

标题：Overlapping Area Computation between Irregular Polygons for Its Evolutionary Layout Based on Convex Decomposition
本地全文：下载
作者：Li, Zi-qiang ; He, Yan ; Tian, Zhuo-jun 等
期刊名称：Journal of Software
印刷版ISSN：1796-217X
出版年度：2012
卷号：7
期号：2
页码：485-492
DOI：10.4304/jsw.7.2.485-492
语种：English
出版社：Academy Publisher
摘要：Low efficiency of interference calculation has become the bottleneck that restricts further development of the performance of evolutionary algorithm for the polygon layout. To solve the problem, in this paper, we propose an algorithm of calculating overlapping area between two irregular polygons. For this algorithm, at first, two irregular polygons are respectively decomposed into the minimum number of convex polygons; afterwards, each pair of the overlapping convex polygons from two resulting partitions is clipped and their overlapping area is calculated. Because through a fast non-overlapping test to all pairs of convex polygons to be clipped, invalid computation is decreased; by making use of simple internal vertex judgment and shear-transformation based on intersecting test and intersection calculation between a line segment and any convex broken line segment, its speed of clipping overlapping convex polygons is improved. The time complexity analysis and numerical experiments indicate that the performance of our presented algorithm superiors to the existing algorithms.
关键词：Overlapping area calculation;Irregular polygon;Convex polygon Clipping;Evolutionary layout