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/