Volume 7 Number 2 (Feb. 2012)
Home > Archive > 2012 > Volume 7 Number 2 (Feb. 2012) >
JSW 2012 Vol.7(2): 485-492 ISSN: 1796-217X
doi: 10.4304/jsw.7.2.485-492

Overlapping Area Computation between Irregular Polygons for Its Evolutionary Layout Based on Convex Decomposition

Zi-qiang Li1, Yan He1, and Zhuo-jun Tian2
1School of Information & Engineering of Xiangtan University Xiangtan, Hunan 411105, China
2Key Laboratory of Intelligent Computing & Information Processing of Ministry of Education, Xiangtan, 411105, China

Abstract—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 sheartransformation 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.

Index Terms—Overlapping area calculation; Irregular polygon; Convex polygon Clipping; Evolutionary layout.


Cite: Zi-qiang Li, Yan He, and Zhuo-jun Tian, "Overlapping Area Computation between Irregular Polygons for Its Evolutionary Layout Based on Convex Decomposition," Journal of Software vol. 7, no. 2, pp. 485-492, 2012.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly (2006-2019); Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Dec 06, 2019 News!

    Vol 14, No 1- Vol 14, No 4 has been indexed by EI (Inspec)   [Click]

  • Jun 22, 2020 News!

    Papers published in JSW Vol 14, No 1- Vol 15 No 4 have been indexed by DBLP     [Click]

  • Jun 22, 2020 News!

    The papers published in Vol 15, No 5 have all received dois from Crossref    [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Jun 22, 2020 News!

    Vol 15, No 5 has been published with online version     [Click]