### Problem Description

Tangram
is a classic Chinese puzzle consisting of 7
pieces cut from a square - 5 triangles, a square and a parallelogram. The
object
is to reassemble them to form the original square, or any of 100's of other
shapes given only the outline of the final figure.

Tangram1 contained the basic graphic
processing to move and rotate figures. Here's the "final" version which actually
lets you solve Tangram puzzles.

### Background & Techniques

This is a Delphi version of an excellent freeware
Tangram program written by Dr. Mark Overmars and available from http://www.cs.ruu.nl/~markov/kids/
. If you just want to play
the game, I recommend that you download from the that site. This version
is not as complete ( Dr. Overmars version includes dozens of graded
outlines to solve, a Tangram Editor, and even a Help file!) . But his program is
available in executable form only, and I was curious about the code required. As
usual, it has been a fun learning experience.

Tangram1 contained the basic
graphic processing code to draw, drag and rotate the pieces. ** Tangram2 **
adds:

**Tangram1** assumed predefined shapes. I found later
that Overmars' version uses generalized polygons, some of which happen to be the
classic triangle, square and parallelogram shapes. I
decided to adopt this data structure to permit use of his set of figure
definitions for testing.** **The** Loadpieces **and **LoadFigSet**
procedures read files in Overmars' format. They are text files that
can be browsed and edited manually. Figure files (**.tan** extension)
contain the name of the associated pieces (**.pcs**) file. The main
problems were in figuring out how to scale the information for proper display -
largely a matter of trial and error. Also Overmars'
files assume counterclockwise rotation and may contain large and/or
negative numbers so it took a bit of manipulation to interpret rotation values properly.
A new ** TFigSet **class holds the figures file information as a **Figures**
array in **tTangram**. The **ShowFigures** method uses this
information to construct the **Solutions** array of pieces when a new figure
is selected. The **Solutions** pieces are marked as unmovable and
colored white.

The problem of drawing figure outlines still hasn't
been entirely solved (by me). I foolishly thought that the **Convex Hull **procedure
from Fences and Traveling Salesmen
would do, but of course, not all figures are
convex. My second attempt was to identify shared edges and delete them so
that the figure could be drawn by simply drawing the remaining
edges. This approach required identifying overlapping co-linear line
segments. (I finally had to solve this problem anyway for piece placement,
but that was after looking at the figure drawing problem. ) I
finally resorted to drawing the figure by drawing its figures in white with a
white pen. They look OK, but are not outlined as are
Overmars'. There are hull drawing algorithms which work for actual
hulls, concave as well as convex, but we'll leave that as an
enhancement.

The other major effort is in the **PieceInSolution**
function. It is called when the user clicks to drop a piece in the
figure section of the screen. In order to be dropped the piece must be
entirely contained in the figure outline and not overlap any previously placed
piece. Easy, right? Wrong! I hadn't appreciated
how complex geometrical shape processing can be, at least to a novice like
me. The **PointInPoly** function written last time to detect
mouse clicks helps identify where the vertices lie, but that's only part of the
story. A piece may have one or two vertices touching the edges of another
piece with no violation, but that gives no information about whether the
area of the piece is outside or inside of the other piece. I
finally decided that if pieces share 2 or more sides, they must
overlap. This restricts pieces to being convex polygons, i.e. no
indentations.

The solution identification problem was solved simply
by counting how many pieces had been placed successfully. When the placed
count matches the number of solution pieces, we must be done.

Finally, flipping the pieces also turned out to be not
bad. Flipping about either the horizontal or vertical axis (through
the piece center) can be accomplished by translating the point so
it's centered on that axis, reversing the sign of the point and translating back
to the original axis location. I.e., to translate point **(Px, Py)**
about the **Y** axis for a piece centered at** (Cx, Cy)**,
move the point to** (Px, Py-Cy)**, reverse its **Y** coordinate sign to **(Px,Cy-Py)**
and move it back to **(Px, Cy-Py+Cy)** or **(Px,2Cy-Py)**.
The **TPiece** method, **Flip, **does just this for all points in a piece
and seems to work fine. Note that the parallelogram is the only standard
piece that may require flipping.

**Addendum November 11, 2004: ** Viewer Max is
busy converting this Delphi version of Tangram to Visual Basic and recently
spotted a bug: Figures that have a notch exactly the size of a piece can
fool the program. So
accepts
as a solution. Or at least it did until today's update. I fixed it
by ensuring that the center of each piece lies within the solution space before
it can be dropped.

**Addendum August 21, 2005: ** I fixed a minor
problem with pieces placement problem today. Users could drop a
piece with one edge outside a concave portion of the solution space so long as
all vertices were inside the space and all other placement constraints were
met.

**Addendum August, 19, 2009:** Version 4
posted today at least partially addresses a problem that had been recognized
several years ago but has no easy solution. The scale used to define
figures does results in changing their size slightly as they are rotated.
Since the same scale is used to define the puzzles and the pieces, the
distortion is normally not noticeable to users. However in some of the
more complex puzzles that happen to have pieces in their larger configuration,
it's possible for smaller versions to fit within the puzzle boundaries and have
some white space left over. This version checks that the sum of areas of
the pieces as placed by the user matches the area of the pieces as rotated in
the original puzzle. If the user sets all pieces with an area less than
the expected area, a "Gremlin" message is given and she is asked to try again.
The program lists all of the provided puzzles with the condition, thanks to a
sharp eyed viewer from Portugal. Finding the
"Gremlin" solutions can be an interesting exercise in its own right.
BTW, Overmars free version is no longer available.

### Running/Exploring the Program