More Tinkering with Random Shapes

In a recent post I talked about generating random shapes. The goal was to generate aesthetically consistent but still random shapes with smooth curves. One of the primary challenges was generating polygons which would not self-intersect (for aesthetic reasons). To get an idea for what I'm talking about, the following is an interactive illustration of the algorithm I ended up designing and using, taken from the linked post.

This is a sort of addendum to that one, talking about some other stuff related to generating simple polygons that wasn't included previously. So the first section talks about the travelling salesman problem and its relation to simple polygons. The following section briefly explores a trivial algorithm that uses triangles to build polygons. The final section explores triangular lattices, a really cool construct, in which we will build polygons.

Shortest Path

When you generate a number of completely random points and connect them, the resulting polygon is usually self intersecting. But when you order the points such that the cumulative distance between them is minimal, you get the following.

Yes, this is equivalent to the travelling salesman problem (TSP).

The shortest route through a given number of points (in two-dimensional Euclidian space) will always form the boundary of a simple polygon. This is probably obvious to some, but I found it fascinating. (Intuition: Every crossing can be eliminated while also decreasing local length.)

Of course, algorithms for (exactly) solving the TSP and related problems have terrible time efficiency. They are only a conceivably acceptable solution if we are given completely arbitrary points. This isn't usually the case, for example the "aesthetic" algorithm in the illustrated in the introduction was specifically designed to yield points that form a simple polygon—it's not designed to work on arbitrary points.

But the above observation has an important consequence: The problem of generating a simple polygon can be equivalently reformulated to the problem of finding an ordering for a set of points such that the path through them is minimal. So any and all algorithms that we may devise for yielding the vertices of a simple polygon must necessarily yield points in an order such that their path is minimal.

This is something I hadn't fully realized when I worked on the project that inspired the first post, and it narrows the solution space significantly. The options are either generating completely random points and using a TSP algorithm. Or generating points such that they will already be in an order that satisfies the TSP. An obvious way to do this is to start with some notion of circularity, as in the algorithm illustrated in the introduction for example. Another is to take a simple polygon that is trivial to randomly generate and build off of it in a way that doesn't violate the simpleness.

Triangles

An interesting topic in computational geometry (from my perspective as someone who presently has no clue about computational geometry) is triangulation, the subdivision of a simple polygon into a set of triangles. This section isn't about that, the algorithms with practical time complexities are beyond me at the moment, but an important result is that every simple polygon has a triangulation. That is a fancy way of saying that we can build more complex (simple) polygons from trivially simple polygons such as triangles, as was already alluded to in the last section. So let's do that!

Start with three completely random points and let them be the initial triangle. For each edge, imagine a square that has dimensions equal to the length of the edge and generate a random point inside of that square. Add them between the points of the initial triangle and you have a simple irregular hexagon.

You might have to regenerate the illustration a couple of times to see a good example, the algorithm is not very consistent. The initial triangle has a gray outline, the squares in which the additional random points are generated have a dashed gray outline.

One could now continue this transformation recursively on the "outer sides" of the newly generated triangles, perhaps inspired by constructions like the Koch snoflake. Of course, this will often produce self-intersecting polygons.

Performing the previously described steps repeatedly on the generated triangles, maximum recursion depth 3.

This (sometimes) looks cool but the result is neither a simple polynom nor particularly practical so I'll leave it at that. As an aside, this neatly shows that an arbitrary n-gon can be partitioned into no less than n - 2 triangles.

(In case it is not obvious, note that my choice to limit the additional random points to the square that can be constructed from the length of the respective edge is arbitrary. It was inspired by illustrations of the Pythagorean theorem.)

It's Lattice not Lettuce

According to Wikipedia, a lattice is an infinite set of points in the real coordinate space such that

• adding or subtracting two lattice points produces another lattice point
• the lattice points are separated by some minimum distance
• every point in the space is within some maximum distance of a lattice point

The following is an example of a lattice, with a line between randomly selected adjacent lattice points.

The (fixed) starting point is highlighted with a colored outline. By the way, this is an example of a random walk.

Again according to the linked Wikipedia article, lattices have many applications in pure mathematics, cryptography and physics. But we won't worry about any of that now, I'm talking about them here because I think they look cool.

So let's draw some shapes in a lattice. Of course, we can't just generate points and draw straight lines between them—we need to construct our lines by connecting adjacent lattice points. As far as we're concerned, nothing but these points exists, and we can't draw on nothing.

Let's build an algorithm that can connect two arbitrary lattice points (just called points, from now on), and later use it to write an algorithm for drawing arbitrary shapes. The algorithm we are looking for will return a polyline of minimal length such that it connects two given points without "leaving" the lattice.

A polyline is a sequence of straght lines. The maximum number of points that a polyline returned by our algorithm will contain is three—one for origin and destination respectively and optionally one to account for vertical movement that isn't diagonal to the origin.

A polyline of length four, between the center and a randomly selected point (marked with a colored outline) around it. Thicker gray circles mark all points that are four units removed from the center. Gray outlines mark points that were stepped through or considered. Note that diagonal movement requires steps and checks all the way, but horizontal movement is done in one step/check.

We first check if the two points (origin and destination) are in a horizontal line, this case is trivial. If they aren't, we will move a "cursor" in incremental steps from the origin in the direction of the destination, so right/left and upwards/downwards. After each step in this direction we check if the destination is in a horizontal line with the cursor. If it isn't we also check if it is in the diagonal opposite to our horizontal direction of movement. So if we are currently stepping to the top right, we would start stepping to the top left to see if we hit the destination.

The distance between the two points determines the amount of steps we need. So if we have a distance of seven and are on the third step in our primary direction, we only need to search for four steps in our off direction.

I have written a separate post about finding the distance between two lattice points. The following is an implementation of a TSP algorithm operating with this custom distance function.

What is particularly interesting about lattices is that in this space, solutions to the TSP are no longer unique because there may be more than one shortest path between two points. For the same reason we are also losing the property of simpleness. We have abandoned Euclid and must live with the consequences. But I like the look.

Art?

Recursive Triangles (a failed experiment)

Rounded TSP (with opacity steps)

Rounded Lattice (racetrack, anyone?)

Random Lattice Marketing

To be expanded...