So I have a problem: given the length of the edges L = {l₀, l₁, … l_N} of an N-sided irregular polygon with N > 3, I need to construct the values for the radius R and the angles A = {a₀, a₁, … a_N} such that the points P = { R, a_i } form a closed polygon with the lengths given.

I searched through the internet and found all sorts of articles on the subject, but a day of searching and I was unable to find a way that I could construct the values R and A. I’m sure it’s out there, but I figured it’d be a good exercise to do it myself.

Based on my reading apparently there is no current solution to the problem–so I went ahead and built a simple algorithm to construct the values. The idea is outlined below.

---

Before we continue, we assume the longest length of our polygon is l₀. We can rotate the edges of the polygon if this is not the case.

Observation 1: The vertices P = { p₀, p₁, … p_N } of our cyclic polygon may be described by the values p_i = ( R, a_i ) in polar coordinates:

By observation, the sum of the angles A is 360°.

Hypothesis 1: For any set of edge lengths L, there is only one set of values for R and A which create a cyclic polygon.

Sketch of proof: By construction.

Hypothesis 2: In constructing a polygon with lengths L, we have two cases for the centroid of the circumscribed circle that encompasses the polygon. Either the centroid is inside the polygon:

Or the centroid is outside the polygon.

If the centroid of the circumscribed circle is outside the polygon, it is outside the edge with the largest length, and it is only outside one of the edges.

Sketch of proof: If the centroid of the circumscribed circle is outside of one of the edges, the edge has the property that the associated angle a_i has an angle greater than 180°. If the centroid is outside two edges, this implies the sum of the angles exceeds 360°, violating Observation 1 above.

Hypothesis 3: The value of R must be greater than ^l₀/₂, where l₀ is the length of the longest edge.

Sketch of proof: The lower bound of R is determined by an edge which passes directly through the center of the circle. If the edge does not pass through the center of the circle, then the diameter must be larger than the specified edge.

Observation 2: Given an edge in a circumscribed polygon with length l_i and a radius R, the angle associated with the edge a_i can be calculated as:

For an edge where the center of the circumscribed circle is outside the edge, the angle a is between 180° and 360°.

Sketch of proof: Law of cosines.

---

With these observations we could construct our polygon by searching for the proper value of R.

The essence of our algorithm is to search for a value R such that the following function is zero:

One issue we need to deal with is calculating the angle on the longest line segment of our polygon. We can handle this case by starting with the angle a₀; the idea is that we know a₀ is in the range (0,360). From the angle a₀ we can calculate r using the formula:

Sketch of proof: Geometric observation.

We now can construct a function F(a) = Σa_i, by calculating the angles of all of the edges in our polygon for a proposed radius r, calculated using the value a as the angle a₀. (If the angle is greater than 180°, this fits hypothesis 2 above.)

Hypothesis 5: The function F(a) is monotonic on the value a.

Sketch of proof: A geometric argument; as R increases, the angles decrease, while as R decreases, the angles increase. The increase or decrease in angles are monotonic, so the sum is monotonic. The function R relating to a is also monotonic.

Hypothesis 6: The function F(a) – 360 has one zero.

Sketch of proof: Trivial observation based on the above hypothesis.

---

We can now sketch the code which searches for the zero given a value a. We can use a number of computational methods to search for the zero of F(a) – 360; in our code below we use a simple binary subdivision search to search for a with 0 < a < 360°.

---

Preliminary functions

Given an object with the following declaration:

#define EPSILON		1e-6			/* A very small value. */

@interface KTCyclicPolygon ()
{
    NSInteger n;            // # edges
    NSInteger *edges;       // length of edge

    NSInteger ledge;        // index of maximum length edge
}

We can implement our algorithm by first, finding the edge that has the maximum length:

- (NSInteger)largestEdge
{
    NSInteger i = 0;
    NSInteger len = edges[0];

    for (NSInteger j = 1; j  len) {
            len = edges[j];
            i = j;
        }
    }
    return i;
}

We need a way to calculate the angle of an edge given a radius:

- (double)angleAtIndex:(NSInteger)index radius:(double)r
{
    // Calculate a from observation 2

    double l = edges[index];
    double c = 1 - (l*l)/(2*r*r);
    return acos(c);         // output from 0 to M_PI
}

Then we can calculate f(a) above:

- (double)f:(double)a
{
    /*
     *  Calculate r from a.
     */

    double l = edges[ledge];
    double m = l / 2;
    double r = m / sin(a/2);

    /*
     *  Calculate the angles and sum from 1 to N
     */

    double sum = a;

    /*
     *  Sum the angles from 1 to N
     */

    for (NSInteger i = 0; i < n; ++i) {
        if (i == ledge) continue;
        sum += [self angleAtIndex:i radius:r];
    }

    /*
     *  Now subtract from our zero.
     *
     *      If the angle is small (meaning we selected too small a start angle)
     *  then this value will be negative. If we picked too large a start
     *  angle (meaning a was too big), then the sum will be large and the
     *  value will be positive.
     */

    return sum - 2*M_PI;                // Return value is angle gap to close.
}

At this point we can easily calculate a value a between 0 and 360°:

- (BOOL)calculateCyclicPolygon
{
    if (n <= 3) return NO;      // Need a 4 sided object or larger

    /*
     *  Step 1: Find the largest edge
     */

    ledge = [self largestEdge];

    /*
     *  Step 2: given a min/max value of 0, 360, find a between those values
     *  which approach our error
     */

    double mina = 0;
    double maxa = M_PI*2;
    double mida;

    for (;;) {
        mida = (mina + maxa)/2;

        double f = [self f:mida];

        if (fabs(f) < EPSILON) break;       // a solves our solution
        if (f < 0) {
            // Angle too small; we need a larger angle
            mina = mida;
        } else {
            // Angle too large; we need a smaller angle
            maxa = mida;
        }
    }

    double a = mida;                        // to within epsilon.

At this point the angle a has been found to within the error specified in our constant EPSILON.

We can validate the correctness of our algorithm by calculating the radius, and the angles for the rest of the items. We can then calculate the polar coordinates of each of the edges and compare the lengths with the stored edge lengths:

    double l = edges[ledge];
    double m = l / 2;
    double r = m / sin(a/2);

    double x = r;
    double y = 0;
    double angle = 0;
    for (NSInteger i = 0; i < n; ++i) {
        if (i == ledge) {
            angle += a;
        } else {
            angle += [self angleAtIndex:i radius:r];
        }
        double xn = cos(angle) * r;
        double yn = sin(angle) * r;

        double dx = xn - x;
        double dy = yn - y;
        double d = sqrt(dx * dx + dy * dy);

        printf("Vertex: %g %gn",x,y);
        printf("  Edge %d: %d == %gn",(int)i,(int)edges[i],d);

        x = xn;
        y = yn;
    }
    printf("Vertex: %g %gn",x,y);
}

When run this will find the initial angle a which converges to our solution. Running with input values 1, 2, 3 and 4, we get the output:

Vertex: 2.0026 0
  Edge 0: 1 == 1
Vertex: 1.75293 0.96833
  Edge 1: 2 == 2
Vertex: 0.0408695 2.00219
  Edge 2: 3 == 3
Vertex: -1.9922 -0.203859
  Edge 3: 4 == 4
Vertex: 2.0026 -3.40378e-07

This shows our vertices define a closed cyclic polygon with edges of lengths 1, 2, 3 and 4–to within our error tolerance.