# Quick Heuristic For Tangram Polygon Intersection

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

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

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

The above statement provides a quick way to skip vertices of the silhouette $s$ when trying to fit the puzzle piece $p$ in the silhouette $s.$ Of course before skipping the vertex the same test needs to be done on the other edge coming out of $v.$ Also we note that the above test only works if the next edge coming out of $v_1$ makes a left turn with respect to the edge $e,$ otherwise the full test for polygon intersection has to be run. Also if one of the edges of the puzzle piece $p$ has length less than or equal to the length of $e$ 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.