Let’s generate random non-overlapping polygons on a plane! Sounded fairly simple to me at the beginning, but soon I discovered those nasty polygons are not as innocent as I thought.

I originally had an idea to explore another optimization problem. I don’t want to write much about it as I’ll probably cover it in a future post but as a first step to it, I had to be able to cover a square area with random non-overlapping polygons. I was mainly interested in equally covering the whole plane (more or less) with many shapes that don’t overlap. Other than that, I didn’t care much and expected it to be fairly simple, although not trivial. Luckily enough, Prof. Dan Halperin works in the office right next to me. He showed me a paper he wrote on Minikowski Sum, and some of the random polygons they generated there proved me that I don’t really want random polygons. Random polygons also include holes, crosses and polygons with 200 vertices that just look like an overkill for me.

So I went with a second approach - why not considering the square area as a large grid, remove some of the boundaries between adjacent cells to create randomly shaped blocks, and then, draw exactly one polygon inside every block. Given a block, drawing the polygon inside shouldn’t be that difficult and although this approach doesn’t cover all possible polygons, it’s much simpler, straight-forward and ensures me full coverage, non-overlapping and polygons that look more like what ordinary people expect them to.

In high level, it will look something like this:

There are two main factors to play with:

• N - the size of the grid (NxN)
• p - the probability of a separator between two cells to exist

Step 1: Generating a Random Grid

Generating a grid inside the square is pretty simple. Making it a Random Grid shouldn’t be a difficult task for anyone with more than 5 minutes experience in any programming language. Just iterate over all separators and remove them with a probability 1-p.

I didn’t feel comfortable enough with p as it’s not very intuitive. I felt like the user should at least be able to get the feeling of what an average block size would be while he plays with different values for p so I started looking for an expression for the number of blocks (or the average block size) in a grid of size NxN when p is the probability for a separator.

I finally used \( \left[ \frac{ (1-p)^N(Np-p+2) + p - 2 }{ p } \right]^2 \) as the expression for the average block size by N and p. It’s not accurate, but gives an estimation that is fairly OK for our purpose considering that we’re mainly interested in large N and p around 0.7-0.8 (large grids and a lot of the separators in place). You can play with different N and p in the example below.

Developing this expression was really nice (at least I think so..) but involved some math that some might find as scary (it’s really basic, but sometimes gets long and ugly). If you want to see how I got this (and you should!), scroll down to the Random Grid Expression Drill Down section. For simplicity I’ll continue assuming this estimation works.

Step 2: From Blocks to Polygons

Given a set of blocks, we want to draw a polygon in every block so every polygon preserves the shape of the block (that was randomly created) and doesn’t get out of the block so we get the non-overlapping property for free. I could draw a squarish polygon inside every block, but that would be boring. Instead, I had the following pseudo-code in mind:

for block in blocks:
    polygon = []

    for separator in block.separators:    
        point = separator.randomizePoint()
        point.addPadding()

        if (nonConvexTurn()):
            polygon.push(cornerPoint)

        polygon.push(point)

    polygon.draw()

Notice that we must take care of the ‘non-convex’ turns. Otherwise, a line drawn straight between those two points will cross another cell and may overlap with the polygon that is there.

I implemented something like this pseudo-code in Javascript. I officially hate this programming language now! I really don’t see why they need to get to the 6th version of the language (ECMA6, not supported yet in most browsers) to add equality operator override and Array utilities, but whatever.. It’s done now and you can see it below.

Example

Below is an example for generating random polygons using the algorithm described. You can play with N to change the grid size, p to change the separator’s probability and get an estimation of the block size. Good luck!

Random Grid Expression Drill Down

Our goal in this (long) section will be to explain the expression for the average block size in a random grid of size NxN with a separator probability of p as shown before.

First, I’ll note that while the original problem came from the world of grids, tiles and separators, one can easily transform the grid to a graph (where every cell is a vertex), the separators to edges (where every two cells that are not separated are connected with an edge) and therefore ask: how many connected components are there in a Random Graph with a probability p for an edge.

The only difference, and apparently that’s a big one, is that a grid is not a regular graph and not every vertex can be connected to all the others. Only those who are adjacent on the grid can have an edge between them. While I’ve found some (pretty complicated) theorems on number of connected components for a general random graph, I couldn’t find anything that I’ll be able to convert to the grid use-case (aka a Lattice Graph) and so I decided to try and get an estimation on my own.

Reducing to a Random Row

A grid, as being a two-dimensional object, is not a very simple one for combinatorics calculations. I tried to tackle it from different angles and decided the best would be to reduce the problem to something more convenient.

A simpler version of a grid would be a single row. If we can find an expression that ties together block sizes, N and p for a single row, it might be easier to get the more generic grid case from there. Basically, we are looking on the following problem:

What’s the expected number of blocks of size K in a row of size N with p as the probability for a separator?
\(E_N(k) = ?\)

In the example above, we have 3 blocks of size 1, 2 blocks of size 2 and 1 of size 3. We want to express the expected (on average) number of blocks of any size by N and p.

Reducing Again to a Cyclic Row

A ‘regular’ row is very annoying as well because the first and last cells are different from the others (have only one adjacent cell). If we want to consider the probability for a block to start on the 1st cell, we can assume there is no neighbor on the left, but in other cells we’ll have to restrict the left separator to be in place. I tried two ways to overcome this. One was writing an expression for an infinite row and then ‘look’ only on part of it (otherwise all expected numbers are ∞). The other, which is what I moved on with, was to look on a cyclic row (a row where the rightmost separator actually separates the last and the first cell).

This assumptions is clearly not in the original problem, but we can assume it is minor, and for large N it won’t make a difference (2 different cells out of a 100 don’t affect much the number of blocks of size 5..). At the end, when we’ll have an expression based on a cyclic row, it’ll be worth checking how well it estimates a regular row.

Let’s define \( X_i^k \) to be a random variable that gets the following values:

\[
X_i^k=
\begin{cases}
1 & \text{if a block of size } k \text{ starts at cell } i \\\
0 & \text{otherwise}
\end{cases}
\]

We denoted before \( E_N(k) \) as the expected number of blocks of size k in a cyclic row of size N. Because the row is cyclic and blocks can start at the end and span to the beginning, the random variable for the number of blocks of size k in a row should simply be \( \sum\limits_{i=1}^N{X_i^k} \).

Here’s the tricky part - Although \(X_i \)s are statistically dependent on each other (i.e. if a block of size 3 starts at the 1st cell, another one can’t start on the 2nd cell as well), \( E_N(k) \) is the expected value of the sum of them, and from the Linearity of Expectation property we get:

\[
\begin{align}
E_N(k) & = E \left( \sum\limits_{i=1}^N { X_i^k } \right) \\
& = E(X_1^k) + E(X_2^k) + \cdots + E(X_N^k) &&\text{from linearity of expectation} \\
& = P(X_1^k) + P(X_2^k) + \cdots + P(X_N^k) &&\text{X gets 0 or 1 with probability P}\\
& = NP(X) &&\text{from symmetry - all P’s are the same}
\end{align} \\
\text{(Where } P(X) \text{ is the probability for a block of size } k \text{)}
\]

Let’s look on P(X). If p is the probability for a separator, we need 2 separators on both sides of the block, and then another (k-1) in the middle. Therefore, \( P(X) = p^2(1-p)^{k-1} \) and that makes:

\[ E_N(k) = Np^2(1-p)^{k-1} \]

The exception to that is when \( k = N \). In that case, there are no two separators at all so the whole expression is wrong. In order to get a block that fills the whole row, you can either have only one separator somewhere in the row (P(X) will be \( p(1-p)^{N-1} \) and we can have it in N places), or none at all (and then P(X) will be \( (1-p)^N \) and can only appear in one place as no matter where you start this combination of separators, you’ll get the same block). So if we try to express \( E_N(k) \) more accurately, it’s going to be like:

\[
E_N(k) = \begin{cases}
Np^2(1-p)^{k-1} & k<N\\
Np(1-p)^{N-1} + (1-p)^N & k=N
\end{cases}
\]

Given that expression, the expected number of blocks in a row would be a summation of the expected number of blocks for any possible length (i.e. 1..N). We’ll denote that as \(B_N\):
\[
\textbf{NUMBER OF BLOCKS} = B_N = Np + (1-p)^N
\]

Verify the \(E_N(k) \) Expression for a Cyclic Row

As we defined, \( E_N(k) \) is an expression for how the expected number of blocks of size k in a row of size N depends on p. Obviously, the total size of all blocks in a row should be N so the following equation should hold:
\[
\sum\limits_{i=1}^N{ i E_N(i) } = N
\]

Another thing we can do is to simulate many random cyclic rows, count the number of blocks and compare to the estimator we got here. Ohh, how lucky I am to know python (code is here).

The following graphs shows \( E_8(k) \) (N=8, k=1..8) by p. The blue line is the average number of blocks in 1000 iterations and the green line is the estimated number based on the expression above. I think we’ve nailed the cyclic row!

Verify the Cyclic Assumption

Just as a reminder, we started with the ‘cyclic assumption’ because we assumed that for large values of N, the average number of blocks of a ‘regular’ row and a cyclic one will converge. It’s also important to mention that for the original purpose of this problem, we want to divide the square into a fairly dense grid (N~100 at least).

Let’s run some tests to verify that the assumption holds for rows and grids. If you want, you can continue running the python notebook to get the following graphs. Notice that the grid simulation might take some time…

Verify the Cyclic Assumption for a Row

The python code iterates over values of N (from 5 to 250) and for every one, iterates over all p’s and averages the total number of blocks (\( B_N \)) for 50 iterations. It does it twice. Once with the RegularRow object and the other with CyclicRow. The average absolute difference between them is divided by N to normalize the results. We basically get the error in % by N.

It’s less than 1% for large N’s which is completely acceptable for my problem.

Verify the Cyclic Assumption for a Grid

More or less the same, only now the two classes being compared are StraightGrid and CyclicGrid. The error is normalized by N squared (number of cells). Notice that N’s are much smaller this time, just because grids are heavier to compute (for many N’s, many p’s and many iterations…). You can run it for larger N’s. I felt it’s enough as it is.

We’ve shown that both for a row, and for a grid, the cyclic assumption doesn’t affect the estimator much when we are dealing with large N’s.

Write the Expression for a Cyclic Grid

Just to recap, we already have the following expressions:

• The expected number blocks in a row for every size of a block - \( E_N(k) \), where k is the block size
• The expected total number of blocks in a row - \( B_N \)

All expressions are by N and p.

In the previous section we’ve looked at the bias we have in the model (we’ve built it for a cyclic row although our rows are actually regular ones) and we are fairly satisfied with it.

We want to do the same for a 2D grid. First, like before, we’ll reduce the problem to a cyclic grid. It had worked once, and we saw it’s safe to use even for grids, so why not try this again?

For simplicity, we’ll assume that all blocks have some sort of a ‘base row’ of an arbitrary length and every cell in that row is a part of a column of an arbitrary length. Our block size is then the summation of all columns sizes.

Obviously this is very simplistic and doesn’t cover all cases. I prefer using this assumption because although here I do expect to see a difference between the actual performance and the estimator for a block’s size, I hope that for large p’s it will be acceptable. The rational is that if p is close to 1.0, most separators are in place and we are less likely to get to ‘crazy’ blocks that doesn’t fit this model.

Don’t get me wrong. This assumption is way weaker than the cyclic one and will almost certainly add bias to our estimator. We use it because without it it would have been a combinatorical nightmare to deal with all possible block’s sizes (and because it’s late and I want to go to sleep..).