Newsgroups: comp.graphics
Path: utzoo!utgpu!watserv1!watcgl!electro.com!nathan
From: nathan@electro.com (Nathan Konrad)
Subject: Re: Distance from Point to a Polygon? (Algorithm wanted)
Message-ID: <1991Jan7.141024.5326@electro.com>
Keywords: polygon point distance
Reply-To: nathan@electro.UUCP (Nathan Konrad)
Organization: Electrohome Ltd., Kitchener, ON
References: <1991Jan4.131532.3933@jarvis.csri.toronto.edu> <1991Jan4.191630.12650@ux1.cso.uiuc.edu>
Date: Mon, 7 Jan 91 14:10:24 GMT

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