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

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.

• Ali Nourollah
• Mohsen Movahedinejad

• Divide and conquer
• genetic algorithm
• merge polygons
• Random simple polygon generation.

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