crds@ncoast.UUCP (Who Am I) (06/27/87)
In a number of articles, a procedure has been described to determine whether a point lies within or outside of a polygon, in three space. I have not read all of the articles on this subject, but I have a solution which I believe works in all cases. Given that you have a planar polygon in three space, and that the plane equation for that polygon is defined as Ax+By+Cz+D=0, and given a point (P,Q,R) in three space which lies on that plane, the solution is fairly trivial. First, reduce the problem into two-space. Determine which axis of the polygon is least significant, flattening both the polygon and the point down to two of the three major axes. Even though this introduces a distortion, the quality of being "inside" or "outside" will remain, as long as the polygon is not flattened to a line. To make sure of this, the decision of which axis to remove is based on the normal to the plane that the polygon lies in, the normal by definition is (A,B,C). Find the greatest value of A, B, and C, and this is the axis to remove (x, y, or z respectively). For sake of discussion lets assume C has the greatest absolute value. This means that the z axis is LEAST significant in the polygon, and therefore can be removed from the problem. All vertices in the polygon are now referenced (for the solution of this problem) by only their x and y coordinates, and the point being tested is now (P,Q). A Prepass phase at this time should determine whether the point (P,Q) lies exactly on a vertex or exactly on a line within the polygon. If this is the case, the point is within the area of the polygon, and further testing is not necessary. Next, translate point (P,Q) to the origin, and translate all points on the polygon as well (this is only for clarity, and can actually be simplified out during the actual test-pass within the program). One "easy-to-test" arbitrary vector is along the positive x-axis, and testing one vector IS sufficient. Moving along our test vector, count the number of intersections with edges of the polygon. For vertex points, there are two distinct cases: Either both of the segments leading to the vertex are on the same side of the test vector (for our translated coordinate system, both have the same y polarity on their second endpoints), or they are both on opposite sides of our test ray (for translated system, they have opposite polarity on their second endpoint). If they are on the same side, count it as 2 intersections, if they are on opposite sides, count it as 1. The only other special case is horizontal lines. Any line lying directly on our test ray must be "skipped", and the line segments attached to both ends of the horizontal line must be treated as if they were connected to each other. Note that since we are only interested in the "y-polarity" of the second endpoints of these segments, their x position is insignificant, and no translation is necessary to handle the special case of a horizontal line. If the resultant count of intersections is even (or 0), we are "outside" of the polygon. If the count is odd, we are "inside". This seems to be a solution that would easily be implemented on any system. Please reply with comments, or if you find a case which I have overlooked. Phone: (614) 263-7118 Glenn A. Emelko, Manager of Technology, Performance Concepts Inc.