path

Read:

Some techniques of drawing random polygons.

See our recent paper and presentation on this topic at SVG Open, Paris, 2010.

A friend and former colleague of mine, Leonard Zusne, wrote a book: Visual Perception of Form Academic Press - 1970. The book was a collection of studies on the psychophysics surrounding the perception of shapes.

I recall one study which generated random polygons for use as stimuli in perceptual research: Given a positive integer, n, a collection of n pairs of the form Pi=(alphai, di) is generated in which 0≤ alphai < 2π represents an angle, and d represents a distance from the origin.

P2

Borrowing from the terminology of the later-posed art gallery lighting problem, the polygons thus constructed are those lightable by a single lamp.

Click here repeatedly to generate polygons of increasing complexity, but all lit by a single lamp. Provided, the center point is located inside the polygon, the polygon has no crossing lines.

P3

Not all polygons are thusly constructable. The one below requires three lights. Some 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. Alternatively, therefore to generate all n-gons, we could consider positioning n/3 lights randomly in the plane, and then building a star from each. It is not obvious (to me) how we would connect the various stars, so this approach seems, although doable, to be a wee bit unwieldy.

P4

Another way would be to generate n random points in the plane and then figure some way to draw a path through all of them exactly once returning to the beginning, without any crossing lines. There will be on the order of n! different paths through the n points; some will have no crossing lines. But how might we make sure that we sample fairly from all of these, without explicity enumerating them? Try building a random collection of 7 points in the plane: Now try a random path through them: If this is going to be easy, I don't see it -- it looks rather like the traveling salesman problem

P5

Another approach might be to find a convex hull H: a convex polygon on k<n points for which the remaining n-k points are all on the interior of H. We may note that if we label the points of H in clockwise order, then no two non-adjacent points in H may be connected. Therefore it seems, the degrees of freedom in the drawing of a simple polygon will be reduced, presumably, therefore, improving our ability to find one. We could partition the points into a series of concentric convex hulls, and later stitch together the points of these hulls with some sort of needlework.(Note my code is not quite right yet.) or build

P6

A final approach worthy of consideration would be to start with a triangle, and work inductively from n-1-gons to n-gons, by, at each stage, selecting one edge at random and replacing it by two (chosen so as not to cross any other edges). It seems obvious that all n-gons may be thusly constructed (is it obvious?). In the following technique, we might imagine restricting the newly built point such that we move the point along a line perpendicular to the replaced edge until neither of the two new lines crosses any others. The process resembles the construction of the Koch curve, familiar to many, because of its frequent use in introducing fractals.