1
\$\begingroup\$

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?

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

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)

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.