Point me in the right direction with this problem since I have no idea on how to tackle it.You're given 4 set of coordinates in R^3 that form a tetrahedron, then another 4 set of coordinates in R^3 that form another tetrahedron.
How do I find the smallest distance from the surface of one tetrahedron to the other?
One way to do it would be with math.
You write an equation which contains all the points in a tetrahedron, then apply that general equation to 2 hypothetical tetrahedrons (so you have 2 functions). The distance in 3D space is given by another simple formula. Afterwards, you just need to minimize this distance and this can be done using calculus. At least, that's the general idea. Once you have the formula, writing a program is easy enough.
>>4
Okay, fine. Also project vectors for each point onto the plane of the other tetrahedron. And some other stuff.
In fact, just test each point in the 10 voronoi regions for the other tetrahedron.
Name:
Anonymous2010-11-17 19:43
>>2
It's the math portion I'm having trouble with >>3
It can be any point in any of the four faces of the tetrahedron. Not just the vertexes. >>5
Can you elaborate?
>>1
Each tetrahedron has four points, eight edges, and four surfaces. That's sixteen parts per tetrahedron. Write a function to check distance point to point, point to edge, edge to edge, point to surface, and edge to surface. Surface to surface can be ignored since it won't ever give a smaller result than the other five types of tests. That gives 240 possible pairs of parts to check.
>>5
No. This won't work when the shortest path is from one edge to another edge.
1. Calculate distance between centers of tetrahedrons. Call it R
2. Convert everything to voxels
3. From each point of surface run A* search in all directions
4. If A* encounters voxel of another tetrahedron, congratulations!
5. From all found distances choose the smallest
6. If it is slow, buy better servers and reimplement everything in erlang to run this hardest taks across the worldglobe.
Name:
Anonymous2010-11-18 5:24
>>9
The specification I was given requires 2 decimals of precision. Ignoring surface to surface still gives me that precision?
>>10
This is an assignment from Algorithms and Data Structures 2. I have no idea how to implement this. I'm trying to do this using just the stuff I learned in Linear Algebra first semester.
>>11
You've learned linear algebra and you don't even know where to start? It is a bit complex, but you should be able to simplify the problem if you're clever. You only need to worry about the verteces since there are no curved surfaces involved.
Name:
Anonymous2010-11-18 7:12
>>12
My initial idea was to just calculate all the surface to surface distances. Which would give me 16 (4 for each surface) of them and pick the smallest one.
I thought that if I found all the surface to surface that already included all the other combinations since technically the vertexes and edges are part of the plane that contains the surface of the tetrahedron.
But I forgot how to calculate this.
>>13
I agree with >>14 (I wouldn't say 'useless', but unnecessary for sure.) At least one edge will be involved in the set of answers for any scenario dealing with with line segments (surface point to surface point may be a correct answer, but a point on an edge will also definitely satisfy the same answer.)
13th Elul, is the day of the passing of M"R Hakham Yosef Hayyim, zy'a"a, the Ben Ish Hai. When Hakham Yosef Hayyim, 'a"h, was about eight years old, he and his sister were arguing as to who should hold the candle for the Habdalah on Saturday night. Their father, Hakham Eliyahu Hayyim, 'a"h, turned to his young son Yosef and told him that if his reason for holding the candle was for mere pleasure, then his sister should take precedence, because she was the younger one. If, on the other hand, it was because he had a deeper understanding of the meaning of Habdalah, then he could be the one to hold it.