How Many Triangles?

[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.

Contact

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

Search DelphiForFun.org only

 

 

Problem Description

How many triangles can you find in this figure?  In addition to the 18 labeled triangles, there are 28 more that can be formed by combining the primitive ones.

Background & Techniques

I wrote this program to help me find the last few triangles.  It is very difficult to keep track of which triangles have been found using pencil and paper. 

To play the downloaded executable program, just click to select one or more of the labeled polygons to form a new triangle, then right click to add it to your list.   When you get stuck, I added a "Hint" button to suggest where the unidentified triangles lie. 

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

Lots of code required here, more than altogether 900 lines.  The octagonal outline and the intersecting interior lines are defined as (x,y) coordinate values in arbitrary units.  We scale the input units to pixels using a scaling factor to fill 90% of the available image width or height, whichever is smaller.  I'm not going to explain the code in detail but here are the major problem areas that have kept me out of trouble for the past three weeks:

  • Computer Geometry: Our UGeometry unit provided the IntersectLine procedure used to locate all of the node created by the intersecting lines.  After the polygons thus formed have been defined, the PointInPoly function is used to identify which polygon was clicked by the user.  
  • StringLists:
    • Nodes holds the list of intersections as 6 character strings representing X and Y pixel values (3 characters each).  
    • Edges hold the list of line segments which make up the sides of all possible triangles. For each interior pattern line, we define edges from each node to every following node on that line. Each entry is a 12 character string (two six character node string).
    • PrimtiveEdges contain the Edges that connect each pair of adjacent nodes, i.e. no other nodes between these two.
    • PrimitivePolys is not a string list, it's an array of records one for each of the primitive polygons and contains the  Id letter, the array of TPoint for the nodes of the polygon, the center of the polygon (used for the label location) and Clearpoint, a point halfway between the  center and one of the corners.  This a a safe point to start the FloodFill procedure to paint the polygon yellow when it is selected  or white when it is deselected. Clicking on or near the center point for a closed letter like B, R, or O may only paint the center of that letter.
    • AllPolys is slightly misnamed, it holds the solution triangles. When searching for all possible triangles, we check all triples (a,b,c) of nodes from the Node list,  identifying those that are mutually connected (a to b, b to c, and  c to a) and not all Colinear (another UGeometry function).  When found, we run through the Primitvepolys array using the PointInPoly function again to check if the center is inside of the newly discovered triangle.  the Ids of those that are contained are used to construct a key used as the AllPolys key for this triangle.
    • UserTriangles the list of triangles defined so far the the user.  We need it in order to detect duplicate selections and to match against the AllPolys list to find missing triangles when a Hint is requested.
  • Image Click processing: I chose to use clicks to select primitive triangles to include in the triangle being defined.  Double click would be the logical signal to add the triangle to the UserTriangles list, but it turns out that the first click of a double click generates an OnClick event which is undesirable in this case. Instead, the user must use the right mouse button to signal completion of a triangle and i use the OnMouseUp event exit to process it..   
  • Memo Click Processing:  Users can click any of several TMemos to display the click item (an edge, polygon, or triangle).  The trick for identifying the line which was clicked is provided by the MemoLineClicked function in out DFFUtils unit.
  •  Hint request processing:  When the user clicks the Hint button, I match the AllPolys entries against the UserTriangles list and build a temporary list triangles not yet identified.  Then a random one of those is selected and the length and the first letter of  its key is presented as the hint.

The UGeometry and DFFUtilties units are part of our DFFLibrary zip file and will be required to recompile the code.  It is available here

 

Running/Exploring the Program 

Suggestions for Further Explorations

Add ability to load additional figures.  The code was written with the idea that it could handle other patterns, but I haven't tried any yet.
 

 

Original:  August 20, 2010

Modified:  August 21, 2010

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.