Message Boards Message Boards

Jigsaw Puzzle

enter image description here

Dear all, from the resemblance of a Voronoi mesh to a jigsaw puzzle I came to the idea for the following little program I want to share. The essential function is

(* in: points p1, p2;
  out: BSplineCurve = jigsaw side if distance > minLength;  *)
jigsawSide[minLength_][pts : {p1_, p2_}] := Module[{m, u, o, vx, vy, n, dist, r, c, angle0, cPts},
  dist = EuclideanDistance @@ pts;
  If[dist < minLength, Return[Line[pts]]];
  (* avoid borders: *)      
  If[Times @@ (p2 - p1) == 0, Return[Line[pts]]];
  m = Mean[pts];
  {u, o} = SortBy[pts, Last];  (* lower/upper point *)
  {vx, vy} = o - u; 
  n = {vy, -vx};  (* normal vector *)
  r = .15 dist;  (* radius *)
  c = m + n/4.;  (* center *)
  angle0 = Sign[Last[n]] VectorAngle[{1, 0}, n];
  (* points on circle: *)
  cPts = c + r {Cos[angle0 + #], Sin[angle0 + #]} & /@ (60 \[Degree] {-2, -1, 0, 1, 2});
  Return[BSplineCurve[{u, m, Sequence @@ cPts, m, o}]]
  ]

which connects two points with a BSplineCurve having the typical elementary shape of a jigsaw puzzle. If the distance is too short then the connection becomes a straight line. The same happens if the points share the same x- or y-coordinate to exclude the jigsaws borders. Here is a simple test of the function:

enter image description here

Anything else is straightforward:

  • start with "randomized" lattice points;
  • from these a Voronoi mesh is created;
  • extract its polygons;
  • convert the polygon sides into the new (puzzle) shape;
  • build new polygons out of these sides;
  • apply a texture.

The result is a bunch of jigsaw pieces one can play with:

enter image description here

I was impressed by the consistent behavior of Texture. The whole (short) code is attached.

Best regards -- Henrik

Attachments:
POSTED BY: Henrik Schachner
9 Replies

@Henrik Schachner this is marvelous, thanks for sharing. Interestingly I had a similar idea visiting me a few years ago. Have you seen my blog post: Designing Jigsaw Puzzles with Mathematica ? For all details see the notebook attached at the end of the blogpost. The original idea came from my answer to this question. I bet the code design is different a bit, but I have not check this yet. A lot of things were added to Wolfram Language since 2012.

enter image description here enter image description here

enter image description here enter image description here

POSTED BY: Vitaliy Kaurov

A relevant neat article: GEODE, MAZE, AND CUSTOM JIGSAW PUZZLES. Some beautiful puzzles are made algorithmically. A very neat way to make locking pieces, which they also start from a Voronoi diagram.

enter image description here

enter image description here

enter image description here

enter image description here

POSTED BY: Vitaliy Kaurov

Wow - very inspiring! Thank you Vitaliy one more for this link! I think I need one of these lasers! Even though - lasers are hot, the jigsaw might melt:

img1 = Binarize@ColorNegate[Graphics[{EdgeForm[White], Black, jigsawPolygsRaw}, ImageSize -> Large]];
SkeletonTransform[img1] // Pruning[#, 40] & // InverseDistanceTransform

enter image description here

POSTED BY: Henrik Schachner

Dear Marco,

I am glad you like my little post! As usual you are trying the most challenging task! Somewhat inspired by this picture

img1 = Binarize@ColorNegate[Graphics[{EdgeForm[White], Black, jigsawPolygsRaw}, ImageSize -> Large]];
DistanceTransform[img1] // ImageAdjust

enter image description here

I was thinking about it but could not come up with a better idea than the most obvious: Making a binary function out of each piece (defined by its polygon)

polygToFunction[p_Polygon] := Module[{meanShift, region},
  meanShift = Mean @@ p;
  region = DiscretizeGraphics@Graphics[Map[# - meanShift &, p, {2}]];
  Return[Function[{pt}, Piecewise[{{1, pt \[Element] region}}]]]
  ]

adding them all up with specific translations, minimizing its integral ... Well, definitely not a good idea! It is probably a NP problem, one probably needs an heuristic algorithm (simulated annealing, genetic algorithm, ...). I am very curious about your solution!

Best regards -- Henrik

POSTED BY: Henrik Schachner

Dear @Vitaliy Kaurov,

thank you for this impressive hint! I particularly like the above animation! No, I did not know this, my little piece of code was just the result of a rainy weekend. I did not do any research whatsoever - maybe I should have done so ...

Best Regards -- Henrik

POSTED BY: Henrik Schachner

Dear Henrik,

that is fantastic! I have been playing for a while now to try and write something that helps solving the jigsaw. I have tried two approaches:

  1. Machine learning For each piece of the jigsaw I have tried to determine all the adjacent ones. Then I have tried to learn how to find fitting parts. The aim is to only find all adjacent pieces not to actually solve the jigsaw.

  2. Similar sections of boundaries I have also tried to detect similar sections of the boundaries using ImageCorners.

Neither of the approaches has worked. I hope to find some time tomorrow and come up with a new idea.

Thank you for posting,

Marco

POSTED BY: Marco Thiel

enter image description here - Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming!

POSTED BY: Moderation Team

Thank you very much !!!

POSTED BY: Henrik Schachner
Posted 6 years ago

This question have no a real answer for the second question still now. I don't sure your this tech can solve it eventually.

POSTED BY: Yode Japhe
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract