Associated Topics || Dr. Math Home || Search Dr. Math

### Lines Intersecting Polygons

```
Date: 03/23/98 at 10:50:59
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.

Sincerely,
```

```
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
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.

```

```
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/
```
Associated Topics:
High School Basic Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search