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$).
Best Answer
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"?