Problem Description
Here's a simple question.
How many rectangles of all sizes are formed by the
lines in this diagram of a standard tennis court?
Background & Techniques
The answer is, "more than you would have thought". You can download the
program below to work on it, or let the program show you the solution.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for programmers
This is a program that I would approach differently is I were to rewrite
it. As usual, I worked on the the program solution code first, since
it is the most fun to write. I decided to use our
TGraphSearch class to
define the court as a graph.
Program Solution search
The 19 corners are the nodes and the
28 line segments connecting the nodes are the edges of our graph. There was
no routine in the class that would find rectangles, so I modified the
MakePathsToDF depth first search path finding function to make a FindRectangles version.
By assigning a Weight value of 0 to horizontal edges and 1 to
vertical edges, I could detect direction changes as paths through the graph
were searched. In the process of checking all paths , whenever we get
back to the start node and have changed direction exactly three times, a rectangle had been found.
I labeled the
nodes with single letters "A" through "S" so rectangles were string of 4 to
10 letters. The search process generates many duplicates (ABCD = BCDA
= CDAB = DABC, for example). I sort the letters within the string
defining each rectangle and save each unique one in a
TStringList named
SolutionList. Duplicates are easily detected and ignored by
checking to see if the sorted string is already in the list.
Recall that a depth first search commonly works by recursively by adding the
passed node to the path and calling itself once for each adjacent node
that has not already been visited. A special test was required in the
FindRectangles to allow the original StartNode to be
visited a second time to verify that a complete rectangle had been found.
User solution search
After program solution search was working, I started implementing user play and found that
defining rectangles by clicking on edges was too cumbersome to be
usable. Search for alternative ways to define rectangles, I settled on
a rectangle based solution. The court has 10 base rectangles with only
the n4 corners as nodes. By allowing users to click individual "base" rectangles do define a "compound"
rectangle to be added to the solution list. The same "solutionlist"
concept used in the program search is used to keep the user from adding
the same rectangle a second time.
As the user click individual base rectangles, we turn on (or off) the
Highlight flag in an array, BaseRects, containing the
corner node letters and coordinates of the upper left and lower right
corners. When the user clicks the "Add rectangle" button, the
button click exit scans the BaseRects array and builds a string of nodes. Rearranging this set of all
selected nodes
was a little
tricky as I wanted to display each rectangle as a string of node
letters in a counter
clockwise direction starting from the upper-left corner.
Function NormalizeRect does the job.
NormalizeRect starts by removing all duplicates from the
input string of nodes and the uses the nodes data to find the minimum and maximum X and Y coordinates
(XMin, YMin, Xmax, Ymax). Nodes must exist
in our input node string for the four corners at (Xmin, Ymin), (Xmax, Ymin), (Xmin, Ymax) and (XMax, Ymax)
or else the figure passed by the user is not a rectangle at all.
All of the nodes which do no have a coordinate at one least one of the four
extreme points are interior nodes and are eliminated from our node string. All of the
nodes at YMin sorted by the X coordinate define the top edge of the
rectangle, etc. In this way can build the string find our way around the rectangle in
the clockwise direction.
If NormalizeRect returns true, it also returns a record containing the
information about the selected rectangle. As in the program search, if
the sorted key for this rectangle has not yet been added to the SolutionList,
is is add and the new rectangle is counted and displayed.
This describes the basic operation of the program. The
TGraphList class used is defined in unit UTGraphSearch
contained in our library zip DFFLibV12 or later. You must do a one
time download of this library file to in order to recompile the program.
Running/Exploring the Program
