Find All Polygons

[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

15 Polygons here.  Can you find them all?

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 

bulletDownload  executable
bulletDownload source 

Suggestions for Further Explorations

Change base figure definition strategy from "outline + intersecting lines" to "nodes + edges"
Improve edge definition to automatically extend colinear edge segments to create new potential edges.  Currently if nodes ABCD are colinear and AD is defined in the outline, segments AB, AC, BC, BD, and CD must all be defined as additional segments.
Add Load and Save procedures to allow new figures to be analyzed.
Allow interactive base figure definition
   
Original: August 22, 2013

Modified:  May 15, 2018

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