A triangle is inside another triangle

Question

Given the lengths of the sides of 2 triangles. Determine if the second triangle can fit into the first triangle?

For more information, see the full description of the problem below:

http://acm.timus.ru/problem.aspx?space=1&num=1566&locale=en

My implementation below tries all (3!) ^ 2 possible combinations of aligning the bases of the triangles. Then he tries to move the second triangle inside the first triangle, checking that the base of the second triangle does not exceed the base of the first triangle.

But I keep getting the wrong answer (WA) No. 16.

The case I gave is the second image. Obviously, if you rotate PQR to align the sides of length 2.77 and 3.0, the third vertex will not be inside the triangle ABC. The side of length 4.2 can only be aligned along side len 5. Thus, this case only occurs when the configuration is displayed in the second image.

Can you help me find the error, suggest some test cases when my algorithm breaks. Alternative algorithms are also welcome.

#include <cmath> #include <iostream> using namespace std; const double PI = atan(1.0)* 4; // Traingle ABC (Envelope) double xa, ya, xb, yb, xc, yc; // Traingle PQR (Postcard) double xp, yp, xq, yq, xr, yr; // Angle between sides AB and AC double theta; double signWrtLine(double x1, double y1, double x2, double y2, double x, double y) { double A = y2 - y1; double B = x1 - x2; double C = -(A * x1 + B * y1); return (A * x + B * y + C); } bool fit() { if ((xr > xc) || (yq > yb)) return false; if (signWrtLine(xa, ya, xb, yb, xq, yq) < 0) { double d = (yq / tan(theta)) - xq; return (xr + d <= xc); } return (signWrtLine(xa, ya, xb, yb, xq, yq) >= 0 && signWrtLine(xb, yb, xc, yc, xq, yq) >= 0 && signWrtLine(xc, yc, xa, ya, xq, yq) >= 0); } bool fit(double a[], double b[]) { // generate the 3! permutations of the envelope // loops i,k for (int i = 0; i < 3; i++) { double angle; double u = a[i], v = a[(i + 1) % 3], w = a[(i + 2) % 3]; for (int k = 0; k < 2; k++) { switch (k) { case 0: xa = 0, ya = 0; angle = theta = acos((u * u + v * v - w * w) / (2 * u * v)); xb = v * cos(angle), yb = v * sin(angle); xc = u, yc = 0; break; case 1: // reflect envelope swap(v, w); angle = theta = acos((u * u + v * v - w * w) / (2 * u * v)); xb = v * cos(angle), yb = v * sin(angle); break; } // generate the 3! permutations of the postcard // loops j,k for (int j = 0; j < 3; j++) { double angle; double u = b[j], v = b[(j + 1) % 3], w = b[(j + 2) % 3]; for (int k = 0; k < 2; k++) { switch (k) { case 0: xp = 0, yp = 0; angle = acos((u * u + v * v - w * w) / (2 * u * v)); xq = v * cos(angle), yq = v * sin(angle); xr = u, yr = 0; break; case 1: // reflect postcard swap(v, w); angle = acos((u * u + v * v - w * w) / (2 * u * v)); xq = v * cos(angle), yq = v * sin(angle); break; } if (fit()) return true; } } } } return false; } int main() { double a[3], b[3]; for (int i = 0; i < 3; i++) cin >> a[i]; for (int i = 0; i < 3; i++) cin >> b[i]; if(fit(a, b)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } 

Answer 1

Use epsilon (1e-10) when comparing doubles!

Answer 2

Barycentric coordinates! More details:

Let the envelope triangle have vertices A, B, C; without loss of generality, you can place vertex A at the origin and align side AB with the + x axis. Use the lengths of the edges of the envelope triangle to find the angle at vertex A, that is, the angle between sides AB and AC. Using this angle, you define a new coordinate system (u, v); in this coordinate system, the vertex coordinates A = (0,0), B = (1,0) and C = (0,1).

Now take another triangle with vertices A ', B', C 'and first find the XY coordinates of the three vertices for each case: (A'B', B'C ', A'C') aligned with the + x coordinate axis. For each such alignment, transform the other two vertices into a UV coordinate system defined by the envelope triangle. If it happens that both other vertices have (u, v) coordinates with 0 <= u, v <= 1 with u + v <= 1, the triangle is placed in the envelope triangle.

The angle between the two sides can be obtained through the sine theorem for plane triangles; although you should be a little careful if the angle at the vertex is obtuse (> PI / 2), since the sinusoidal function is symmetrical around PI / 2 on the interval [0, PI]. To check if the angle is obtuse, you also need to use the cosine theorem, although you do not need to calculate the cosine itself: if | AB | ^ 2 + | AC | ^ 2> | BC | ^ 2, the angle at A is obtuse.

I think this sums it up.

Answer 3

 //23/08/11 13:56 //determine if a triangle will fit inside a second triangle #include<iostream> #include<cmath> #include<algorithm> using namespace std; const double pi= 3.1414926; const double tri=180;//deg in triangle double find_B_ang(double a,double b,double c); double find_C_ang(double a,double b,double c); double movetri_r , tc_ghosthor_B; int main() {double a=0.0,b=0.0,c=0.0,x=0.0,y=0.0,z=0.0; double A=0.0,B=0.0,C=0.0,A1=0.0,B1=0.0,C1=0.0;// L&R base angles double te_vert_B=0.0,te_hor_B=0.0,te_hor_C=0.0; double tc_vert_B=0.0,tc_hor_B=0.0,tc_hor_C=0.0; //points B and B1 are considered co-incedent cout<<"\n\ndetermine if a triangular card will fit inside\n" <<"a triangular envelope\n"; //envelope dimensions cout<<"\nenter lengths of the sides of envelope (space between)\n"; cout<<"ensure longest of them is less than sum of other two\n"; do { cin>>a>>b>>c;//the e sides if(c>a)swap(a,c);//sort sides in decending order if(b>a)swap(a,b); if(c>b)swap(b,c); if(a >(b+c)) cout<<"WRONG...b+c must be greater than a"; }while(a >(b+c)); cout<<"\nthe sides of the envelope are "<<a<<','<<b<<','<<c<<endl; B=find_B_ang(a,b,c); C=find_C_ang(a,b,c); te_vert_B=c*sin(B*pi/tri);//apex to base vertical line te_hor_B=te_vert_B/tan(B*pi/tri);//B to vertical line te_hor_C=a-te_hor_B;//C to vertical line cout<<"-------------------------------------------\n"; //card dimensions do { cout<<"\nenter lengths of sides of card (space between) \n"; cout<<"ensure longest of them is less than sum of other two\n"; do { cin>>x>>y>>z;//the c sides if(z>x)swap(z,x);//sort sides in decending order if(y>x)swap(y,x); if(z>y)swap(y,z); if(x>(y+z)) cout<<"WRONG...y+z must be greater than x\n"; }while(x>(y+z)); cout<<"\nthe sides of card are "<<x<<','<<y<<','<<z<<endl;//x is base B1=find_B_ang(x,y,z); C1=find_C_ang(x,y,z); tc_vert_B=z*sin(B1*pi/tri);//apex to base vertical line tc_hor_B=tc_vert_B/tan(B1*pi/tri);//B to vertical line tc_hor_C=x-tc_hor_B;//C to vertical line tc_ghosthor_B=tc_vert_B/tan(B*pi/tri); movetri_r= abs(tc_ghosthor_B-tc_hor_B); cout<<"------------------------------------------------\n"; //determine and advise if card fits within envelope if(B1<B && tc_vert_B <(tc_hor_C + ax)*tan(C*pi/tri))cout<<"\ntrue"; else if(B1<B && tc_hor_B< te_hor_B && tc_vert_B<te_vert_B)cout<<"true"; else if(B1>B && movetri_r<ax && tc_vert_B<te_vert_B)cout<<"true"; else cout<<"\nfalse"; } while(x>0); cout<<"\npress any key..."; cin.ignore(); cin.get(); return 0; } double find_B_ang(double a,double b,double c) { double X=0.0; X=((a*a)+(c*c)-(b*b)); X/=2*a*c; X=acos(X); X*=tri/pi; return X; //degrees } double find_C_ang(double a,double b,double c) { double X=0.0; X=((a*a)+(b*b)-(c*c)); X/=2*a*b; X=acos(X); X*=tri/pi; return X;//degrees } 

Answer 4

You can try from here - http://www.springerlink.com/content/t10266u5832477w7/ . It seems that the problem has not yet been solved, so it is best to go with some heuristics to get simple cases (for example, checks for inscribed / restricted circles, border alignment, etc.) and hope for the best.