Lines Intersecting Polygons
Date: 03/23/98 at 10:50:59 From: Rhandy Lado Subject: Check if line intersects polygons I have an interesting problem that I do not know how to solve and I was wondering if maybe you could point me in the right direction. I have two points (x1, y1) and (x2, y2) and between these points lie polygons (some may overlap). If I draw a straight line between the two points, how do I check which polygons are crossed by the line? The real life scenario for this question is that on a map we have two points with certain highlighted areas (polygons) that may represent types of vegetation or something, and I need to know which of these areas are crossed by a line connecting the two points. Thanks you for any help you can provide. Sincerely, Rhandy Lado
Date: 03/23/98 at 14:48:07 From: Doctor Rob Subject: Re: Check if line intersects polygons The equation of the line is (y-y1)/(x-x1) = (y2-y1)/(x2-x1) (y2-y1)*x - (x2-x1)*y = x1*y2 - x2*y1 A*x + B*y = C All the points (x,y) satisfying A*x + B*y < C lie on one side of the line, and all the points satisfying A*x + B*y > C lie on the other side of the line. To see if the line intersects a polygon, make the test for each vertex of the polygon. If all are on one side of the line, there is no intersection. If you can find two vertices on opposite sides of the line, there is an intersection. -Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Date: 03/30/98 at 00:33:23 From: Rhandy Lado Subject: Re: Check if line intersects polygons Dr. Rob, this works great but there is one situation where it doesn't work: If the line connecting the two points is outside the polygon (i.e. no intersection) but still in a position so that there are polygon vertices on either side, the formula indicates that the line crosses the polygon when really it doesn't. Hope you can provide me some help on this one. Thanks in advance, Rhandy Lado
Date: 03/30/98 From: Doctor Rob Subject: Re: Check if line intersects polygons You talked about a line (i.e., extending to infinity in both directions) when you, in fact, meant a line segment (the part of a line between two points on it). You also did say (check it out above) that the polygons lie *between* the two points. In either situation as described by you, your exceptional case cannot occur. To tell whether two line *segments* intersect, you need to make two tests. You need the endpoints of *each* line segment to be on opposite sides of the other line. So compute the equations of the line L connecting (x1,y1) and (x2,y2) and of all the polygon edges. Then for each edge, test (as above) that the vertices lie on opposite sides of L, and that (x1,y1) and (x2,y2) lie on opposite sides of the polygon edge extended. If both tests are satisfied, then the line segments intersect, but if either fails, then they do not. -Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.