# Algorithm to generate random shapes that fill up a rectangle?

The final result can be like this

I've thought up several approaches:

1. Generate random curved lines to "cut" the rectangle (or generate random dots and form the line from the dots)

2. Break the rectangle with Fracture Voronoi algorithm and shrink the broken parts to make the curved lines thicker.

3. Generate random shapes and let it fall into the rectangle like the game Tetris

But before implement the ideas, I want to know if there is an algorithm (with pseudo code) to generate random shapes that fill up a rectangle?

• All three techniques you just described are algorithms for solving this problem. Is there something about them you're unsatisfied with? What should a proposed answer do differently to be judged as a "correct" solution? Jun 18 '18 at 12:02
• @DMGregory: the 3 techniques above I'm just afraid that they are not professional enough. I just wonder if this problem has been solved with an algorithm by expert (for example:BFS/DFS algorithm is used to solve path finding), but if there isn't, I think I'll implement 1 of the 3 ideas above. Jun 19 '18 at 3:09
• To get a "professional" answer you'd need very precise optimality conditions, which might not apply here. If what you're looking for is "something that kinda looks like this" then any method that gets you a result that looks the way you want (without spending the age of the universe computing it) is a pretty good solution. ;) Jun 19 '18 at 3:11
• @DMGregory: Thanks for your help, I understand now :) Jun 19 '18 at 3:14

## 1 Answer

Did you check Fortune's algorithm?

Here is the Pseudocode from Wikipedia (sorry, in the Pseudocode has images, so I can't copy it as text but I can only capture the image)

You can find some people share their implementation on GitHub (for example: C++ implementation of Fortune's Algorithm)

• This is currently a link only answer. Can you edit it in order that we would not need to rely on the external source to understand what's the actual solution? Jun 19 '18 at 13:49
• Thank @AlexandreVaillancourt, I've added the Pseudocode. Jun 19 '18 at 13:59