9
\$\begingroup\$

Introduction

Given five points in the plane, your task is to compute the area of the ellipse passing through these points.

You can assume that exactly one non-degenerate ellipse can be constructed with the given input values.

Rules

Input is 10 integers in any convenient form, corresponding to the x and y coordinates of the points. For example, you could take input as a list of 10 integers [x1, y1, x2, y2, ..., x5, y5], or as [[x1, y1], [x2, y2], ..., [x5, y5]], etc.. You may also handle decimal numbers, but only integers are required.

Output is a representation of the area of the ellipse. This may be some symbolic expression, or a decimal value with at least 8 digits of precision.

This is code-golf, so the shortest answer in bytes wins.

Example Input and Output

Input:

[-2, 3, 2, 5, 5, 3, 4, 0, 1, -3]

Output:

62.15326783788685

A depiction of the ellipse passing through these points:

The ellipse for this example

More examples:

f(60, -92, -31, -10, 78, -19, -27, -35, 91, -37) = 9882.59540465108
f(-9, -4, 7, 7, 10, 1, -7, -10, 0, 7) = 269.5966648188643
f(-3, 2, 0, -5, 4, 0, -4, 1, -1, 2) = 98.54937293879908
\$\endgroup\$
  • \$\begingroup\$ Was this by any chance inspired by this SPOJ problem? http://www.spoj.com/problems/ELLIPSE/ \$\endgroup\$ – xnor Oct 3 '17 at 8:42
  • \$\begingroup\$ It was not. I am not active on that site. \$\endgroup\$ – Ethan Ward Oct 3 '17 at 8:45
  • \$\begingroup\$ What does it mean that the output may be a symbolic expression? \$\endgroup\$ – xnor Oct 3 '17 at 9:21
  • \$\begingroup\$ @xnor Perhaps an (unevaluated) elliptic integral? \$\endgroup\$ – Mego Oct 3 '17 at 9:28
  • 2
    \$\begingroup\$ Annnnd the best tool for the job goes tooooooo: Mathematics graphing programs! Go figure :P. \$\endgroup\$ – Magic Octopus Urn Oct 4 '17 at 16:26
7
\$\begingroup\$

Mathematica, 87 80 78 bytes

Area@ImplicitRegion[+##Sign@#&@@Det[{1,##,1##,#^2,#2^2}&@@@{x|y,##}]>0,{x,y}]&

Takes 5 inputs: [{x1, y1}, ... , {x5, y5}].

Returns an exact/symbolic value.

How?

Let f(x, y) denote the vector (1, x, y, xy, x^2, y^2) for some x, y.

Then, the determinant of the matrix with row vectors [f(x, y), f(x1, y1), f(x2, y2), ..., f(x5, y5)] is zero iff (x, y) is a point on the ellipse we are looking for. i.e. the determinant gives the expression for the ellipse.

Since the sign of the expression might be inverted, we take the constant term and multiply the entire expression by the sign of the constant. That way, we can set the expression greater than 0 to find the area.

\$\endgroup\$
  • \$\begingroup\$ +1. I like how you fixed an issue with Sign. \$\endgroup\$ – Vitaliy Kaurov Oct 3 '17 at 20:38
5
\$\begingroup\$

MATLAB, 130 124 114 bytes

The input is takean as two column vectors, one for the x- and one for the y-coordinates. This method uses a least sequares regression, which provides the exact ellipse if all points are exactly on an ellipse, and then applies the formula provided here (thanks @orlp) to calculate the area.

function A=f(x,y);p=null([x.^2,2*x.*y,y.^2,2*x,2*y,0*x+1]);A=pi*det(p([1,2,4;2,3,5;4:6]))/abs(p(1)*p(3)-p(2)^2)^1.5

By appending following lines you can even plot the curve:

X=x;Y=y;
[x,y] = meshgrid(linspace(-7,7,50));
W = [x(:).^2,2*x(:).*y(:),y(:).^2,2*x(:),2*y(:),0*x(:)+1];
Z=x;Z(:) = W*p;
clf;plot(X,Y,'o');hold on;contour(x,y,Z,[0,0]);

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Mathematica 84 Bytes

I found this to be an interesting problem. Every ellipse is an affine transformation of the unit circle which can be parameterized as {x,y}={Cos(t),Sin(t)}, so the points on the circle can be mapped to the ellipse by {xE,yE}=A{x,y}+B where A is a constant matrix and B a vector. Plugging in the points yields 10 scalar equations and 11 scalar unknowns, but we can decide that the parameterization starts at t=0, so the system is solvable. The absolute value of the determinant of the matrix A is the ratio of the area of the ellipse to the unit circle so we multiply by Pi. Taking Max gets rid of the negative solution.

Max[π(a d-b c)/.Solve@MapThread[#2=={e,f}+{a,b}Cos@#+{c,d}Sin@#&,{{0,u,v,w,x},#}]]&

Usage:

%@{{-2, 3}, {2, 5}, {5, 3}, {4, 0}, {1, -3}}

Yields:

(1001 π)/(16 Sqrt[10])
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 144 bytes

x_±y_:=x^2a+b*x*y+y^2c+d*x+e*y+f;n=∞;Integrate[UnitStep[x±y/.FindInstance[And@@(#±#2==0&@@@#),{a,b,c,d,e,f},Reals,2][[1]]],{x,-n,n},{y,-n,n}]& 


works for all test cases

Input example: [{{-3, 2}, {0, -5}, {4, 0}, {-4, 1}, {-1, 2}}]

Results

9882.59540465108163146329
269.596664818864334050934
98.5493729387989852754258

-10 bytes from JungHwan Min
± is 1-byte in default windows encoding [CP-1252]

\$\endgroup\$
  • \$\begingroup\$ Hmm...why am I getting infinity on your input example? \$\endgroup\$ – numbermaniac Oct 4 '17 at 0:34
  • \$\begingroup\$ @numbermaniac I don't know. I get it right. are you using this input [{{-3, 2}, {0, -5}, {4, 0}, {-4, 1}, {-1, 2}}]? \$\endgroup\$ – J42161217 Oct 4 '17 at 0:38
  • \$\begingroup\$ Yeah, I am - that's weird. \$\endgroup\$ – numbermaniac Oct 4 '17 at 0:52
  • \$\begingroup\$ I am getting (3575880 π)/(2351 Sqrt[2351]) which is accepted as an answer \$\endgroup\$ – J42161217 Oct 4 '17 at 0:54
  • 1
    \$\begingroup\$ Weird, even ClearAll doesn't fix it. Oh well, don't worry about it haha. As long as it works for you. What version of Mathematica are you on? \$\endgroup\$ – numbermaniac Oct 4 '17 at 1:00
2
\$\begingroup\$

Desmos, 101 bytes

u
v
f(a,b,c,h,k,x,y)=(((x-h)cosc+(y-k)sinc)/a)^2+(((x-h)sinc-(y-k)cosc)/b)^2
f(m,n,o,p,q,u,v)~1
mn\pi

Online Desmos doesn't like multiline pastes, so you have to enter it in one line at a time, or

Try It Online!

Input is taken with the two lists u and v. The output is shown on the last line.

Explanation:

  • The first two lines name the input variables.
  • The third line defines the equation for any ellipse, with radii a and b, rotation angle c, and offset (h,k).

    • Prettified, it looks like this: enter image description here
  • The fourth line calculates a regression of f over the lists u and v, finding radii m and n, rotation angle o, and offset (p,q).

  • The last line calculates the area of the ellipse with the formula A = pi*r1*r2

You can also Try It Online (different link) for a slightly expanded, interactive visual version. You can move around the five points and view the ellipse and area in real time:

enter image description here

Alternatively, here is a slightly longer solution using this formula (same as @flawr's answer):

Desmos, 106 bytes

u
v
f(A,B,C,D,E,F,x,y)=Axx+2Bxy+Cyy+2Dx+2Ey+F
f(G,H,I,J,K,L,u,v)~0
\pi(GIL+2HJK-JJK-GKK-HHL)/(GI-HH)^{1.5}

Try It Online!

\$\endgroup\$
  • \$\begingroup\$ You might not need the backslash there before pi on the last line: if I type in mnpi, the pi symbol still shows up. Also, do you mean "the output is shown on the last line", not input? \$\endgroup\$ – numbermaniac Oct 4 '17 at 0:38
  • 1
    \$\begingroup\$ @numbermaniac I'm putting in the backslash because when I copy-paste it in, it doesn't recognize mnpi, even though it words when I type it out. And yes, I meant output, not input, thanks. \$\endgroup\$ – Scott Milner Oct 4 '17 at 2: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.