**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32937

##### A Genetic Based Algorithm to Generate Random Simple Polygons Using a New Polygon Merge Algorithm

**Authors:**
Ali Nourollah,
Mohsen Movahedinejad

**Abstract:**

In this paper a new algorithm to generate random simple polygons from a given set of points in a two dimensional plane is designed. The proposed algorithm uses a genetic algorithm to generate polygons with few vertices. A new merge algorithm is presented which converts any two polygons into a simple polygon. This algorithm at first changes two polygons into a polygonal chain and then the polygonal chain is converted into a simple polygon. The process of converting a polygonal chain into a simple polygon is based on the removal of intersecting edges. The experiments results show that the proposed algorithm has the ability to generate a great number of different simple polygons and has better performance in comparison to celebrated algorithms such as space partitioning and steady growth.

**Keywords:**
Divide and conquer,
genetic algorithm,
merge
polygons,
Random simple polygon generation.

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1098960

**References:**

[1] C. Zhu, G. Sundaram, J. Snoeyink, J. S. B. Mitchel, Generating random polygons with given vertices, Computational Geometry: Theory and Application (1996) 277–290.

[2] T. Auer, M. Held, RPG: Heuristics for the generation of random polygons, in: Proc. 8th Canadian Conference Computational Geometry, 1996, pp. 38–44.

[3] P. Epstein, J. Sack, Generating triangulation at random, ACM Transaction on Modeling and Computer Simulation VOL 4 NO 3 (1994) 267–278.

[4] J. O’Rourke, M. Virmani, Generating random polygons, in: Technical Report 011,CS Dept., Smith College, Northampton, MA 01063, 1991,pp. 38–44.

[5] J. V. Leeuwen, A. A. Schoone, Untangling a travelling salesman tour in the plane, in: 7th Conference Graph-theoretic Concepts in Computer Science, 1982, pp. 87–98.

[6] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications 3rd ed, Springer-Verlag TELOS Santa Clara, CA, USA, 2008.

[7] R. L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letter (1972) 132–133.

[8] F. P. Preparata, S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Commun. ACM (1977) 87–93.

[9] R. A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Information Processing Letter (1973) 18–21.

[10] A. C. Yao, A lower bound to finding convex hulls., J. ACM (1981) 780– 787.

[11] S. K. Ghosh, Visibility Algorithm in the Plane, Cambridge University press, 2007.

[12] K.F. Man, K.S. Tang, S. Kwong, Genetic Algorithms: Concepts and Designs, Springer, New York, 1999.

[13] J.E. Rawlins, Gregory (Eds.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1991.

[14] L.D. Whitley (Ed.), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 1993.

[15] A.M.S. Zalzala, P.J. Fleming (Eds.), Genetic Algorithms in Engineering Systems, The Institution of Electrical Engineers, London, 1997.

[16] J.T. Alander (Ed.), Proceedings of the First Nordic Workshop on Genetic Algorithms and their Applications (1NWGA), January 9–12, Vaasa Yliopiston Julkaisuja, Vaasa, 1995.

[17] W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, FL, July 13–17, Morgan Kaufmann, San Mateo, CA, 1999.

[18] R.K. Belew, L.B. Booker (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, University of California, San Diego, July 13–16, Morgan Kaufmann, San Mateo, CA, 1991.

[19] J.R. Koza, D.E. Goldberg, D.B. Fogel, R.L. Riolo (Eds.), Genetic Programming: Proceedings of the First Annual Conference, Stanford University, July 28–31, MIT Press, Cambridge, 1996.

[20] G. Winter, J. Pe´riaux, M. Gala´n, P. Cuesta (Eds.), Genetic Algorithms in Engineering and Computer Science, Wiley, New York, 1995.

[21] J.C. Bean, Genetic algorithms and random keys for sequencing and optimization ORSA, Journal on Computing 6 (1994) 154–160.