Solving Tangrams Using JTS

The project, 2dfit, solves Tangram puzzles using the Java Topology Suite (JTS). The algorithm implementation is based on what I outlined in item 3 of the post “
http://bloggingmath.wordpress.com/2007/05/28/tangram-puzzle/
“.

The implementation difficulties are from using floating point arithmetic, which is not robust for geometric operations. The JTS library attempts to minimize this by a coordinate snapping technique. But for the operations used in solving Tangrams the provided snapping was not sufficient.

There’s an option in JTS to specify the snapping tolerance (it has a fairly small default). I added small wrapper functions for the two operations of Boolean intersection and Boolean difference. The wrapper functions apply successively larger snapping tolerances up to a factor of epsilon, where epsilon = 1e-5. The below code shows the wrapper functions (in the code, g1 is the Tangram and g2 is a puzzle piece).

    public static Geometry SemiRobustGeoOp(Geometry g1, Geometry g2, int op) throws Exception {
        double e1 = EPSILON/10;
        double snapTolerance = GeometrySnapper.computeOverlaySnapTolerance(g1, g2);
        while (snapTolerance < e1) {
            try {
                Geometry[] geos = GeometrySnapper.snap(g1, g2, snapTolerance);
                switch (op) {                    
                case DIF_OP:   // difference
                    return geos[0].difference(geos[1]);
                case UNION_OP: // union
                    return geos[0].union(geos[1]);
                default:
                    throw new Exception("unhandled semirobustgeoop: " + op);
                }
            } catch (TopologyException e){
                snapTolerance *= 2;
            }
        }
        return null;
    }

    public static boolean SemiRobustGeoPred(Geometry g1, Geometry g2, int pred) throws Exception {
        double e1 = EPSILON/10;
        double snapTolerance = GeometrySnapper.computeOverlaySnapTolerance(g1, g2);
        while (snapTolerance < e1) {
            try {
                Geometry[] geos = GeometrySnapper.snap(g1, g2, snapTolerance);
                switch (pred) {                    
                case COVER_PRED: // 
                    return geos[0].covers(geos[1]);
                default:
                    throw new Exception("unhandled semirobustgeopred: " + pred);
                }
            } catch (TopologyException e){
                snapTolerance *= 2;
            }
        }
        return false;
    }

Using the wrapper functions was key to a more robust implementation. The below figure shows a solved Tangram puzzle (from Test.java:FitTest_ToSingleLargeTriangle()), in the figure the puzzle pieces are labeled l1.dat, l2.dat,…, l7.dat (I was lazy in naming the files). It’s the result of running FitTest_ToSingleLargeTriange() in Test.java and plotting the result using gnuplot.

I used the symmetry of each puzzle piece and a heuristic for choosing which puzzle piece to fit in reducing the number of permutations used for solving a Tangram.

For the puzzle piece symmetry, I used that the square is completely symmetric so only its first line segment needs to be used when fitting it. The triangle pieces are only partially symmetric so two of their three line segments need to be tried.

The below figure illustrates the symmetry of the square:

I used two heuristics for which pieces to try fitting, first try larger pieces before smaller ones and two skip a piece if another identical piece has already failed to be fitted (there are two identical small triangles and similarly two identical large triangles).

With the above two optimizations it takes ~1min to solve a Tangram. Without the optimizations the algorithm did not complete for the Tangrams I tried.

Quick Heuristic For Tangram Polygon Intersection

For the combinatorial approach to solving Tangram puzzles one frequent operation is to test if a puzzle piece, , is contained in the silhouette . Before this test is made the puzzle piece, , is translated to a vertex, , of and one of the edges of is aligned with an edge, coming out of vertex

For clarity I’ve included a figure below illustrating this.

In the above figure it’s obvious that the puzzle piece, , does not fit in the silhouette. One way to see this computationally is to look at the edge, , and notice that at vertex, , the next edge of the silhouette, makes a left turn with respect to the edge . This means that if the length of is less than the length of all the edges in then there is no possible way to fit in That is as long as we have the condition that one of the edges of is aligned with the edge of .

The above statement provides a quick way to skip vertices of the silhouette when trying to fit the puzzle piece in the silhouette Of course before skipping the vertex the same test needs to be done on the other edge coming out of Also we note that the above test only works if the next edge coming out of makes a left turn with respect to the edge otherwise the full test for polygon intersection has to be run. Also if one of the edges of the puzzle piece has length less than or equal to the length of then the full test for polygon intersection has to be run.

In summary this is a very specific heuristic that in general isn’t very useful but if you ever find yourself needing it, it can be just what the doctor ordered.

A Heuristic Solution to the Tangram Puzzle

In this post I present a short summary of the paper “A Heuristic Solution to the Tangram Puzzle” by E.S. Deutsch and K. C. Hayes Jr. I’ve uploaded a scanned copy of the paper to scribd here. Uploading the scanned copy probably violates some copyright law so if they or anyone else contacts me I’ll remove the document. Ironically it’s taken me over two-years since my post here to finally read the paper.

In their paper they talk about two possible approaches to solving tangrams. One is the combinatorial approach that I’ve taken and the other is the heuristic method that they describe in their paper. The heuristic method that they use is a little clever, what they do is take the outline of the tangram puzzle and then try to break it out into sub-puzzles. The following figure illustrates where two puzzles have both been separated out into sub-puzzles. In both cases one of the sub-puzzles exactly matches a tangram piece thus allowing the algorithm to solve that sub-puzzle.

The dashed lines in the figure show where the algorithm is splitting the sub-puzzles out from the original puzzle. First note that the dashed lines are called “extension lines” in the paper. They are generated to allow the extraction of the sub-puzzles. To create the extension lines the algorithm goes along the outline of the puzzle and at convex corners it generates an “extension line” that allows the possible separation of the puzzle into sub-puzzles. The following figure illustrates this. In the paper they outline various ways for eliminating extension lines that are unlikely to be of use.

Once the above extension lines are created there is a set of heuristics for splitting out sub-puzzles, the heuristics are used in the following order.

1. direct-match rule
The algorithm attempts to locate puzzle pieces fully described by edges, rather than by extension lines or by combinations of edges and extension lines.

2. 2 1/2 – 3 1/2 edge-match rule
The direct-match rule while being very reliable in finding matches cannot be used in most cases this means that a more relaxed rule is needed. The 2 1/2 – 3 1/2 edge-match rule allows the location of puzzle pieces where most of the periphery is described by edges and a small portion is described by extension lines. Specifically the “2 1/2 – 3 1/2 edge-match rules requires that in the case of triangular shapes two complete sides must be defined by edges and the remaining side can be defined by a combination of collinear edges and extension lines. Moreover, the combination must include at least one portion of edge. For four sided puzzle pieces the rule requires that the additional side also be fully described by an edge.” [1]

There are an additional 8 extraction rules that are used but the above two give you their general flavor.

The organization of the extraction rules is to run them recursively and at each step try to apply the most specific one possible first. If the algorithm gets to a step where there are no possible extractions it backtracks and tries another extraction rule. This process is not guaranteed to find a solution and in fact the paper gives an example of a puzzle on page 239 for which no solution is found.

The paper is a niece example of where a little clever thinking and some very specific heuristics can solve tangram puzzles.

References

[1] Deutsch, E. S., and K. C. Hayes Jr. “A Heuristic Solution to the Tangram Puzzle”, Machine Intelligence vol. 7, 1972, p. 205–240.

Solving Tangrams Using the Java Topology Suite (jts)

I’ve been using the Java Topology Suite (jts) to try and solve the Tangram puzzle. The basic algorithm is the same as I posted previously (it’s item 3 on the list of algorithms). The JTS is much easer to use and the source code is actually readable compared to CGAL. But on the downside JTS does not enforce rigorous geometry like CGAL does. This has some downsides mainly I had to modify the basic algorithm for shape fitting.

The main issue is that when trying to fit for example a triangle, , inside another polygon say . We can have roundoff errors such as in the following image.

One slightly add-hoc way to solve this issue is to multiply by a scaling factor where epsilon is a small constant. Then when subtracting the new triangle from we won’t have the issue of a small corner of being left over. But it does mean that we subtract slightly too much area from . Which could cause an issue when we try to fit say another triangle, , inside of (e.g. won’t fit). To ensure fits what we can do is create a buffer of size #pieces around before testing if is inside of . Please note that #pieces is the number of for instance triangles we’re trying to fit inside of (so in this case #pieces = 2 since we’re trying to fit and inside of ). With the addition of the buffer even if is slightly too small the union of and its buffer will be large enough to cover . I’ve had pretty good luck using this method with the JTS library.

You can see my code at the GitHub 2dfit site.

But a new problem is that solving the tangram puzzle takes a really long time since the algorithm goes through a large number of possible solutions before finding the correct one. Even after using the heuristic of fitting the largest shapes first the algorithm still takes a lot of time (in fact I’m still waiting for it to complete while writing this post). So I’ve been thinking of possible ways to speed up the algorithm. Below I’ve listed an algorithm that might be of some help in this.

Given two simple polygons called the silhouette and the puzzle piece. What we want is the algorithm to have two possible outcomes (1) it says “does not fit” in which case the puzzle piece cannot possible fit inside the silhouette and (2) “don’t know” in which case the puzzle piece could possible fit inside the silhouette but it’s also possible that it does not fit inside the silhouette.

In the below image I’ve shown the puzzle piece, , which is a square and the silhouette, , which is a simple polygon.

One way to determine that the puzzle piece, p, won’t fit is to start by constructing a bounding circle around it. As in the following figure.

What we do is calculate the %area of the circle filled by the puzzle piece (in this case a square). I’ve done the calculation and it’s Now suppose we wanted to test if the
square would not fit in the silhouette, . Now also suppose that we try putting the bounding circle that we used for the square on the silhouette, as in the following figure.

As is obvious the area of the bounding circle filled by the silhouette, is much less than . Infact if we tried all possible placements of the bounding circle on the silhouette, we would find that the %area of the bounding circle filled by the silhouette is always less than This implies that the square cannot fit inside the silhouette, . Now we need to determine what placements to use of the bounding circle to let us conclude that there is no possible placement that would give an %area of filled by the silhouette .