# 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 &lt; 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(&quot;unhandled semirobustgeoop: &quot; + 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 &lt; e1) {
try {
Geometry[] geos = GeometrySnapper.snap(g1, g2, snapTolerance);
switch (pred) {
case COVER_PRED: //
return geos[0].covers(geos[1]);
default:
throw new Exception(&quot;unhandled semirobustgeopred: &quot; + 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.

# Reflection Symmetry

I’m interested in a method for determining if a simple polygon has reflection symmetry.

Let $r$ denote reflection about the y-axis and $\rho_\theta$ denote counter clockwise rotation by the angle $\theta$. Note that P has reflection symmetry iff $r \rho_\theta P = P$ for some angle $\theta$. We also know $r \rho_\theta = \rho_{-\theta} r$. Hence $r\rho_{\theta} P = \rho_{-\theta} r P = P$. Multiply both sides by $\rho_\theta$ to have $rP = \rho_{\theta} P$.

(1) Thus P has reflection symmetry iff $rP = \rho_{\theta}P$ for some angle $\theta$.

This simple fact enables a easy method to determine if P has reflection symmetry. Take a simple polygon P. First assume the centroid of P is the origin this is needed to ensure that a rotation about the x-axis is a rotation of P and not a rotation and translation of P.

From (1) we know that $rP = \rho_\theta P$ for some angle $\theta$. To determine $\theta$ we pick a vertex, v, of $P$. We know that v is rotated into some vertex w of $rP$. Hence we try rotating v into every vertex w of $rP$ until we get a match.