manually cutting a picture

[Amit Khemka]

On 11/6/07, Joseph king <king.a.joe at gmail.com> wrote:
> I have a kinda hard question.... i am trying to build a jigsaw game with
> python, i would like to give the option for people to create there own
> puzzle piece.... does anyone know how to accomplish this it is becoming
> increasingly difficult for me

Disclaimer: I don't know how helpful I am being here. I have no
experience with jigsaw puzzles programming, but the problem seemed
interesting enough to give it a thought.

I think given an image (may be user provided) you want to cut it in N
(user input) pieces.

Here is an idea:

Cut image by "m X m" grid (bigger the m, the more varied shapes you
would be able to generate), this will give you m*m square pieces. With
each piece store a vector which represents the polygon (say by storing
co-ordinates of the corners).
Now visualize this set of pieces as a graph with an edge between
adjacent pieces. Now depending on the final number of pieces that you
want to generate (N), you traverse the graph and for each node:

1. "Merge" a node with a randomly selected neighbor

Repeat step 1 until you have N pieces left

Notes:
1. ''merge" operations can be optimized calculating a factor "m*m/N"
and doing all merges together.
2. You can also maintain a 'size' attribute with each piece, so that
all the pieces generated are of approximately same size.

Please let me know if you have other ideas.

Cheers,
-- 
--
Amit Khemka