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

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>

Answer 2

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.

Answer 3

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 4

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 5

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.