manually cutting a picture

[Cameron Walsh]

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.