corkum@csri.toronto.edu (Brent Thomas Corkum) (01/05/91)
I'm looking for a FAST algorithm for calculating the distance from a point in 3 space to a polygon (not the plane of the polygon) in 3 space. It only need work for convex three noded triangles and four noded quadralaterals. Any ideas or references would be appreciated. Brent Corkum corkum@boulder.civ.toronto.edu
marcc@yoyodyne.ncsa.uiuc.edu (Marc Cooper) (01/05/91)
In article <1991Jan4.131532.3933@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: > > >I'm looking for a FAST algorithm for calculating the distance from a >point in 3 space to a polygon (not the plane of the polygon) in 3 space. >It only need work for convex three noded triangles and four noded >quadralaterals. >corkum@boulder.civ.toronto.edu This seems easy enough, given the simplied case. First, calculate the distance from the point to the polygonal plane. If the intersection point is within the polygon, stop. That is the shortest distance. If the perpendicular dropped from the point to the polygonal plane lies OUTSIDE the polygon, calculate the distance from each vertex of the polygon to the point. Then find the minimum distance between the point and the line segment defined by the two closest vertecies. I don't know how fast this would be. I suppose that depends if you're willing to hack out the calculations in the relevent assembley language or not.. -- Marc Cooper | "In my childhood, I WAS an imaginary playmate." marcc@ncsa.uiuc.edu | -Tom Robbins, EVEN GOWGIRLS GET THE BLUES National Center for Supercomputing Applications Disclaimer: "It's mine! All mine!" -D. Duck
nathan@electro.com (Nathan Konrad) (01/07/91)
In article <1991Jan4.191630.12650@ux1.cso.uiuc.edu> marcc@yoyodyne.ncsa.uiuc.edu (Marc Cooper) writes: >In article <1991Jan4.131532.3933@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: >> >> >>I'm looking for a FAST algorithm for calculating the distance from a >>point in 3 space to a polygon (not the plane of the polygon) in 3 space. >>It only need work for convex three noded triangles and four noded >>quadralaterals. >>corkum@boulder.civ.toronto.edu > >This seems easy enough, given the simplied case. > >First, calculate the distance from the point to the polygonal plane. If the >intersection point is within the polygon, stop. That is the shortest distance. > >If the perpendicular dropped from the point to the polygonal plane lies OUTSIDE >the polygon, calculate the distance from each vertex of the polygon to the >point. Then find the minimum distance between the point and the line segment >defined by the two closest vertecies. The minimum distance between the point and *any* line segment will have to be found, since the end points of the nearest segment may not be the nearest verticies. Consider this example: 1------------2 ---- ---- ---- ---- ---- ---- 4---------------------------------------------------------3 X If X is the nearest point in the plane of the polygon, points 1 and 2 are the nearest verticies but the nearest point lies on the segment between 3 and 4. -- Nathan P. Konrad ...!watmath!watcgl!electro!nathan Electrohome Ltd., Phone: (519) 744-7111 809 Wellington St. N. Fax: (519) 749-3131 Kitchener, ON, N2G 4J6