# manually cutting a picture

Cameron Walsh cameron.walsh at gmail.com
Wed Nov 7 14:27:45 CET 2007

```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.

```