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

Problem Description

This program searches a given set of nodes and lines to count and display polygons of various types.

Background & Techniques

Counting polygons embedded in a figure is the goal of a number of puzzles that I have run across.  See "How Many Rectangles?" and "How Many Triangles?" for  previously implemented examples using figures with only rectangles (a Tennis Court) or triangles as the figures to analyze.  Extending this to other shapes and polygon types was more difficult than I had anticipated.  There are a number of definitions of what makes a polygon but I have settled on 4 types here.  From simple to complex they are:

Primitive:  A single closed figure with no other lines intersecting its edges.  Typically these are triangles or quadrilaterals, but could be any number of sides.

Convex: Combinations of adjoining primitive polygons whose outer outline (the "hull") forms a figure with no "notches", i.e. all turns are in the same direction, right or left, as the boundary is traveled.  A polygon is convex if and only if all internal angles at the vertices are less than 180º.

Simple:  All polygons which have the same number of edges as vertices.  That is, each edge connects two vertices and each vertex has exactly two edges touching it.  Simple polygons include all of the convex polygons plus those which are concave, i.e. have "notches".

All types: If we allow two simple polygons to touch at a point without sharing an edge, we have a "self intersecting" polygon.  In a single polygon there may be more than one vertex which is shared by multiple simple polygons, so long as the never share an edge since such sharing would make that edge internal to the polygon.  By definition, an edge must separate areas inside the polygon from areas outside.

Implementing this has required a few weeks of spare time "brain exercise" and about 600 lines of new code in addition to modifications to previously implemented Graph Searching and Geometry units.  It may take that much additional effort to generalize and simplify inputting the figures to be analyzed. There are currently 4 predefined figures to choose from: Small, Medium, Large, and Tennis Court. The "Large" figure in particular requires a "depth
of search" parameter to keep search time to a reasonable values. Search depth limits the maximum number of edges on polygons detected to 1 less than the depth selected. Maximum depth allowed is 12 levels, but I have only completed searches up to depth 10. Setting a depth limit to 4 will find only triangular polygons and a depth limit of 5 is sufficient to find all rectangles in the Tennis Court figure.

Everything else you need to know about the program should be self-evident.  There are separate pages which list the total set of nodes and edges found and some or all (you choose) of the found polygons of the selected type.  Polygons are "named" with a string of letters representing the vertices which are labeled on the display from top to bottom within increasing left to right coordinates.  Clicking on any polygon label in the list will display that figure with red edges.  

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:

Deferred for now. (So many programs, so little time J)  Email me if you tackle the source code and have questions. 

Note that the source for UTGraphSearch and UGeometry units has been enhanced for this program.  Those units are included in the source code here but have not yet been moved  to the DFF Library. 

Addendum August 26,2013:  Version 3.2 posted today does a better job of finding all polygons at a given search level.  When I added the figure from our "How Many Triangles?" program I realized that some of the  interior nodes (created when interior lines intersect) were not being examined during the polygon search.  That problem is corrected today.  The easily checked polygon counts (the Tennis problem rectangle counts,  the Triangles problem triangle counts, and the the primitive counts for any figurer now correct.  (Total rectangle and triangle counts are found by limiting "Max Search Depth" values to 5 and 4 respectively.)      

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.