Message Boards Message Boards

GROUPS:
1876 Views
|
9 Replies
|
25 Total Likes
|

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:
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

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

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

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

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

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

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!

Thank you very much !!!

Posted 11 months 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.

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