Constructing random polygons

ABSTRACT

The construction of random polygons has been used in psychological research and for the testing of algorithms. With the increased popularity of client-side vector based graphics in the web browser such as seen in Flash and SVG, as well as the newly introduced <canvas> tag in HTML5.0, the use of random shapes for creation of scenes for animation and interactive art requires the construction of random polygons. A natural question, then, is how to generate random polygons in a way which is computationally efficient (particularly in a resource limited environment such as the web browser). This paper presents a random polygon algorithm (RPA) that generates polygons that are random and representative of the class of all n-gons in O(n²logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.

References

1. Ahn, H. K., de Berg M., Bose P., Cheng S. W., Halperin D., Matousek J. V., and Schwarzkopf O. 2002. Separating an Object from its Cast. Computer-Aided Design. 34, 8 (July 2002), 547--559.
2. Auer, T. and Held M. 1996. Heuristics for the Generation of Random Polygons, in: 8th Canadian Conference on Computational Geometry (CCCG). Ottawa, Canada, 1996, 38--44.
3. Chazelle B. 1991. Triangulating a Simple Polygon in Linear Time. Disc. Computational Geomentry 6(1991), 485--524.
4. Chazelle, B., and H. Edelsbrunner 1992. An Optimal Algorithm for Intersecting Line Segments in the Plane, Journal of the ACM. 39 (1992), 1--54.
5. Chvátal V. 1975. A combinatorial theorem in plane geometry, J. Combin. Theory B18 (1975), 39--41.
6. Clarkson, K. L., Tarjan R. E., and Van Wyk C. J. 1989. A Fast Las Vegas Algorithm for Triangulating a Simple Polygon. Discoveries of Computational Geometry. 4 (1989), 423--432.
7. Dailey, D. P. 1978. Graph Coloring by Humans and Machines, a Polynomial Complete Problem Solving Task. Doctoral Dissertation, University of Colorado, 1978.
8. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Mathematik. 1 (1959), S. 269--271
9. Graham, R. 1972. An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set. Info. Proc. Letters. 1 (1972), 132--133.
10. Epstein, P. and Sack J. R. 1994. Generating Triangulations at Random. ACM Transactions on Modeling and Computer Simulation (TOMACS). 4,3 (1994) 267--278.
11. Mandelbrot, Benoit B., The Fractal Geometry of Nature, W. H. Freeman and Co. San Francisco, 1982, 34--57.
12. Michael, T. S. and Val Pinciu 2003. Computational Geometry: Theory and Applications. 26,3, (Elsevier Science Publishers B. V. Amsterdam, The Netherlands, The Netherlands 2003). 247--258.
13. Mitchell, J. S. B. and O'Rourke J. 2001. Computational Geometry Column 42. International Journal of Computational Geometry Applications. 11,5 (2001) 573--582.
14. Prim, R. C. 1957. Shortest connection networks and some generalisations, in: Bell System Technical Journal, 36 (1957), 1389--1401.
15. Toussaint, G. T., Sitaru V. and Ruso T. 1996. Drawing Simple Polygons through Point Sets at: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
16. World Wide Web Consortium: HTML 5: W3C Editor's Draft, September 22: The Canvas, 2007: http://www.w3.org/html/wg/html5/#the-canvas
17. Zhou, Z. 2007. Developing BREW Applications with Qualcomm's SVG Solution SVG Open, Tokyo, September 2007.
18. Zhu, C., Sundaram G., Snoeyink J. and Mitchell J. S. B. 1996. Generating Random Polygons with Given Vertices Computational Geometry Theory and Application. 6 (1996) 277--290.
19. Zusne, L., 1970. Visual Perception of Form, Academic Press, New York, 1970.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry