Identify the Conic Section

Question

Given 5 distinct points on a two-dimensional plane, determine the type of conic section formed by the points. The output shall be one of circle, hyperbola, ellipse, or parabola.

Rules

• The points will be in general linear position, meaning that no three points are collinear, and thus the conic passing through them will be unique.
• The coordinates of the 5 points will be decimal numbers between -10 and 10, inclusive.
• The precision for the decimal/float values should be the precision of your language's native float/decimal type. If your language/data type is arbitrary-precision, you may use 12 digits after the decimal point as the maximum required precision, rounding toward zero (e.g. 1.0000000000005 == 1.000000000000).
• Capitalization of the output does not matter.
• Outputting ellipse when the conic section is actually a circle is not allowed. All circles are ellipses, but you must output the most specific one.

On floating point inaccuracies and precision:

I'm trying to make this as simple as possible, so that issues with floating point inaccuracies don't get in the way. The goal is, if the data type was "magical infinite precision value" instead of float/double, then everything would work perfectly. But, since "magical infinite precision value" doesn't exist, you write code that assumes that your values are infinite precision, and any issues that crop up as a result of floating point inaccuracies are features, not bugs.

Test Cases

(0, 0), (1, 5), (2, 3), (4, 8), (9, 2) => hyperbola
(1.2, 5.3), (4.1, 5.6), (9.1, 2.5), (0, 1), (4.2, 0) => ellipse
(5, 0), (4, 3), (3, 4), (0, 5), (0, -5) => circle
(1, 0), (0, 1), (2, 1), (3, 4), (4, 9) => parabola

• xnor: For floats, outputs like circle seem to require checking float equality to distinguish from a very round ellipse. What precision should we assume here?
• orlp: @Mego Why not allow the integer version of the problem for all languages , but with a wider range, e.g. -10000 to 10000.
• Maltysen: are you sure test case four is correct? desmos: desmos.com/calculator/fmwrjau8fd
• Maltysen: Also, 3 looks wrong too: desmos.com/calculator/tkx1wrkotd
• edc65: I think you are understimating the problems with FP accuracy, and that leads to answer like this codegolf.stackexchange.com/a/77815/21348

Answer 1

JavaScript (ES6), 316 (削除) 323 347 (削除ここまで)

p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'

Any language better suited for handling matrix and determinant should score better (APL, J, CJAM, Jelly)

References: General form of a conic, Five points determine a conic, System of linear equations, Determinant

In the cartesian plane, the general equation of a conic is

A*x*x + B*x*y + C*y*y + D*x + E*y + F = 0 

having A or B or C not equal to 0 (otherwise it's a straight line)

A ... F are six unknowns to be found. With five pairs of (x,y) we can build a linear system with five equations, and scaling remove one dimension. That is, we can set one of A,B or C to 1 if it's not 0 (and we know that at least one is not 0).

I build and try to solve 3 systems: first trying A=1. If not solvable then B=1, then C. (There could be a better way, but that's my best at the time)

Having the values of A,B,C we can classify the conic looking at the discriminant d=B*B-4*A*C

• d == 0 -> parabola
• d> 0 -> hyperbola
• d < 0 -> ellipse, particularly (A == C and B == 0) -> circle

Less golfed

F=p=>(
 // Recursive function to find determinant of a square matrix
 D=m=>m[1]
 ?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0)
 :m,
 // Try 3 linear systems, coefficients in Q
 // Five equation made from the paramaters in p
 // And a first equation with coefficient like k,0,0,0,0,0,1 (example for A) 
 [1,2,4].some(
 x => (
 // matrix to calc the determinant, last coefficient is missing at this stage
 Q = [ 
 [x&1, x&2, x&4, 0,0,0] // first one is different
 // all other equations built from the params 
 ,...p.map( ([x,y]) => [x*x, x*y, y*y, x, y, 1] )
 ],
 d = D(Q), // here d is the determinant
 d && ( // if solvable then d != 0
 // add missing last coefficient to Q
 // must be != 0 for the first row, must be 0 for the other
 Q.map( r=> (r.push(x), x=0) ),
 // solve the system (Cramer's rule), I get all values for A...F but I just care of a,b,c
 [a,b,c] = Q.map((v,i)=>D(Q.map(r=>(r=[...r],r[i]=r.pop(),r))) / d),
 d = b*b - 4*a*c, // now reuse d for discriminant
 d = d<0 ? !b&c==a ? 'Circle' : 'Ellipse' // now reuse d for end result
 : d ? 'Hyperbola' : 'Parabola'
 ) // exit .some if not 0
 ), d // .some exit with true, the result is in d
 ) 
)

Test

F=p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'
console.log=(...x)=>O.textContent+=x+'\n'
;[
 [[0, 0], [1, 5], [2, 3], [4, 8], [9, 2]]
,[[1.2, 5.3],[4.1, 5.6], [9.1, 2.5], [0, 1], [4.2, 0]]
,[[5, 0], [4, 3], [3, 4], [0, 5], [0, -5]]
,[[1, 0], [0, 1], [2, 1], [3, 4], [4, 9]]
].forEach(t=>console.log(t.join`|`+' => '+F(t)))

<pre id=O></pre>

• Alex A.: This is really nice! Excellent work!

Answer 2

C, 500

My JavaScript answer ported to C. Just to see if it can be done.

Usage: read 10 values from standard input

echo 1 0 0 1 2 1 3 4 4 9 | conic

Output:

Parabola

Test (ideone)

double D(m,k)double*m;{double t=0;for(int s=1,b=1,x=0;x<6;x++,b+=b)k&b||(t+=s*m[x]*(k+b>62?1:D(m+6,k+b)),s=-s);return t;}i,u,h;double m[36],*t=m+6,w[6],s[3],b,d;main(){for(;i++<5;*t++=d*d,*t++=d*b,*t++=b*b,*t++=d,*t++=b,*t++=1)scanf("%lf%lf",&d,&b);for(u=4;u;u/=2)for(m[0]=u&1,m[1]=u&2,m[2]=u&4,d=D(m,0),h=0;d&&h<3;h++){for(i=0;i<6;i++)w[i]=m[i*6+h],m[i*6+h]=i?0:u;s[h]=D(m,0)/d;for(;i--;)m[i*6+h]=w[i];}b=s[1];d=b*b-4*s[0]*s[2];puts(d?d<0?!b&(s[2]==s[0])?"Circle":"Ellipse":"Hyperbola":"Parabola");}

Less golfed

// Calc determinant of a matrix of side d
// In the golfed code, d is fix to 6
double D(m, d, k)
double*m;
{
 int s = 1, b = 1, x = 0;
 double t = 0;
 for (; x < d; x++, b += b)
 k&b || (
 t += s*m[x] *(k+b+1==1<<d? 1: D( m + d, d, k + b)), s = -s
 );
 return t;
}
double m[36],d, *t = m + 6, w[6], s[3], a, b, c;
i,u,h;
main()
{
 for (; i++ < 5; )
 {
 scanf("%lf%lf", &a, &b);
 *t++ = a*a, *t++ = a*b, *t++ = b*b, *t++ = a, *t++ = b, *t++ = 1;
 }
 for (u = 4; u; u /= 2)
 {
 m[0] = u & 1, m[1] = u & 2, m[2] = u & 4;
 d = D(m, 6, 0);
 if (d) 
 for (h = 0; h < 3; h++)
 {
 for (i = 0; i < 6; i++)
 w[i] = m[i * 6 + h],
 m[i * 6 + h] = i ? 0 : u;
 s[h] = D(m, 6, 0)/d;
 for (; i--; )
 m[i * 6 + h] = w[i];
 }
 }
 a = s[0], b = s[1], c = s[2];
 d = b*b - 4 * a * c;
 puts(d ? d < 0 ? !b&(c == a) ? "Circle" : "Ellipse" : "Hyperbola" : "Parabola");
}

Answer 3

Sage, 247 bytes

def f(p):
 for i in[1,2,4]:
 z=[i&1,i&2,i&4,0,0,0]
 M=matrix([z]+[[x*x,x*y,y*y,x,y,1]for x,y in p])
 try:A,B,C=(M\vector(z))[:3]
 except:continue
 d=B*B-4*A*C
 return['parabola','hyperbola','circle','ellipse'][[d==0,d>0,d<0and B==0and A==C,d<0].index(1)]

Try it online

This function takes an iterable of (x,y) pairs as input, tries computing the discriminant of each of the 3 possible linear systems (A=1, B=1, and C=1), and outputs the type of conic section based on the values of the discriminant, A, B, and C.

There's probably some more golfing to be done, but I'm rusty with Sage and sleepy right now, so I'll work on it more in the morning.

Answer 4

Matlab, 154 bytes

p=input();c=null([p.^2 prod(p,2) p 1+p(:,1)*0]),s={'circle' 'ellipse' 'parabola' 'hyperbola'};s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

Saved some bytes thanks to Suever's suggestions.

Takes input as [x1 y1;x2 y2;x3 y3; etc]. This used a Vandermonde matrix, and finds the basis of its null space, which will always be a single vector. Then it calculates the discriminant and uses it to make an index between 1 and 4 which is used to get the string.

Ungolfed:

p=input();
c=null([p.^2 prod(p')' p ones(length(p),1)]);
s={'circle' 'ellipse' 'parabola' 'hyperbola'};
s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

The sign(...) part calculates the discriminant, giving 1 if it's positive (hyperbola), -1 if it's negative (ellipse), and 0 if it's 0 (parabola). The max(...) subtracts 1 away if it is a circle. Matlab arrays are one-indexed, so add 3 to give values 1, 2, 3, 4, and use that to index the array of conic section names.

• Suever: Rather than comparing max() == 0 you can simplify to ~max()
• Suever: Also instead of ones(length(p),1) you could do 1+p(:,1)*0
• David: Cheers, the max() thing was silly of me, I did have comparisons there before and got lazy obviously! That way of getting the ones is very nice too.

Answer 5

Python - 234 bytes

import numpy as n
x=input()
d=[n.linalg.det(n.delete(n.array([[i*i,i*j,j*j,i,j,1]for i,j in x]),k,1))for k in range(6)]
t=d[1]**2-4*d[0]*d[2]
print"hyperbola"if t>0else"parabola"if t==0else"circle"if d[1]==0and d[0]==d[2]else"ellipse"

I never print circle or parabola because t and d[1] never hit exactly 0, but OP said that was okay.

Answer 6

APL(NARS), 153 chars

{M←⊃{⍵,(×ばつ/⍵),⍵*2} ̈q←⍵∼⊂0 0⋄v←5⍴1⋄(M v)←{q≡⍵:M v⋄(0 1↓M)M[;1]}⍵⋄(b c a)← ×ばつ1x⋄(b=0)∧a=c:'circle'⋄0>t←(b*2)×ばつa×ばつc:'ellipse'⋄0<t:'hyperbola'⋄'parabola'}
 

Input should be choosen in the way matrix coefficients is square and its determinat is different of 0.

For me there are 2 cases, case 1 there is no (0 0) in the argument data points, case 2 there is 1 (0 0) in argument data points. The book formula for general conic is below, but I modify something in the hope that not change delta (B^2)×ばつC.

Ax^2+Cy^2+Bxy+Dx+Ey+F=0

For case 1 for build the matrix M I use this formula below, where v=(1 1 1 1 1)

Ax^2+Cy^2+Bxy+Dx+Ey=1

For case 2 for build the matrix M I use this formula below, where v=(y)=(the second coordinate 4 points)

Ax^2+Cy^2+Bxy+Dx =y

For find "A C B" I use ̄3↑v⌹M that would return the last 3 numbers of vector of solution, the ones in the position of B C A. I use rationals in the hope of not have round errors, multipling the matrix M for rational 1 1x, in ×ばつ1x.

test:

 f←{M←⊃{⍵,(×ばつ/⍵),⍵*2} ̈q←⍵∼⊂0 0⋄v←5⍴1⋄(M v)←{q≡⍵:M v⋄(0 1↓M)M[;1]}⍵⋄(b c a)← ×ばつ1x⋄(b=0)∧a=c:'circle'⋄0>t←(b*2)×ばつa×ばつc:'ellipse'⋄0<t:'hyperbola'⋄'parabola'}
 
 f (1 0)(0 1)(0.5 0.5)(0.3 0.7)(4 9)
hyperbola
 f (1.2 5.3)(4.1 5.6)(9.1 2.5)(0 1)(4.2 0)
ellipse
 f (5 0)(4 3)(3 4)(0 5)(0 ̄5)
circle
 f (1 0)(0 1)(2 1)(3 4)(4 9)
parabola
 f ( ̄1 4)(2 2)(6 4)( ̄3 2)(2 5)
ellipse
 f (0 0)(1 5)(2 3)(4 8)(9 2) 
hyperbola
 f (5 9)( ̄4 ̄3)(2 4)(8 13)( ̄1 1)
DOMAIN ERROR
 f (5 9)( ̄4 ̄3)(2 4)(8 13)( ̄1 1)
 ∧