Tangram 2

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

Square and Cat 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:

bulletFile handling and data structure compatible with the Overmars'  Tangram program.  
bulletGeometric processing code to: 
bulletDraw figure outlines,  i.e. collections of piece polygons without the interior lines.
bulletDetect valid drop locations - pieces can only be placed within the figure outline and not overlapping previously placed pieces. 
bulletDetect when a puzzle has been solved.

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 

bulletDownload source (includes some Overmars figure and piece definition files)
bulletDownload executable code (includes some Overmars' figure and piece files).

Suggestions for Further Explorations

Construct (and draw)  proper figure outlines.
Write a Tangram Editor.  (Although a fine editor is included in the Overmars download and it seems that the code would actually be simpler than the playing program.   No new problems=no fun  :>) )
There's a function in Tangram2, Overlapped, that decides if 2 co-linear line segments overlap or are just end-to-end.  The current version has  50 lines of source code, which seems absurd.  The problem is simple and the solution just shouldn't be that long.   But I've thought that about a lot of geometric testing tasks in the course of writing this program.    
I haven't checked for memory leaks, but it would surprise me there are none.  We'll do a "Delphi Topics" on this one of these days and use this program as an example.   
 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.