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.

puzzle piece and silhouette

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s