Shortest Distance between a vector and a triangle

Started by
1 comment, last by JeroMiya 22 years, 2 months ago
I''m attempting to find the shortest distance from any point on a vector to any point on a triangle in 3D space. I''ve tried a couple methods and haven''t had much luck. I tried finding the shortest distance from a vector to the plane the triangle was on, but that only gave me the shortest distance if that point was inside the triangle. There are also several cases which look differently. For example, one case is if the vector and the triangle intersect. Another case is if the vector intersects the plane the triangle is on but not the triangle. Also, there''s the case where the vector is on the same plane as the triangle, and there''s one case where the vector is on a plane which is parallel to the triangle''s plane. If multiple points on the vector are the same shortest distance from the triangle (from the last two cases), then I need the first point. That is, if I have a vector from point A to point B, then the first point on the vector that is the shortest distance from the vector to the triangle.
Advertisement
It''s too late for me to think too clearly, but since when did that stop me The only comment I can really make at this point is that being in the plane or in a plane parallel is not two seperate cases. You calculate the closest point exactly the same way in both of them. You could form three planes using the normal of the plane containing the triangle and each of the sides of the triangle. That would let you project the triangle into a parallel plane that contains your vector. The closest point to that triangle is also the closest point to the original triangle. So there is no differance between the two.

One thought in the more general case is that you could draw two lines perpendicular to each side of the triangle positioned at each end of the side. If a point is between two lines for a side then it''s distance from the triangle is the distance from that side. If it is outside all of them then its distance is the distance from a vertex and which vertex it is is the one you can get to without crossing any lines. If it wasn''t so late I might actually have some suggestions on how you could use that for this purpose.
Keys to success: Ability, ambition and opportunity.
I wrote some code to do this a while ago, as part of some test code for a v-clip implementation. The goal was to be able to find the precise distance between polyhedron features as v-clip iterated through them, to check it was converging. The code is robust but not at all fast.

I first coded a number of distance routines for points, lines and polygons. These were used to work out the distance between features.

So for a triangle and edge I have an edge-edge distance function to find the shortest distance from the edge to the edges of the triangle. I also do further checks in case either the endpoints are nearer to the triangle face (if so they muat lie in the prism it is a cross section of) or in case the edge crosses the triangle (so the distance is zero).

If you need the point you will need to keep track of it a you go along, e.g. work out the point that is nearest at each step and if the distance is shortest remember the point.

I would be careful of dealing with cases where multiple points are nearest, as for a random 3D line and plane this should be impossible, e.g. it could happen but the probability is zero. In practice it will happen, but very rarely, and it will happen at the point where the limit of floating point accuracy will be significant, making a choice of ''best'' point pretty arbitrary.
John BlackburneProgrammer, The Pitbull Syndicate

This topic is closed to new replies.

Advertisement