[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
The question is: "What is the largest rectangle that can be inscribed in an arbitrary given simple polygon"?
Background & Techniques
This is an exploration of techniques for finding the maximum area rectangle
that can be inscribed in arbitrary concave or convex simple polygons.
Polygons can be defined by clicking vertex points on the image area or loaded
from a text file. All coordinates in this version are pixel locations on
an 500 x 500 pixel image area.
Several strategies are available for searching for rectangles. The
"Strategies" options create trial rectangle centers which are then passed to the
rectangle creation procedure, looking for new maximum area examples.
A small book could be written describing the code written so far, however because of the exploratory nature of the program, the geometry involved, and time constraints it is probably best to delay better documentation until the code has evolved to a more permanent form. Much of the code was developed while "in the zone" which is not conducive to tidy organization so cleanup is needed.
It is still fun to play with though, watching various strategies improve results, sometimes quickly, sometimes slowly.
The UGeometry library unit has been modified to add a TPolygon type and to override the PolygonArea function to return the Centroid (center of mass) point as well as the Area of a polygon. The modified version has been included with the source download here and will be added to our DFFLib zip file with the next update.
Suggestions for Further Explorations
Copyright © 2000-2017, Gary Darby All rights reserved.