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.

### Like this:

Like Loading...