On 11/7/07, Cameron Walsh <[EMAIL PROTECTED]> wrote: > Amit Khemka wrote: > > > 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 > > > Doesn't that have the fairly likely possibility of ending up with 1 very > large piece and n-1 very small pieces? If you iterate over the graph > merging with a neighbour at random, then each node has a 50% chance of > being merged with a node that has already been merged. > > *-*-* *-* > | | | > * *-*-* * > > * * * * * etc. could be the result of the first 8 steps. Already every > node touched is part of the same group. Or have I misunderstood your > algorithm?
Yes, It potentially can result into that. That is the reason I suggested to calculate (m*m/N) and while merging nodes keep track of the "size" (number of nodes are merged in a node), so that while growing/merging the node does not grow 'much large' than (m*m/M) > > A random region growing approach might work, with seeds scattered evenly > throughout the image. That would be prone to orphaning squares inside > larger objects, but that may be what you want. It would not be easy to > program. > > What I would do is break the graph in to m*m squares, then for each > edge, randomly select a means of joining them - blob sticking out of > piece A, or hole for blob in piece A; move hole/blob along the edge by a > random amount, move edge in or out to get different sized pieces. For > each square this was applied to, it would apply the reverse sizing to > the square touching on that edge. > > I'd restrict in/out movement of edges and movement of blob/hole along > the edge to a specific range, to avoid problems where the blob of one > square is stuck on the furthest corner, but the piece touching that > corner has had its edge moved in too far so the blob would overlap two > squares. Interesting idea, though the implementation may become a bit complex ! To OP : 1. Have you checked out research papers on Digital Image Processing and Graphics ? I would guess that there should exist some good solutions. I hadn't had much time but a quick search showed quite a few "free softwares" to create Jigsaw puzzles and Algorithms to solve one. 2. Can you please post anything relevant to this topic on this thread only instead of doing a new post. Helps to track the postings easily. Cheeers, -- -- Amit Khemka -- http://mail.python.org/mailman/listinfo/python-list