How to divide an image into random sized parts?

[crono]

Hi,

I want to divide an image into random sized parts. I need this for some kind of puzzle game I'm writing with a friend. Dividing an image into even sized parts like this:

[attach=#1]

is not a problem at all. But how could I divide in into randomsized parts like this:

[attach=#2]

The algorithm I'm searching must be capeable of slicing any image in a variable amount (which is set by the player) of parts. The resulting images (parts) should not be smaller than X pixels and not larger than Y Pixels. The parts may not overlap each other. I have no idea how to do this.

[mouser]

a non-intuitive approach might work well ---
start by imagining a very large grid that divides the entire picture into a grid where each square is X by Y.
now simply REMOVE random edges until you have the desired # of pieces.

(note you'll have to do this a bit differently if you only want rectangular shapes pieces)

[crono]

Good idea Mouser But I think keeping track of only producing rect-shapes will be very tricky. I have to use only rect-shapes, because the puzzle will be jpg + javascript based, so there is no way to overlay other shaped images (because of the missing transparency). I think I will try to prototype this Idea on the weekend - Thanks

[Ampa]

How about the alternative aproach...

Code: (Pseudocode)

Begin with a single Slice (this will be the whole image)
Repeat until you have enough slices {
  Randomly choose a slice (check that it is not already too small to further divide)
  Randomly choos an orientation (vertical or horizontal)
  Divide the Slice it into two parts (this need not be two even parts)
}

This will always ensure you have rectangles.

[crono]

Thanks for your input Ampa. I came to the exact same methode while I was in the shower  It works very well 

[Silverchip]

It's probably not irrelevant but you could print, tear it to size desired then scan. I had to post it lol

[crono]

It's probably not irrelevant but you could print, tear it to size desired then scan. I had to post it lol

I will remember this if there is a table-top version of the game