Jigsaw Puzzle

GROUPS:
 Henrik Schachner 15 Votes 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: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:I was impressed by the consistent behavior of Texture. The whole (short) code is attached.Best regards -- Henrik Attachments:
7 months ago
9 Replies
 Vitaliy Kaurov 3 Votes @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.
7 months ago
 Henrik Schachner 1 Vote 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
7 months ago
 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: 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. 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
7 months ago
 Henrik Schachner 2 Votes 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 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
7 months ago
 Vitaliy Kaurov 2 Votes 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.
7 months ago
 Henrik Schachner 2 Votes 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