Generating Random SVG Elements in Polynomial Time

David Dailey1, Deborah Whitfield1, George Shirk
1Slippery Rock University
Play (29min) Download: MP4 | MP3

The ability to generate dynamic graphical content is a major asset of SVG. Accordingly, a natural question that has caught the attention of computer scientists for some time is how to efficiently generate “interesting” random shapes. The generation of random shapes could be used to mimic scenery found in nature which appears to the human eye to be truly random. Trees grow at apparently random angles, water bodies such as lakes, and oceans have random contours edges. Furthermore, streams have unusual edges and meander randomly. Random polygons with a large number of edges can be smoothed, filtered and given gradients to resemble natural entities such as clouds, lakes and land formations. An efficient algorithm for generating poly-gons has been created and implemented in SVG. The paper will demonstrate its use to create random shapes.

The SVG code is implemented so that the user simply needs to select the number of points and the bounding size of the n-gon to be created. The algorithm is provably random – it can generate any possible n-gon within the specified bounding box. Furthermore, it is fair and representative – it does not tend toward a typical shape as other techniques do (e.g., convex hull, star-shaped polygons). Unlike other techniques (Auer, Held), it does not require a given set of vertices, but rather generates the vertices randomly as the polygon is constructed. Additionally, taking advantage of newly discovered methods (Dailey & Whitfield), it draws these polygons in time polynomially related to the number of vertices, unlike the previous exponential-time techniques that have been explored for this problem from a given set of vertices.

This paper will introduce the algorithm and its implementation, and provide numerous examples of the utility of the technique. The technique may be used for creating interesting random shapes and elements of nature. SVG gradients, filters, noise, and patterns are used to make the dynamic images more realistic. In addition, the polygons can be smoothed using cubic splines and Bezier curves. The authors intend to extend this work to improve the efficiency of the algorithm for generating random polygons.