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? 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. Let me know how it goes, it sounds like a fun problem. Cameron. -- http://mail.python.org/mailman/listinfo/python-list
