In a drawing application I am writing, I would like to offer the opportunity for a user to draw an equiangular n-sided polygon inscribed in rectangular bounds drawn by their finger (this application is being written for the iPhone and iPad). My head must not be screwed on right today, because for the life of me, I cannot figure out an algorithm to do that.

So far, I've very easily come up with an algorithm to inscribe such a polygon in an ellipse bounded by that rectangle, but it's not what I want. Pseudocode:

From 0 to the number of sides in the polygon (exclusive):
    Create an affine transform that scales a point to half the width of the rectangle and to half its height.
    Create an affine transform that rotates a point by: (current side + 0.5) * 2 * pi / total sides

    Apply both affine transforms to the point (0, -1)

(Sample Objective-C code can be found here: http://pastie.org/3017040)

Now, this correctly creates an equiangular polygon inside the ellipse (bonus: the polygon is 'right-side-up', meaning if there are an odd number of sides, the bottom of the polygon is the side with a line segment parallel to the bottom segment of the rectangle), but unfortunately, it's not what I'm looking for.

Of course, since the ellipse is inscribed inside the rectangle, the resulting polygon is smaller than the rectangle (I would like the polygon's vertices to be flush against the rectangle's sides, where applicable) - the effect worsens the less sides the polygon has (you can't miss it on triangles and rectangles).

So, it's obvious to me that what I'm doing is wrong, but I can't find any material online or in my brain on how to achieve inscribing an equiangular polygon inside a rectangle. Any help?

To clarify - I understand that polygons with greater than 8 sides cannot be inscribed in a rectangle - I just want to get the vertices of the polygon as close to the rectangle as possible (touching it, in the case of a polygon with $n \leq 8$).


This is impossible. You can have at most two vertices on each side of the rectangle, so you can't inscribe an $n$-gon with $n\gt8$ into a rectangle.

In case your "where applicable" is meant to indicate that you were already aware of this, then you'd need some criterion to measure "how inscribed" a polygon is, in order to have a well-defined problem of finding the "most inscribed" one.

[Edit in response to comment:]

If understand your reformulation of the problem in the comment correctly, then this is an ill-defined problem, at least for $n$ a multiple of $4$, and I suspect also in general. If $n$ is a multiple of $4$, you can get as close as you want to the bounds by having four edges almost identical with the bounds and turning by $90^\circ$ with arbitrarily small edges in the corners.

This is assuming that you really meant "equiangular". Perhaps you meant "regular"?

  • $\begingroup$ Yes, that is what I meant. Basically, I want to get the polygon as close to the bounds of the rectangle as possible. In the case of an octagon and lower, that means actually touching the sides of the rectangle. $\endgroup$ – Itai Ferber Dec 14 '11 at 23:15
  • $\begingroup$ @itaiferber: You can't get a heptagon touching the sides, either, since two pairs of adjacent angles would have to add up to $90^\circ$. $\endgroup$ – joriki Dec 14 '11 at 23:42
  • $\begingroup$ @itaiferber: I edited my answer in response to your comment. $\endgroup$ – joriki Dec 15 '11 at 0:24
  • $\begingroup$ Perhaps this is a little ill-defined, and I haven't explained well enough, but basically, I just want to get an n-sided polygon to fit as closely as possible inside any arbitrary rectangle. Instead of getting a bounding rectangle for a given polygon, I want to do the opposite - generate a polygon using the bounding rectangle. Also, isn't regular more restricting than equiangular? Regular polygons can be inscribed in circles because they are also equilateral, but simply equiangular polygons can be inscribed in ellipses. Perhaps I'm not looking for something more general than equiangular. $\endgroup$ – Itai Ferber Dec 15 '11 at 2:09
  • 1
    $\begingroup$ @itaiferber: This seems to be a misunderstanding. Yes, "regular" is more restricting than "equiangular", and that was the point -- "equiangular" is unrestricting enough that, at least in the case where $n$ is a multiple of $4$, there's no best solution because the solutions can come arbitrarily close to coniciding with the bounding rectangle everywhere, except in an arbitrarily small neighbourhood of the corners. Making it even more general won't help, since it will just add more solutions to the all ready too many solutions. $\endgroup$ – joriki Dec 15 '11 at 7:46

Your Answer

