The centers of a triangle

13

1

Circles and squares have a single, definite center point. However, the notion of the center of a triangle has long been discussed. Four different centers were known to the Ancient Greeks:

  • Incenter: The intersection of the angle bisectors of the triangle
  • Centroid: The intersection of the lines from each vertex of the triangle to the middle of its opposite side
  • Circumcenter: The intersection of the perpendicular bisectors of the sides
  • Orthocenter: The intersection of the altitudes of the triangle

Euler later proved that the centroid, circumcenter and orthocenter are collinear in any triangle. The line that these three points are on in a triangle is called the Euler Line. It is defined for every triangle except an equilateral triangle, where all the points coincide.

Your challenge is to create the shortest program or function that, when given two inputs, outputs a specific center or the Euler Line of the triangle. The first specifies the coordinates of each vertex of a triangle. The second is an integer from 1 to 5, determining what to output.

1 - Incenter
2 - Centroid
3 - Circumcenter
4 - Orthocenter
5 - Equation of Euler Line
    (if the Euler Line is vertical, output the `x` value of the line
      (e.g. output `5` if the equation of the line is `x = 5`))

You may assume that the given vertices will never be collinear, and that they will always be integer coordinates (this also excludes the possibility of having an equilateral triangle as an input, as per @R.Kap's comment).

The input array should be a valid nested array in your language, and input should be in any reasonable format. Any float values should be displayed to at least 3 decimal places, but no less. An outputted point should be a valid array in your language, matching with the input format.


Test cases:

Input: [(-2, 0), (1, 0), (0, 1)] 1
Output: (-0.089, 0.451)

Input: [(-2, 0), (1, 0), (0, 1)] 2
Output: (-0.333, 0.333)

Input: [(-2, 0), (1, 0), (0, 1)] 3
Output: (-0.5, -0.5)

Input: [(-2, 0), (1, 0), (0, 1)] 4
Output: (0, 2)

Input: [(-2, 0), (1, 0), (0, 1)] 5
Output: 5x + 2

Clarification: The input can either be from stdin, either space or new-line separated, or as the arguments to a function. The output, however, must be written to stdout.

Volatility

Posted 2013-05-25T01:58:37.823

Reputation: 3 206

Can you please tell me how you can possibly create an equilateral triangle with only integer coordinates? – R. Kap – 2016-05-23T04:32:46.723

1You may either want to make it that the input can be floating point coordinates, or completely get rid of (if the triangle is equilateral, output the point at which the centers meet) as it is not possible to create an equilateral triangle on the coordinate plane using only integer coordinates. – R. Kap – 2016-05-23T05:36:36.210

@R.Kap thanks for pointing that out. Edited. – Volatility – 2016-05-24T01:15:39.553

1

I'm afraid explicit formulas for the circumcenter and orthocenter in cartesian coordinates are pretty ugly. If I go the way of creating a general trilinear/barycentric => carthesian coordinates, the incenter drops out almost free. See http://en.wikipedia.org/wiki/Trilinear_coordinates#Examples. Do I get extra points for implementing it?

– John Dvorak – 2013-05-25T06:43:45.167

What are the valid output formats for the Euler line? If it is vertical, it cannot be expressed as y=f(x). – John Dvorak – 2013-05-25T06:46:44.043

1(please comment if you disagree) Please use the sandbox if you are not sure if a challenge is ok or not. There you can ask for comments and refine the question until it fits. Once posted here it shouldn't be changed with regards to content. Several people might already work on it - and don't like moving targets. – Howard – 2013-05-25T06:53:36.627

@Howard fixed now, apparently I didn't realise there was a simple formula for it [the incenter]. – Volatility – 2013-05-25T07:32:31.480

@JanDvorak No. Also, I've edited the challenge details - see them. – Volatility – 2013-05-25T07:34:13.237

1"When outputting a point, the coordinates must be... surrounded in round brackets (())". Why this requirement? In some languages, points are represented in curly brackets. And something like (12, -2) can only be represented as a string, in which case the elements themselves are interpreted as strings rather than numbers. – DavidC – 2013-05-25T13:20:45.573

@DavidCarraher I have changed the output format to be a little more lax. Do note though that I have said that "The input array should be a valid nested array in your language". – Volatility – 2013-05-25T13:32:45.163

You forgot one(or should I say 3?). Excenters. – Matthew Roh – 2017-03-11T01:49:48.533

I'm unclear - do you expect the input to be read from a textual input (stdin, say), and parsed by the program? Or is the program a function that takes "valid nested array", but prints the result rather than returns a result? – MtnViewMark – 2013-12-23T00:40:22.350

@MtnViewMark either is fine; see the edit. – Volatility – 2013-12-23T02:25:29.237

Answers

2

Python - 908 870

Newlines were added to reduce scrolling. This could probably be golfed further.

from math import*;t=eval(input());p=int(input())-1;
r=[];A,B,C=t[0],t[1],t[2];
a,b,c=hypot(B[0]-C[0],B[1]-C[1]),hypot(A[0]-C[0],A[1]-C[1]),hypot(A[0]-B[0],A[1]-B[1]);
r.append(((a*A[0]+b*B[0]+c*C[0])/(a+b+c),(a*A[1]+b*B[1]+c*C[1])/(a+b+c)));
r.append(((A[0]+B[0]+C[0])/3,(A[1]+B[1]+C[1])/3));d,e,f=(0,0),(B[0]-A[0],B[1]-A[1]),(C[0]-A[0],C[1]-A[1]);g=2*(e[0]*f[1]-e[1]*f[0]);
r.append(((f[1]*(e[0]**2+e[1]**2)-e[1]*(f[0]**2+f[1]**2))/g+A[0],(e[0]*(f[0]**2+f[1]**2)- f[0]*(e[0]**2+e[1]**2))/g+A[1]));
h=acos((b*b+c*c-a*a)/(2*b*c));i=acos((a*a+c*c-b*b)/(2*a*c));j=acos((a*a+b*b- c*c)/(2*a*b));k=cos(i)*cos(j);
l=cos(h)*cos(j);m=cos(h)*cos(i);r.append(((a*k*A[0]+b*l*B[0]+c*m*C[0])/(a*k+b*l+c*m),(a*k*A[1]+b*l*B[1]+c*m*C[1])/(a*k+b*l+c*m)));
n,o=r[1][0]-r[2][0],r[1][1]-r[2][1];q=r[1][1]-o/n*r[1][0]if n!=0 else 0;
r.append(r[1]if a==b==c else("x="+str(r[1][0])if n==0 else"".join([str(o/n),"x+(",str(q),")"])));print(r[p])

Test cases (annotated):

Input: [(-2, 0), (1, 0), (0, 1)]
1
Output: (-0.08907279243665268, 0.45110872103880023) --> More digits than in question

Input: [(-2, 0), (1, 0), (0, 1)]
2
Output: (-0.3333333333333333, 0.3333333333333333) --> More digits than in question

Input: [(-2, 0), (1, 0), (0, 1)]
3
Output: (-0.5, -0.5)

Input: [(-2, 0), (1, 0), (0, 1)]
4
Output: (-1.1702778228588997e-16, 1.9999999999999984) --> More digits than shown in question

Input: [(-2, 0), (1, 0), (0, 1)]
5
Output: 4.999999999999999x+(1.9999999999999996) --> More digits than in question

As you can see, there are possibly errors caused by using floating point.


Further golfing:

Based on suggestions in the comments below, I've managed to make this smaller.

from math import*;I=input;t=eval(I());p=int(I())-1;r=[];A,B,C=t[0],t[1],t[2];R,H,D,S,T=r.append,hypot,cos,acos,str;a,b,c=H(B[0]-C[0],B[1]-C[1]),H(A[0]-C[0],A[1]-C[1]),H(A[0]-B[0],A[1]-B[1]);R(((a*A[0]+b*B[0]+c*C[0])/(a+b+c),(a*A[1]+b*B[1]+c*C[1])/(a+b+c)));R(((A[0]+B[0]+C[0])/3,(A[1]+B[1]+C[1])/3));d,e,f=(0,0),(B[0]-A[0],B[1]-A[1]),(C[0]-A[0],C[1]-A[1]);g=2*(e[0]*f[1]-e[1]*f[0]);R(((f[1]*(e[0]**2+e[1]**2)-e[1]*(f[0]**2+f[1]**2))/g+A[0],(e[0]*(f[0]**2+f[1]**2)-f[0]*(e[0]**2+e[1]**2))/g+A[1]));h=S((b*b+c*c-a*a)/(2*b*c));i=S((a*a+c*c-b*b)/(2*a*c));j=S((a*a+b*b-c*c)/(2*a*b));k=D(i)*D(j);l=D(h)*D(j);m=D(h)*D(i);R(((a*k*A[0]+b*l*B[0]+c*m*C[0])/(a*k+b*l+c*m),(a*k*A[1]+b*l*B[1]+c*m*C[1])/(a*k+b*l+c*m)));n,o=r[1][0]-r[2][0],r[1][1]-r[2][1];q=r[1][1]-o/n*r[1][0]if n!=0else 0;R(r[1]if a==b==c else("x="+T(r[1][0])if n==0else"".join([T(o/n),"x+(",T(q),")"])));print(r[p])

golfer9338

Posted 2013-05-25T01:58:37.823

Reputation: 411

I think it's actually 907 bytes. (URL shortened). – Erik the Outgolfer – 2017-01-14T20:43:03.633

1Could you do something like R=r.append and then use that throughout to save bytes? – FlipTack – 2017-01-14T22:19:38.970

1

AutoHotkey - 731

f(z, r:=1){
static 1:="i",2:="m",3:="c",4:="o"
r := %r%,mx :=(z.1.1+z.2.1+z.3.1)/3,my:=(z.1.2+z.2.2+z.3.2)/3
s:=(c:=sqrt((z.2.1-z.1.1)**2+(z.2.2-z.1.2)**2))+(a:=sqrt((z.3.1-z.2.1)**2+(z.3.2-z.2.2)**2))+(b:=sqrt((z.3.1-z.1.1)**2+(z.3.2-z.1.2)**2))
ix:=(a*z.1.1+b*z.2.1+c*z.3.1)/s,iy:=(a*z.1.2+b*z.2.2+c*z.3.2)/s
midx_a:=(z.3.1+z.2.1)/2,midy_a:=(z.3.2+z.2.2)/2,m:=-1*(z.3.1-z.2.1)/(z.3.2-z.2.2),cc_a:=midy_a-(m*midx_a)
midx_b:=(z.3.1+z.1.1)/2,midy_b:=(z.3.2+z.1.2)/2,n:=-1*(z.3.1-z.1.1)/(z.3.2-z.1.2),cc_b:=midy_b-(n*midx_b)
cx:=(cc_b-cc_a)/(m-n),cy:=cc_a+(m*cx),oc_a:=z.1.2-(m*z.1.1),oc_b:=z.2.2-(n*z.2.1),ox:=(oc_a-oc_b)/(n-m),oy:=oc_a+(m*ox)
if r in m,i,c,o
return [%r%x, %r%y]
else return "y=" (m:=(oy-cy)/(ox-cx)) "x+" oy-m*ox
}

The function can be more minified (to about 600 chars OR less) by shortening the variable names like midx_a, midx_b and so.

Calling the function

d:=f([[-2, 0], [1, 0], [0, 1]], 1)
for k,v in d
    msgbox % k "`n" v

Avi

Posted 2013-05-25T01:58:37.823

Reputation: 261

1

Python 3.5, 851 772 bytes:

def H(z,a,b,l):c=complex;T=lambda A,B:abs(c(*A)-c(*B));d=T(z,a);e=T(z,b);f=T(a,b);g=[((a[0]+b[0])/2,(a[1]+b[1])/2)for a,b in[[a,b],[z,a],[b,z]]];E=(z[0]+a[0]+b[0])/3;F=(z[1]+a[1]+b[1])/3;m=lambda f:[(a,0)if(b[1][0]-b[0][0])==0else(a,-1/((b[1][1]-b[0][1])/(b[1][0]-b[0][0])))if(b[1][1]-b[0][1])else''for a,b in zip(f,[[a,b],[z,a],[b,z]])];i=[u for u in m(g)if u!=''];C=i[0][1];D=i[0][0][1]-(C*i[0][0][0]);A=i[1][1];B=i[1][0][1]-(A*i[1][0][0]);G=(B-D)/(C-A);H=C*G+D;j=[u for u in m([z,b,a])if u!=''];C=j[0][1];D=j[0][0][1]-(C*j[0][0][0]);A=j[1][1];B=j[1][0][1]-(A*j[1][0][0]);I=(B-D)/(C-A);J=C*I+D;K,L=[((d*b[o])+(e*a[o])+(f*z[o]))/sum([d,e,f])for o in[0,1]];a=(H-J)/(G-I)if(G-I)else'';b=H-(a*G)if a!=''else G;print(['',(K,L),(E,F),(G,H),(I,J),[b,'%sx+%s'%(a,b)][a!='']][l])

Takes input as a sequence of comma separated coordinates followed by an integer conveying what to output. For instance, if the input coordinates are (1,0),(2,1),(1,4) and you want the orthocenter of the triangle corresponding to those coordinates you would simply call the function like so:

H((1,0),(2,1),(1,4),4)

Outputs in the format of a tuple if a specific point is needed, in the format of a string with the equation in the form y=mx+b if the Euler line is needed and the line is not vertical, or simply the x value of the line if the Euler line is needed but the line is vertical.

So, using the triangle with vertices (1,0),(2,1),(1,4), the outputs would be:

1. Incenter: (1.4663911961440428, 1.125967951102358)
2. Centroid: (1.3333333333333333, 1.6666666666666667)
3. Circumcenter: (0.0, 2.0)
4. Orthocenter: (4.0, 1.0)
5. Euler Line: -0.25x+2.0 

I will try to golf this more over time where and when I can.

Try It Online! (Ideone)

R. Kap

Posted 2013-05-25T01:58:37.823

Reputation: 4 730