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.