The final result can be like this

Random shapes fill a rectangle

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?

  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – DMGregory
    Jun 18, 2018 at 12:02
  • \$\begingroup\$ @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. \$\endgroup\$
    – 123iamking
    Jun 19, 2018 at 3:09
  • 1
    \$\begingroup\$ 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. ;) \$\endgroup\$
    – DMGregory
    Jun 19, 2018 at 3:11
  • \$\begingroup\$ @DMGregory: Thanks for your help, I understand now :) \$\endgroup\$
    – 123iamking
    Jun 19, 2018 at 3:14

1 Answer 1


Did you check Fortune's algorithm?

Fortune's algorithm animation

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) Pseudocode

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

  • \$\begingroup\$ 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? \$\endgroup\$
    – Vaillancourt
    Jun 19, 2018 at 13:49
  • \$\begingroup\$ Thank @AlexandreVaillancourt, I've added the Pseudocode. \$\endgroup\$
    – 123iamking
    Jun 19, 2018 at 13:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .