11275 - 3D Triangles

[sclo]

My algorithm is quite simple, but I keep getting WA.

If the 2 triangles are on parallel planes {
if the planes do not intersect, then return 0
else {
if any pair of line segments between different triangle intersect, return 1
if any triangle is contained in another triangle, return 1
else return 0
}
}
else {
compute L, the line of intersection between the 2 planes.
compute intervals on L where the line segments of the triangle intersects L
if the interval overlaps, then return 1
else return 0
}

What is wrong with my approach? I notice that the acceptance ratio is quite low.

[goodwill]

Actually, the acceptance rate is quite high, but after i got about 10 WAs it began to drop. BTW, i used the same algorithm as yours. My code for this problem is 300 lines. I think it is quite long and small mistakes can appear here and there.

[sclo]

Actually, is there any problem with using epsilons everywhere? I mean, are there any cases where the difference is close to epsilon?

[goodwill]

I used epsilon=1e-6 just like the description said and i used it everywhere. I even used it for the distance between points after i had projected them in some 2D plane. So maybe the epsilon is not so important.

[ImLazy]

My AC code's epsilon is 1e-8.

Your algorithm is right, but notice the problem statement: "if the distance between two points is equal or less than 1e-6, they are regarded as one point". So you should consider these situations:

1. If the distance between one endpoint of triangle A and one edge of triangle B is equal or less than 1e-6, return true.

2. if triangle A's one endpoint's projection on plane B falls inside triangle B, and the endpoint's distance to plane B is equal or less than 1e-6, return true.

And as my test, the situation 1 appears in the test cases, but situation 2 doesn't.

[baodog]

You can test your i/o on this really useful website by Greve.

http://uva.xgd.dk/problemssolve.php


It lets you enter input, and gives you output file.

[SePulTribe]

This question is quite crazy. I've tried many algorithms from Möller to Held to even Guigue but they all took more than 2 seconds and TLEd. I nearly gave up until I tried an algorithm from Hao Shen, Pheng Ann Heng and Zesheng Tang which was the only one which took less than a second to complete. Amazing stuff. I never knew calculating the intersection of two triangles in 3D space would take so much work. Here is an implementation of the algorithm: http://jgt.akpeters.com/papers/ShenHengTang03/
Good luck.