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, 4]. The problem of how to generated random polygons has resurfaced in modern times in both computational geometry [5] and in research in human perception[6]

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 [7]. 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 [6] 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 [8] demonstrated in the early 1970's that while all n-gons can be lit with n/3 lights, some do require that many.

Fig. 1. A polygon requiring more than one light source.

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 this process.


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 [9] 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.”

Often in the computational literature the problem of generating random polygons is phrased a bit differently. That is, perhaps following the popularity of the well-known problem of Hamiltonian circuits (known as the traveling salesman problem), we are often expected to start with a collection of n random points, and then to construct a polygon from those. Why one would wish to phrase the problem this way, or exactly what the practical benefit is of that approach (since it seems more likely to begin with a set of specific points than a set of random ones) as opposed to the present one remains unclear.

Nevertheless, if given a set of n points randomly chosen in the plane (typically in within a given rectangle since it is hard, in practice to generate points at random between 0 and infinity since so many of them end up being infinite!), we wish to find a polygon (i.e. a path having no crossing lines) constructed on those points, then this problem does start to have some of the apparent complexity associated with the NP-complete problems. For example, given an arbitrary set of points, many of the lines between those points will cross one another. There will necessarily be at least some sequences of traversals of those N points that have no crossing lines, but with N points there are N! different traversals. Prior to the authors’ first paper on this subject [2] there appears to have been no solution to the problem that ran in time bounded above by any fixed polynomial function of the number of vertices. We might try replacing pairs of crossing lines by either of the other two-edged graphs on four nodes that involve no crossing lines, but certain of those realignments will result in a disconnect, unless we have the ability to look ahead. Again the problem takes on the character of the NP-complete problems, in this multiplicatively expanding sequence of interdependent choices.

Two other approaches may come to mind, other than the one we finally present. First we might consider Chvatal’s theorem [8] to begin with n/3 lamps and from each of these to generate a star-like cluster. We might then consider stitching those individual clusters together (e.g., pairwise) so as to grow more complex polygons out of simpler ones. The problem, of course, with this reasoning is that finding a nontrivial way of identifying pairs of these n/3 points together as candidates for stitching requires that two such pairs do not overlap with one another: precisely the same problem we began with of finding a Hamiltonian path without crossing lines, albeit on a linear reduction of the original problem!

Secondly, we might consider the “onion-skin” approach. Find a series of concentric convex hulls. Finding a convex hull (an outermost convex polygon containing all the other points on its interior) is computationally “easy” from a time-complexity point of view. Accordingly, we can just as easily produce a sequence of concentric convex hulls starting with the outermost shell and working inward until we have a point, a line, or a convex polygon. We may then consider all possible ways of routing a path in and out of these convex hulls. If we are not careful, we will end up producing only shapes that look like spirals. If we are truly careful to include all possible shapes, then the problem seems to explode in combinatorial complexity!

It is these various attempts that don’t work, that motivates the approach presented in this paper!

The Random Polygon Algorithm (RPA) [2] was implemented in Javascript to generate a random n-gon in polynomial time. Unlike some approaches to generating n-gons, the polygon is not constructed by starting with n points as input, but instead, the points are generated at random as the polygon is constructed. The algorithm produces as output a polygon that is random and representative of the class of all n-gons. Briefly, the RPA operates as follows:

1. Create a random triangle by generating three random points in the bounding area
2. Randomly select a line of the n-1 gon
3. Calculate the region visible to the randomly selected line segment
4. Triangulate the visible polygonal region into triangles (there are no holes in the visible region) [10]
5. Select a triangle with probability directly proportional to its weight.
6. Select a point within the triangle at random and with equal probability.
7. Add the new point to the n-1 gon to create the n-gon (by adding the line segments from it to the endpoints of the chosen line.

RPA was implemented in Javascript and tested in both Firefox and Explorer. The implementation began by strictly following the algorithm, however as work progressed, many short cuts were found. As most of the steps above are simple, only the implementation of step 3 above will be discussed here. Although triangulating can be difficult (step 4), Ratcliff's C++ code was easily translated to Javascript.

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:

1. Create a list of vertices that initially consists of the vertices of the original n-gon. This ordered list consists of potential vertices for the visible region and will be updated as the vertices are examined.
2. Create another list to maintain the bounding box
3. Extend the random line segment in both directions. Insert the intersection point(s) that are inside the n-gon in the correct location. If one or both of the intersection points are on the bounding box, determine the regions of the bounding box that are visible.
4. Traverse the list of vertices that are potentials for the visible region. If a vertex is visible, it remains in the list; if it is not, then it is removed from the list. However, whenever there is a switch from visible to not visible between two adjacent vertices (or a switch from not visible to visible), then that line segment has to be examined to determine the segment of the edge that is visible.
   When there is a switch in visibility, then either the previous node or the last visible node occluded the visibility. Both are tested and the appropriate intersection point(s) on the edge are calculated. At most two new points are found and added to the visible region list. It is possible that the intersection point does not lie on the edge.

Although the process is straightforward, several unforeseen issues were encountered; not all of which were bad.

THE GOOD

The implementation of an n-gon was accomplished with an array of objects where the object held x,y coordinates of the vertices. This implementation was a natural translation to the svg path object.

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.

Permitting the user to select a region in which to draw the n-gon was not part of the original RPA. However, its implementation was simple once the bounding box was defined.

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.

THE BAD

Several issues arose during the implementation that expanded the length of the code and/or were not foreseen when the algorithm was created.

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

Figure 4. New vertices along partially visible edges. From a and b, pts. 2, 3, and 4. are visible while 1 and 5 are not.  Pts 2 and 3 are added to the perimeter of the visible region.

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

Two ugly issues raised their heads during the implementation.

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.

Furthermore if floats are rounded to integers, then triangulation may fail because the n-gon now has a hole in the visible region. If the random point is only one pixel away (using integer calculation) then you now have an "unreachable" region of the n-gon. Currently, the program detects the problem of creating a hole and restarts by selecting another random edge. This so-called solution is not practical and could theoretically cause an infinite loop. The authors are considering two approaches to solve this problem. The first would involve simply using floating point numbers and assuming the  probability of holes would be infinitessimal given the resolution of floating point numbers in Javascript. Secondly, one could round to integers and then if the random point in the randomly selected triangle (step 6 of RPA) is within a threshold (e.g., one pixel), then move that point further from the edge on the n-1 gon.

From the outset, the authors sought to build a program which had some considerable flexibility. We wished for the user to be able to

• produce a polygon of n edges, for a given n and a particular bounding box.
• expand the polygon incrementally, one vertex at a time.
• re-generate new polygons easily.
• experiment with textures and colors
• smooth the polygon, by converting into Bezier curves using the polygons vertices as control points.

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 [9]

When the program starts, the web page looks similar to Figure 5. A random polygon of 15 points is illustrated.

< 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”>

If the user wishes to visualize the algorithm as it creates a polygon, one may begin with a random triangle (using the Fresh 3 option). Subsequently one may choose the “add vertex” option to grow the polygon one vertex at a time as illustrated in Figure 7.


Fig. 7. Showing the evolution from a triangle (3) through a decagon (10).

The numbers in Figure 7 show the positions of the new vertices. Using the “Almost Approach” discussed earlier, the user can interactively help build the polygon by clicking on points in the plane either inside or outside the given triangle. From any point selected by the user, a line visible to that point is randomly selected from among all such lines and then the new point is incorporated into the path as described earlier. From Figure 7, one can see that steps 4, 6, 7 and 8 add area to the polygon, while steps 5, 9 and 10 remove area from it. If the following conjecture can be proven, then we would expect, asymptotically that the probability of a point adding to the curve (as opposed to subtracting) will approach 0.5. Conjecture: The area of an n-gon constructed via the Almost Approach will approach half the area of the bounding rectangle.

Given a random polygon one may convert it from a polygon to a smooth curve by choosing the “smooth” option. This takes a curve as shown above in Figure 8 and converts it into one as shown below.


Figure 8. Before and after smoothing a polygon

In addition to allowing an n-gon to be smoothed (which changes its appearance considerably), the software also implemented the following techniques for adding visual uniqueness to a shape:

1. Random colors. By choosing the color option, a random color in RGB space may be applied to the shape.
2. Random gradients. A random gradient, either linear or radial may be applied. The five stop-colors in that gradient are each chosen randomly in RGB space with bits of transparency applied randomly and somewhat judiciously
3. Random feTurbulence. The SVG feTurbulence filter may be applied as a fill pattern for the region, with the scale of that turbulence being randomly determined.
4. Random Patterns. An SVG <pattern> is randomly constructed. The size of that pattern space is randomly determined as is the position, shape, and color of five random ellipses placed into that pattern space.
5. Keeping and adjusting positions. Opportunities for the user to “keep” a shape by removing it from the document’s work space and placing it in a permanent layer have been provided. Currently, kept shapes all inherit the same working gradient.
6. Animation. Various options for animating the gradients associated with the on-screen objects have been developed for some interesting visual effects.

The user also has the option of “seeing” and “saving” either a shape or the color values of a particularly appealing gradient by displaying relevant parts of the underlying SVG code.

The following are all among the tasks the authors would like to undertake or to encourage others to undertake:

1. adding code as a module in SVG-edit or Inkscape (make a random polygon)
2. establishing the code base as an open source project.
3. fancier options for smoothing
4. interpolation (as with <replicate>)
5. more filter effects
6. more complex filter effects
7. customized control over colors and gradients
8. making the overall code faster
9. allowing multiple gradients to be associated with multiple saved paths.
10. investigating the possibility of using the approach of first choosing an arbitrary point in the bounding box, finding a line segment visible to it, and then replacing that line segment by two new ones.