share
MathematicaHow can I calculate a jigsaw puzzle cut path?
[+60] [2] Mr.Wizard
[2012-06-12 06:19:41]
[ computational-geometry puzzle ]
[ https://mathematica.stackexchange.com/questions/6706/how-can-i-calculate-a-jigsaw-puzzle-cut-path ]

I want to generate a path to cut an arbitrary shape into a set of jigsaw puzzle pieces.

  1. All pieces must be unique to preclude placing a piece in the wrong spot.
  2. Pieces must be interlocking such that each piece is held by adjacent pieces.
  3. It must be possible to generate different paths (sets) for a specific shape that are not merely rotations or reflections of the first.

Since jigsaw puzzles are mass produced there must be a known solution. However, my interest is not in simply implementing this solution, rather I am curious to know how one might approach this task, aided by Mathematica. I am also interested in alternatives to the standard puzzle piece [1] such as these (even if pieces are not 100% interlocking):

jigsaw puzzles

Great question. Jigsaw puzzles can be with or without picture. Did you intend to make pieces unique purely by shape of the boundary or boundaries can by repetitive and uniqueness is also set by the pieces image or color? - Vitaliy Kaurov
@Vitaliy my intent is to have unique shapes which may or may not be overlaid with an image; a solid-color puzzle should have a single solution. - Mr.Wizard
I'd first partition the puzzle into polygons, then shaping those little "tongues" that interlock them. Are you interested mostly in the partitioning part or making the shapes interlock? Partitioning into rectangles then distorting the rectangles a bit and adding "tongues" to them (I really can't find a good English word for these!) would be the easiest, but also a bit boring. - Szabolcs
@Szabolcs both, really; the tongues (sounds reasonable) need to be unique shapes as they are often what determines whether or not a piece fits. That adds to the complexity. Also, there is a question of "how unique" a piece is; if we apply a random distortion I do not think we are guaranteed to have a "highly unique" piece, meaning there is a chance we create pieces which someone could force into place incorrectly. - Mr.Wizard
Another idea is starting with a mesh generator program used for finite element modelling. The IMTEK Mathematica Supplement seems to have an interface for the EasyMesh mesh generator. I have not used this before though. It could make meshes similar to e.g. this one: cs.cmu.edu/~quake/spiral.ele.a.2.gif - Szabolcs
@Szabolcs that's an interesting idea. That may not be ideal as the meshes I've seen have widely varying segment sizes, and while I didn't specify a uniform piece size I am aiming for practicality, and they couldn't be too far off. - Mr.Wizard
How about this as a starting point? (Ignore the edges, I know they're not good.) I took this post (this is a good and fast answer) and looked at the Delaunay triangulation and Voronoi diagram of the points. What I linked is the Voronoi diagram, cropped to the relevant region. About the mesh generators: I think they can be adjusted to give a rather uniform size (...) - Szabolcs
(...) take a look for example at Triangle. If you have a nice and convex outline and specify an area constraint, then it'll give quite uniform pieces. It seems though that there might still be a factor of 2 between the areas of the smallest and largest triangles, which might be too much. - Szabolcs
Generally, Voronoi diagrams might be a good way. You could even start with a regular point grid (rectangular, triangular or hexagonal), then "shake" the points a bit to introduce distortion. Then compute the Voronoi diagram. (EDIT: Oh, I just notice you already discussed this with Vitaliy) - Szabolcs
@Szabolcs why don't you post that series of comments as an answer? You can expand it later if you find a way to make the tongues. - Mr.Wizard
(1) There is a guy, Sam Savage, that produces puzzles based on Escher patterns: shmuzzles.com/shmuzzle_resources.htm - berniethejet
[+46] [2012-06-12 07:17:34] Vitaliy Kaurov [ACCEPTED]

======= Update =========

Great question! It inspired this Wolfram Blog article [1] and includes most of the code below plus some apps and fractal layouts like this:

enter image description here

I think it make sense to keep the older code blow for archival and historic purposes.

======= Older implementation =========

Excellent motivating creativity question. This is a bit big for a comment, so here are a few thoughts.

==== Voronoi practical implementation ====

Let's start from writing the following function:

bsc[p1_, p2_] := 
 With[{rc = RandomChoice[{-1, 1}], d = EuclideanDistance[p1, p2], 
   pm = (p1 + p2)/2, dp = (p2 - p1)/5},
  If[d < .1,
   Line[{p1, p2}],
   BSplineCurve[{p1, pm, pm - dp + rc {1, -1} Reverse[dp], 
     pm + dp + rc {1, -1} Reverse[dp], pm, p2}, 
    SplineWeights -> {1, 5, 5, 5, 5, 1}/22]
   ]]

which will morph a long enoug line into a line with a "tongue". It will put the tongue in a random direction for more random generation of puzzle pieces. And some comparison function that will show what points we are adding to wrap BSplineCurve around. 

f[p1_, p2_] := 
 With[{d = EuclideanDistance[p1, p2], pm = (p1 + p2)/2, 
   dp = (p2 - p1)/5},
  If[d < .1,
   Line[{p1, p2}],
   Line[{p1, pm, pm - dp + {1, -1} Reverse[dp], 
     pm + dp + {1, -1} Reverse[dp], pm, p2}]
   ]]

Here is a Manipulate to test it out:

Manipulate[
 Graphics[{f @@ pt, {Red, Thick, bsc @@ pt}}, ImageSize -> {300, 300},
   Axes -> True, Frame -> True, AspectRatio -> 1, 
  PlotRange -> {{0, 1}, {0, 1}}], {{pt, {{0, 0}, {1, 1}}}, Locator}, 
 FrameMargins -> 0]

enter image description here

Now this will create a simple Voronoi diagram:

gr = ListDensityPlot[RandomReal[{}, {35, 3}], InterpolationOrder -> 0,
   Mesh -> All, Frame -> False]

enter image description here

And this will extract lines out of it and replace long enoug lines with our tongues function:

Graphics[bsc @@@ 
  Union[Sort /@ 
    Flatten[Partition[#, 2, 1] & /@ 
      Map[gr[[1, 1, #]] &, 
       Flatten[Cases[gr, Polygon[_], Infinity][[All, 1]], 1]], 1]]]

enter image description here

This can be superimposed on an image or simply colorized (with added outer frame):

MorphologicalComponents[
  Binarize@Graphics[{Thick, 
     bsc @@@ Union[
       Sort /@ Flatten[
         Partition[#, 2, 1] & /@ 
          Map[gr[[1, 1, #]] &, 
           Flatten[Cases[gr, Polygon[_], Infinity][[All, 1]], 1]], 
         1]]}, Frame -> True, FrameTicks -> False, 
    PlotRangePadding -> 0, FrameStyle -> Thick]] // Colorize

enter image description here

You have to execute code a few times to find best random colorization - it is based on random tongue orientation.

=== Yet another way - Hilbert & Moore curves====

I slightly modified this Demonstration [11] and cut resulting curves with grid lines:

LSystem[axiom_, rules_List, n_Integer?NonNegative, False] := 
  LSystem[axiom, rules, n, False] = 
   Nest[StringReplace[#, rules] &, axiom, n];
LSystem[axiom_, rules_List, n_Integer?NonNegative, True] := 
  LSystem[axiom, rules, n, True] = 
   NestList[StringReplace[#, rules] &, axiom, n];
LSeed["Hilbert curve"] = "+RF-LFL-FR+"; 
LSeed["Moore curve"] = "+LFL+F+LFL-";
LRules["Hilbert curve"] = {"L" -> "+RF-LFL-FR+", 
  "R" -> "-LF+RFR+FL-"}; 
LRules["Moore curve"] = {"L" -> "-RF+LFL+FR-", "R" -> "+LF-RFR-FL+"};
LPoints[lstring_String] := 
  LPoints[lstring] = Map[First, Split[Chop[Map[First,
       FoldList[Function[{pta, c},
         Switch[c,
          "+", {pta[[1]], pta[[2]] + 90 Degree},
          "-", {pta[[1]], pta[[2]] - 90 Degree},

          "F", {{pta[[1]][[1]] + Cos[pta[[2]]], 
            pta[[1]][[2]] + Sin[pta[[2]]]}, pta[[2]]},
          _, pta]],
        {{0, 0}, 0.},
        Characters[lstring]]]]]];
LPoints[lstring_String, level_Integer?NonNegative] := 
  Map[(2^(5 - level)*# + ((2^(5 - level) - 1)/2)) &, LPoints[lstring]];
LLine[lstring_String, 
   level_Integer?NonNegative] := {AbsoluteThickness[2*(5 - level)], 
   BSplineCurve[LPoints[lstring, level]]};
Manipulate[
 MorphologicalComponents[
   Binarize@Graphics[If[showPreviousLevels == False,
      LLine[
       LSystem[LSeed[whichcurve], LRules[whichcurve], n - 1, 
        showPreviousLevels], n], 
      MapIndexed[LLine[#1, First[#2]] &, 
       LSystem[LSeed[whichcurve], LRules[whichcurve], n - 1, True]]], 
     GridLinesStyle -> Directive[Thick, Black], FrameStyle -> Thick, 
     GridLines -> {None, Table[x, {x, 4, 30, 4}]}, Frame -> True, 
     FrameTicks -> False, PlotRangePadding -> 0]] // Colorize
 , {{n, 4}, 
  ControlType -> None}, {{whichcurve, "Hilbert curve", 
   ""}, {"Hilbert curve", "Moore curve"}, 
  ControlType -> RadioButtonBar}, {{showPreviousLevels, False}, 
  ControlType -> None}, SaveDefinitions -> True]

enter image description here

[1] http://blog.wolfram.com/2012/06/28/designing-jigsaw-puzzles-with-mathematica/
[2] http://demonstrations.wolfram.com/topic.html?topic=Tiling
[3] http://demonstrations.wolfram.com/RobinsonTiling/
[4] http://demonstrations.wolfram.com/PenroseTiles/
[5] http://demonstrations.wolfram.com/PinwheelTiling/
[6] http://demonstrations.wolfram.com/AmmannTiles/
[7] http://demonstrations.wolfram.com/PentagonTilings/
[8] http://demonstrations.wolfram.com/VoronoiImage/
[9] http://demonstrations.wolfram.com/NeatAlternatingTilingsOfThePlane/
[10] http://demonstrations.wolfram.com/NowhereNeatTilingsOfThePlanePart2/
[11] http://demonstrations.wolfram.com/HilbertAndMooreFractalCurves/

Thanks for answering. It did occur to me to create a Voronoi segmentation and then perturb the edge into something interlocking. Most of the tilings are problematic however in that they specifically have repeating shapes which I am expressly trying to avoid. - Mr.Wizard
@Mr.Wizard Agreed, Voronoi is a good candidate for morphing. In relation to other tilings - this is why I asked about the cover image. I thought with small set of pieces image/color/pattern will make them unique. But I see you are trying to go in the opposite direction - towards unique boundaries. - Vitaliy Kaurov
f is not defined in the first manipulate and there are some problems on the edges, but otherwise a great big +1! - Ajasja
Vitaliy, I am sitting back and enjoying the show; thank you. However, doesn't the last example have a lot of pieces of the exact same shape? There would be many different solutions to the puzzle as shown. - Mr.Wizard
@Mr.Wizard this is indeed correct and uniqueness can be granted by clever cutting. This should be proper "dashed" lines I think. I just truly have no more time and hoping you guys can take it form here. Just wanted to show the idea of these beautiful Hilbert and Moore curves. Thanks for comments! - Vitaliy Kaurov
(5) Vitaliy, you get much sleep last night? (Apparently not, given when the response was posted.) - Daniel Lichtblau
(1) @DanielLichtblau Sleepcoding ;-) - Vitaliy Kaurov
@Ajasja Thanks! I fixed f. - Vitaliy Kaurov
Nice answer, nice blogpost and nice question! Congratulations for everyone! - István Zachar
I am honored that my question inspired such a fine answer and Blog post! Thank you Vitaliy. - Mr.Wizard
let us continue this discussion in chat - Vitaliy Kaurov
Could someone explain what rc {1, -1} Reverse[dp] is doing in the sample above? Not a Mathematica guy but it most of it makes sense except how these are they interacting. I see no operators to link them together. - RiverHeart
1
[+22] [2012-06-12 08:53:53] Szabolcs

The first part of the problem is partitioning a shape into smaller parts of a roughly equal area. Then we can add little "tongues" on the pieces to make them interlock.

One idea for partitioning is using either a Delaunay triangulation of a set of points (for triangular pieces) or a Voronoi tessellation (for many-sided polygons).

Let's take for example this method [1] of generating a set of random points with a minimum distance. I modified the algorithm a little to squeeze as many points into a region as possible:

canvas = Image@ConstantArray[0, {100, 100}];
distance = 15;

{img, {pts}} = Reap[
   NestWhile[
    ImageCompose[#, SetAlphaChannel[#, #] &@Image@DiskMatrix[distance],
      Sow@RandomChoice@Position[
         Transpose@ImageData[#, DataReversed -> True], 0.]] &,
    canvas,
    Count[Flatten@ImageData@Binarize[#], 0] > 0 &]];

Then the Delaunay triangulation looks like this:

<<ComputationalGeometry`
PlanarGraphPlot[pts, LabelPoints -> False]

(For a better result we'd need to add points from the edges.)

The Voronoi tessellation looks like this:

Show[DiagramPlot[pts], PlotRange -> 100 {{0, 1}, {0, 1}}]

It can also be shown with ListDensityPlot:

showTiles[pts_] := 
 ListDensityPlot[ArrayPad[pts, {{0, 0}, {0, 1}}], Mesh -> All, 
  InterpolationOrder -> 0, Frame -> False, ColorFunction -> (White &)]

showTiles[pts]

Mathematica graphics

Another possibility is to start with a regular grid of points (e.g. a hexagonal grid),

hex = Join @@ Table[{x, Sqrt[3] y}, {x, 0, 4}, {y, 0, 2}];
pts = Join[hex, TranslationTransform[{1/2, Sqrt[3]/2}] /@ hex];

showTiles[pts]

and distort it randomly:

pts = RandomReal[0.1 {-1, 1}, Dimensions[pts]] + pts;
showTiles[pts]

Mathematica graphics

Just for some fun, we can actually create the tiles and shuffle them a bit. Who wants to add some code to make them draggable and rotatable?

Graphics[
 {EdgeForm[Black],
  Texture@ExampleData[{"TestImage", "Sailboat"}], 

  GeometricTransformation[#, 
     Composition[
      TranslationTransform@RandomReal[0.1 {-1, 1}, 2], 
      RotationTransform[RandomReal[{-Pi, Pi}], Mean@First[#]]]] & /@ 
   Cases[Normal@showTiles[Rescale[pts]], 
    Polygon[p_, ___] :> Polygon[p, VertexTextureCoordinates -> p], 
    Infinity]}
 ]

Mathematica graphics

[1] https://mathematica.stackexchange.com/questions/2594/efficient-way-to-generate-random-points-with-a-predefined-lower-bound-on-their-p/2606#2606

It is already draggable and rotateable I guess. Slightly easier if one adds the option ContentSelectable -> True. It would be nice to prevent stretching though. Nice one +1 - Rojo
Your code needs to be updated to accommodate the new version (such as 12.0). - A little mouse on the pampas
2