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. 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. This paper demonstrates its use to create random
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 method (Dailey & Whitfield ), it draws these polygons in polynomial time 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 introduces the algorithm and its implementation, and provides 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.
Table of Contents
Random polygons have been of
interest in probability theory since at least shortly after the
solution of Buffon’s needle problem in the early 1700’s [3,
The problem of how to generated random polygons has resurfaced in
modern times in both computational geometry 
and in research in human perception
To the researcher outside this area, it may not immediately be apparent why the problem is difficult, so the authors begin by introducing a brief treatment of the topics “why are the easy approaches not good enough?” and “why are the good approaches not easy?”
Let's examine some easy ways to generate some but not all random polygons.
First we follow a technique suggested from certain discussions within probability theory . We take a collection of n points on the unit circle and join them by lines according to their clockwise ordering from any start point. The n points may be generated by simply choosing n angles (real numbers in the range 0 to 360, in SVG’s angle-handling language). Those n numbers may be sorted from least to largest. This sort (taking at most n log (n) steps) provides the clockwise ordering and, from that, we have an n-gon drawn on n randomly chosen points. The problem with this approach, however, is that it is limited in such a way that all of its vertices will be on a circle. More significantly perhaps, because of that fact, it will always be a convex polygon. We have in effect found a way to chose randomly from among those convex polygons having the special property that all vertices lay on a circle. Polygons with concavities, thus, may not be generated via this technique.
Next, consider this approach used in the psychology of perception literature  Begin by choosing one central point. As before generate and sort a series of n angles from 0 to 360 degrees. Along each of those rays, emanating from the center point, choose randomly a positive number between zero and the distance to the edge of the screen (or bounding rectangle). Connecting the generated points, creates a random n-gon, without the limitation of being convex. However, the polygons constructed are those which, in the terminology of the museum lighting problem, can have their edges illuminated (via line-of-sight) by a single lamp placed on the interior of the polygon. Not all polygons can be illuminated with a single lamp. The polygon in Figure 1 requires three lights. Some polygons require arbitrarily many inside lights. Hence, one is forced to think of other ways to proceed. Chvatal  demonstrated in the early 1970's that while all n-gons can be lit with n/3 lights, some do require that many.
Yet another approach that fails to
generate all possible polygons, but which can be implemented with
comparative ease, is the following:
Let us work recursively, starting with a triangle and, given an n-gon,
P, defining from that an n+1 –gon . Choose the next point, q, anywhere
in the plane (but not on an existing side of P) . Draw lines from this
new point to each of the vertices of P. Among all those vertices whose
line from them to the new point q does not intersect P, find two, u and
v, that are adjacent on the polygon (i.e., share a line segment of P).
Replace this line uv with the lines uq and qv. The result is a new
polygon with one more vertex than the preceding. Figure 2 illustrates
Figure 2. Step 1: Given a Polygon P, find any point q, then from among the edges of P visible to Q choose one, L, at random. Step 2: replace L=uv by uq and qv
The only problem is that in certain instances, the algorithm may find a point from which no line is visible. This situation is demonstrated by the diagram in Figure 3.
Figure 3. A situation in which no point within the shaded region, if chosen, would have a complete edge of the polygon visible to it.
While the above illustration of Figure 3 makes it clear that this approach sometimes generates situations in which a particular chosen point may not succeed in allowing the next line to be replaced by two, it is believed that a) these situations are relatively rare and b) if one were to find such a situation and simply resample a new point, we could do so without loss of generality – that is, we conjecture that all polygons could be constructed via this technique. However, this is still unappealing from the perspective of computational complexity, since it is not clear yet that we can easily characterize all these “untenable” situations, and therefore the worst case runtime behavior of such an algorithm might be infinite. If this conjecture is accurate then, it may well be that our implementation of this procedure  might be “faster” than the more robust algorithm that is presented as the primary contribution of this paper. We will have occasion to refer to this approach later and will call it the “Almost Approach.”
A point object and line object were defined to maintain the structure of an n-gon. A point consisted of two values: x and y. A line consisted of two points and a vertex number that was used for easy indexing. To calculate the visible region, a new polygon was created that consists of the interior and exterior area visible to both endpoints of the randomly selected line. The visible region calculation process consists of:
Prior to the implementation, it was assumed that the algorithm would have to make two passes: one to determine exteriorly visible region and another to determine interiorly visible region. However, two implementation techniques were used that made the second pass unnecessary. First, separate lists were created for tracking interior and exterior visible regions. Second, when the randomly selected edge was extended, if it intersected the bounding box, the exteriorly visible region was updated (prior to traversing the n-gon). Thus when other exteriorly visible vertices were found, they were easily added at the correct location in the exterior list.
Intersection calculations were an integral portion of the implementation of the algorithm. Intersections between two line segments, a line and a line segment, and counting the number of intersections were crucial to the implementation. A basic intersection test was written to do the calculations and separate functions for segment and line intersections were built to call the basic test. In addition, separate counting functions were then built that called the appropriate intersection test.
Determining whether a point was visible from the inside or the outside was implemented using the popular test that counts the number of path segments that a line from that point intersects as the line is extended to the bounding box.
Walking the n-gon was easily implemented using the array of vertices. When a visible vertex was encountered, determining which vertex was the last visible was easily implemented since the array of potentially visible points can be directly queried. A marker within the array of potentially visible vertices divided the array into two pieces: on the left, those vertices known to be visible, and on the right, those vertices that were potentially visible. This technique is the same as the one used by the popular insertion sort.
Extending the randomly selected edge required extensive programming once it was determined that the interiorly and exteriorly visible region could be calculated in one pass. The issues were a result of determining how to maintain the correct order of the vertices that were visible exteriorly. The separate lists for interior/exterior had to be stitched together after the n-gon was walked. So when extending the random edge, it was important to order the exteriorly visible bounding box vertices relative to the node where the walk begins.
As a consequence of combining the two walks (exteriorly and interiorly visible) into one, it was necessary to maintain whether the last vertex was visible to the source and/or the sink of the random edge, and whether that visibility was with respect to the interior or exterior. After struggling with the interiorly or exteriorly visible issue, an object that contained information about the visibility of a vertex was created to solve the problem. It was quickly observed that it would be less computationally complex if the calculation of the visibility object was done once before the walk of the n-gon and this information saved in an array. Thus, re-calculation of the same information inside the loop that walked the n-gon was not necessary. After the selected edge was extended, every vertex of the n-gon was examined to determine if it was visible from the source and/or sink and if so, was it from the inside or outside.
It was briefly considered that the knowledge of whether it was visible from the inside or outside was not necessary; only whether a vertex was visible to the edge from the same side. However during the walk of the n-gon, it is necessary for the differentiation. It must be know whether the last node was visible from the inside or outside so that any new intersections are added to the correct list.
During the walk of the n-gon, new intersection points had to be inserted into the correct location. Given the vertex ordering that existed, it was relatively easy to make this determination and either splice the new vertex before or after the node being examined. Initially, this expanded the code. However, a parameterized function reduced the code length, but at the same time increased the number of parameters in multiple functions. (Note: the programmer despises global variables).
When determining the intersection point when a prior vertex was not visible and the current one is, it is possible for the intersection to occur off the n-gon line. Consider the Figure 4 where the randomly selected edge of the n-gon is shown with the two red vertices and the two yellow vertices shown intersection points on the n-gon. Where the two yellow lines intersect, is visible to the selected edge and must be included in the visible region. This case was not part of the original published RPA and is not yet implemented.THE UGLIES
As discussed above, part of the implementation required determining whether a point was inside or outside of an n-gon and the typical test that counts the number of intersections was used. In the case that the intersection occurred at a vertex, the counting technique counted the vertex twice: once for each of the two edges. If the x,y coordinates are stored as floating point numbers, round-off errors created other problems including the possibility that the vertex would not get counted at all. Thus, conditionals to specifically check for end points were necessary.
One of the most intriguing problems is a product of applying a theoretical concept. The display device is a finite area and integer pixels are used for display purposes. However, intersection points are not necessarily integers. When the visible region is being calculated and the intersection points are being determined, two calculated points (intersections are calculated with respect to the last visible vertex and with respect to the previous vertex) can appear as the same point on the screen. Also, if any intersection point is close enough to another edge, the n-gon begins to appear to have holes.
As the prototype code began to develop we discovered something slightly unexpected: the shapes and forms generated were often “interesting.” A bit of scope-creep then occurred as we realized that the act of “drawing” often entails considerable serendipity. Accordingly, we have come to conceptualize this work as having possible utility as a drawing tool. We are interested in sharing the source code with others, perhaps as an add-in to a project like SVG Edit, or as a stand-alone serendipitous drawing program.
Thus, the user of this software may experience a sense of divergent purpose. Yes, the overall goal of generating n-gons in polynomial time using SVG has been met, but in pursuit of our stated goal of drawing “naturalistic shapes” we began to toy with the idea of a “package” rather than a mere algorithm. In this section we briefly explain what the working code actually does and how to use it. At the time of this writing, the code itself is still evolving. We will illustrate using an earlier version 
When the program starts, the web page looks similar to Figure 5. A random polygon of 15 points is illustrated.
This version also shows the value of the “d” attribute of the associated SVG path, should one wish to be able to recreate the particular path. In this case, we can use the displayed coordinate data to easily build the associated polygon in our own SVG code:
< path d = “M 685 134 596 85 507 49 153 17 601 168 87 66 452 148 506 284 270 163 86 216 55 276 315 329 629 391 747 361 441 322 611 281 789 324 613 253 z”>
Redefining new polygons. By choosing the option “fresh 15” a new 15 sided polygon will be generated. Examples are shown in Figure 6.