9
\$\begingroup\$

Given consecutive side lengths s1, s2, s3... s_n of an n-gon inscribed in a circle, find its area. You may assume that the polygon exists. In addition, the polygon will be convex and not self-intersecting, which is enough to guarantee uniqueness. Built-ins that specifically solve this challenge, as well as built-in functions that calculate the circumradius or circumcenter, are banned (this is different from a previous version of this challenge).

Input: The side lengths of the cyclic polygon; may be taken as parameters to a function, stdin, etc.

Output: The area of the polygon.

The answer should be accurate to 6 decimal places and must run within 20 seconds on a reasonable laptop.

This is code golf so shortest code wins!

Specific test cases:

[3, 4, 5] --> 6
[3, 4, 6] --> 5.332682251925386
[3, 4, 6, 7] --> 22.44994432064365
[5, 5, 5, 5] --> 25
[6, 6, 6, 6, 6] --> 61.93718642120281
[6.974973020933265, 2.2393294197257387, 5.158285083300981, 1.4845682771595603, 3.5957940796134173] --> 21.958390804292847
[7.353566082457831, 12.271766915518073, 8.453884922273897, 9.879017670784675, 9.493366404245332, 1.2050010402321778] --> 162.27641678140589

Test case generator:

function randPolygon(n) {
  var left = 2 * Math.PI;
  var angles = [];
  for (var i = 0; i < n - 1; ++i) {
    var r = Math.random() * left;
    angles.push(r);
    left -= r;
  }
  angles.push(left);
  var area = 0;
  var radius = 1 + Math.random() * 9;
  for (var i = 0; i < angles.length; ++i) area += radius * radius * Math.sin(angles[i]) / 2;
  var sideLens = angles.map(function(a) {
    return Math.sin(a / 2) * radius * 2;
  });

  document.querySelector("#radius").innerHTML = radius;
  document.querySelector("#angles").innerHTML = "[" + angles.join(", ") + "]";
  document.querySelector("#inp").innerHTML = "[" + sideLens.join(", ") + "]";
  document.querySelector("#out").innerHTML = area;

  draw(angles);
}

function draw(angles) {
  var canv = document.querySelector("#diagram"),
    ctx = canv.getContext("2d");
  var size = canv.width
  ctx.clearRect(0, 0, size, size);
  ctx.beginPath();
  ctx.arc(size / 2, size / 2, size / 2, 0, 2 * Math.PI, true);
  ctx.stroke();
  ctx.beginPath();
  ctx.moveTo(size, size / 2);
  var runningTotal = 0;
  for (var i = 0; i < angles.length; ++i) {
    runningTotal += angles[i];
    var x = Math.cos(runningTotal) * size / 2 + size / 2;
    var y = Math.sin(runningTotal) * size / 2 + size / 2;
    ctx.lineTo(x, y);
  }
  ctx.stroke();
}
document.querySelector("#gen").onclick = function() {
  randPolygon(parseInt(document.querySelector("#sideLens").value, 10));
}
<div id="hints">
  <p><strong>These are to help you; they are not part of the input or output.</strong>
  </p>
  Circumradius:
  <pre id="radius"></pre>
  Angles, in radians, of each sector (this are NOT the angles of the polygon):
  <pre id="angles"></pre>
</div>
<hr>
<div id="output">
  Input:
  <pre id="inp"></pre>
  Output:
  <pre id="out"></pre>
</div>
<hr>
<div id="draw">
  Diagram:
  <br />
  <canvas id="diagram" width="200" height="200" style="border:1px solid black"></canvas>
</div>

Number of side lengths:
<input type="number" id="sideLens" step="1" min="3" value="3" />
<br />
<button id="gen">Generate test case</button>

\$\endgroup\$
  • 7
    \$\begingroup\$ I know an easy way to find its perimeter. \$\endgroup\$ – mIllIbyte Apr 16 '16 at 18:04
  • 1
    \$\begingroup\$ I know an easy way to find the number of sides \$\endgroup\$ – Luis Mendo Apr 16 '16 at 19:05
  • \$\begingroup\$ This problem is pretty easy given the circumradius, but without it it's incredibly difficult. \$\endgroup\$ – poi830 Apr 16 '16 at 19:32
  • \$\begingroup\$ It's also easy if there are fewer than five sides, not that it matters in code golf. \$\endgroup\$ – Neil Apr 16 '16 at 19:54
5
\$\begingroup\$

Python 2, 191 bytes

from math import*
C=sorted(input());l,h=C[-1]/2,sum(C)
while h-l>1e-9:m=l+h;a=[asin(c/m)for c in C[:-1]];f=pi-sum(a);l,h=[l,m/2,h][m*sin(f)<C[-1]:][:2]
print sum(l*l*sin(2*t)for t in a+[f])/2

Uses a binary search to find the radius, then calculates the area of each segment by the angle/radius.

It finds the radius by first summing all but the largest chord angle, and checking the remaining angle to the remaining chord. Those angles are then also used to compute the area of each segment. A segment's area can be negative, if it's angle is bigger than 180 degrees.

Readable implementation:

import math

def segment_angles(line_segments, r):
    return [2*math.asin(c/(2*r)) for c in line_segments]

def cyclic_ngon_area(line_segments):
    line_segments = list(sorted(line_segments))
    lo, hi = max(line_segments) / 2, sum(line_segments)
    while hi - lo > 1e-9:
        mid = (lo + hi) / 2
        angles = segment_angles(line_segments[:-1], mid)
        angles.append(2*math.pi - sum(angles))
        if 2 * mid * math.sin(angles[-1]/2) < line_segments[-1]:
            lo = mid
        else:
            hi = mid
    return sum([lo*lo * math.sin(a) / 2 for a in angles])
\$\endgroup\$
  • \$\begingroup\$ Does this work if the center is outside the polygon? (For example, a triangle with side lengths 6, 7, 12). Sometimes the sqrt(4**2 - c**2/4) needs to be negative, when the angle is greater than pi. \$\endgroup\$ – soktinpk Apr 16 '16 at 19:58
  • \$\begingroup\$ @soktinpk I fixed my answer. \$\endgroup\$ – orlp Apr 20 '16 at 8:43
0
\$\begingroup\$

Octave, 89 bytes

r=sum(s=input(''));while sum(a=asin(s/2/r))<pi r*=1-1e-4;b=a;end;disp(sum(cos(b).*s/2*r))

Explanation

The angle a spanned by a segment of length s is 2*asin(s/2/r), given a circumradius r. Its area is cos(a)*s/2*r.

Algorithm

  1. Set r to something too large, such as the perimeter.
  2. If the cumulated angle is smaller than 2pi, reduce r and repeat step 2.
  3. Calculate the area.
\$\endgroup\$
  • \$\begingroup\$ On average, how many iterations does this take for r to be set? (out of curiosity) \$\endgroup\$ – soktinpk Apr 16 '16 at 19:50
  • \$\begingroup\$ There is no way this has the required precision. You repeatedly multiply the radius by 0.9999 to reduce it, this makes it very easy to undershoot the required 6 decimals of precision. \$\endgroup\$ – orlp Apr 16 '16 at 19:53
  • \$\begingroup\$ @soktinpk around 15000 for r*=1-1e-4 and 150000 for r*=1-1e-5. \$\endgroup\$ – Rainer P. Apr 16 '16 at 19:54
  • \$\begingroup\$ @RainerP. Those two values are the same. \$\endgroup\$ – Nic Hartley Apr 16 '16 at 19:55
  • 1
    \$\begingroup\$ @soktinpk it is generally not a good idea to make an exception for a specific answer. \$\endgroup\$ – Cyoce Apr 16 '16 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.