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[1]),
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 [2]),
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**

- The Problem
- The "Almost Approach"
- Ways to solve the problem that take too long.
- Random Polygon Algorithm
- Implementing the Algorithm
- The good, the bad, and the UglieS
- Building the polygons in SVG with JavaScript
- Watching the process in progress
- Smoothing
- Giving additional personality to the shape
- Future directions
- Possiblities with random shapes
- Bibliography

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!

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:

- Create a random triangle by generating three random points in the bounding area
- Randomly select a line of the n-1 gon
- Calculate the region visible to the randomly selected line segment
- Triangulate the visible polygonal region into triangles (there are no holes in the visible region) [10]
- Select a triangle with probability directly proportional to its weight.
- Select a point within the triangle at random and with equal probability.
- 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.

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.

Figure 5: A random polygon, showing various operations and the x,y coordinates of the path associated with the polygon.

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.

Figure 6. Three random 15 sided polygons.

What is done here is that the smoothed path actually has its coordinates modified from

M 335 220 326 285 130 335 617 236 351 99 399 32 100 28 260 43 47 39 118 196 274 210 287 246 319 154 z

to

M 330.5 252.5 Q 326 285 228 310 Q 130 335 373.5 285.5 Q 617 236 484 167.5 Q 351 99 375 65.5 Q 399 32 249.5 30 Q 100 28 180 35.5 Q 260 43 153.5 41 Q 47 39 82.5 117.5 Q 118 196 196 203 Q 274 210 280.5 228 Q 287 246 303 200 Q 319 154 327 187 Q 335 220 330.5 252.5z

by letting vertices on the original path become control points in the smoothed curve and with new points lying on the new curve introduced at the midpoints of the original vertices. The differences between the two paths can perhaps be visualize more easily in Figure 9.

Figure 9. Superimposition of a normal polygon (green) and its smoothed (pink) versions. Areas in common to both are grey.

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:

- Random colors. By choosing the color option, a random color in RGB space may be applied to the shape.
- 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
- 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.
- 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.
- 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.
- Animation. Various options for animating the gradients associated with the on-screen objects have been developed for some interesting visual effects.

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

- adding code as a module in SVG-edit or Inkscape (make a random polygon)
- establishing the code base as an open source project.
- fancier options for smoothing
- interpolation (as with <replicate>)
- more filter effects
- more complex filter effects
- customized control over colors and gradients
- making the overall code faster
- allowing multiple gradients to be associated with multiple saved paths.
- 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.

[8] Chvátal V. 1975. A combinatorial theorem in plane geometry, J. Combin. Theory B18 (1975), 39-41.

[9] http://srufaculty.sru.edu/david.dailey/svg/polygons6.svg and http://srufaculty.sru.edu/david.dailey/svg/polygons7.svg

[10] Ratcliff, J. COTD Entry submitted by John W. Ratcliff http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml