37
$\begingroup$

I have five DXF files with various geometric figures.

enter image description here

Are squares with a different geometric shape in each DXF file...

Four DXF files have a square with a different geometric shape on one side while one DXF file on each side have a different geometric shape, as shown above.

(DXF1,DXF2,DXF3,DXF4,DXF5)

  1. It is possible join these 5 files?

enter image description here

  1. Some files are in the wrong position to be mounted. It is possible to rotate them?

  2. It is possible to create a code that can recognize these geometries and make some assembly like this? The animation is only illustrative. It was created only to facilitate understanding

Animated gif

An attempt was made to convert the files above into 2D BoundaryMeshRegions, and these can be imported via:

meshes = << "http://pastebin.com/raw/zNxS87RP"
$\endgroup$
  • 1
    $\begingroup$ Forget about the animation, it isn't necessary to state the question. Also, a better title might be "Can MMA put these puzzle pieces together". Finally, you should try to convert these files into 2D BoundaryMeshRegions first to make this easier. $\endgroup$ – Jason B. Aug 15 '16 at 21:01
  • $\begingroup$ Why are the MeshRegions in 3D? $\endgroup$ – Feyre Aug 15 '16 at 21:05
  • 1
    $\begingroup$ @LeandroMacieldeCarvalho - Hope you don't mind the edits, I think this is an interesting problem $\endgroup$ – Jason B. Aug 15 '16 at 22:34
  • 3
    $\begingroup$ closely related: How to find alignments of interlocking shapes? $\endgroup$ – Kuba Aug 16 '16 at 9:42
  • 2
    $\begingroup$ @LeandroMacieldeCarvalho what do you mean? p.s. also closely related: Community: Programming approach to solving "One Tough Puzzle" $\endgroup$ – Kuba Aug 16 '16 at 9:51
30
$\begingroup$

Assuming polygons follow the same (clockwise or counterclockwise) vertex order, find all good quality two line segment rigid mappings between polygons without overlap with each other (at least much overlap, that is). Construct a graph of these mappings and apply appropriate transforms to polygons by finding transform paths from one polygon to all others. (In this case, these paths are pretty simple).

ReplaceList[MeshPrimitives[#, 2] & /@ meshes, {___,
    {a : Polygon[{___, ap : Repeated[_, {3}], ___}]}, ___,
    {b : Polygon[{___, bp : Repeated[_, {3}], ___}]}, ___} :>
   Module[{err, trans},
    {err, trans} = 
     Chop[FindGeometricTransform[{ap}, Reverse@{bp}, 
       TransformationClass -> "Rigid", Method -> "Linear"], 0.001];
    {Property[a \[DirectedEdge] b, "trans" -> trans],
      Property[b \[DirectedEdge] a, "trans" -> InverseFunction@trans]} /;
     err < 1 && 
      Quiet@Area[
         RegionIntersection[BoundaryDiscretizeRegion@a, 
          BoundaryDiscretizeRegion@TransformedRegion[b, trans]]] < 1]] //
 With[{g = Graph@Flatten@#},
   Graphics[{FaceForm[], EdgeForm@Thick, First@VertexList@g,
     GeometricTransformation[#,
        Composition @@ (PropertyValue[{g, DirectedEdge @@ #}, "trans"] & /@ 
           Partition[FindShortestPath[g, First@VertexList@g, #], 2, 1])] & /@
      Rest@VertexList@g}]] &

enter image description here

$\endgroup$
  • 2
    $\begingroup$ such a neat approach...learned a lot from just cursory look +1 :) $\endgroup$ – ubpdqn Aug 16 '16 at 11:04
22
$\begingroup$

For a different approach with image processing, I start with the image of your puzzle.

fig = Import["http://i.stack.imgur.com/xpue6m.jpg"];
comp = MorphologicalComponents[fig // Binarize];
comp = Colorize[comp, ColorFunction -> "Rainbow"];
cols = DominantColors[comp, 20];
blocks = ColorNegate[Binarize@ColorReplace[comp,
         Cases[cols, Except[cols[[#]]]], .01]] & /@Range[10];
pieces = blocks[[{1, 6, 7, 8, 9}]] 

enter image description here

Now I have my puzzle pieces, I can try to match them. First I fix the centrepiece and try to match other

cen = pieces[[1]];

Now I want to see where does the second piece go. So I use ImageCorrespondingPoints.

n=2

i1 = cen; i2 = pieces[[2]];
matches = ImageCorrespondingPoints[i1, i2 // ColorNegate];
Show[i1, Graphics[{Red, PointSize[Large], Point[matches[[1]]]}]]
Show[i2, Graphics[{Red, PointSize[Large], Point[matches[[2]]]}]]

enter image description here

The red dots show the corresponding points in each piece. Similarly, you can check the other pieces.

You can crop the images if you want, but make sure the image size remain compatible.

$\endgroup$
  • $\begingroup$ Amazing. Very cool. $\endgroup$ – LCarvalho Dec 23 '17 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.