Determine If A Line Segment Intersects A Polygon

If I have a vector (a line consisting of 2 points) on a 2D plane how can I determine if it has passed through a polygon? I know I can take each line which makes up the polygon and

Solution 1:

If you want a python library for geometric operations, have a look at shapely. It makes this as simple as someline.intersects(somepolygon).

Here's a quick example of intersections, buffer, and clipping (with a nice plot... I'm using descartes to easily convert shapely polygons into matplotlib patches.).

import numpy as np
import matplotlib.pyplot as plt
import shapely.geometry
import descartes

circle = shapely.geometry.Point(5.0, 0.0).buffer(10.0)
clip_poly = shapely.geometry.Polygon([[-9.5, -2], [2, 2], [3, 4], [-1, 3]])
clipped_shape = circle.difference(clip_poly)

line = shapely.geometry.LineString([[-10, -5], [15, 5]])
line2 = shapely.geometry.LineString([[-10, -5], [-5, 0], [2, 3]])

print'Blue line intersects clipped shape:', line.intersects(clipped_shape)
print'Green line intersects clipped shape:', line2.intersects(clipped_shape)

fig = plt.figure()
ax = fig.add_subplot(111)

ax.plot(*np.array(line).T, color='blue', linewidth=3, solid_capstyle='round')
ax.plot(*np.array(line2).T, color='green', linewidth=3, solid_capstyle='round')
ax.add_patch(descartes.PolygonPatch(clipped_shape, fc='blue', alpha=0.5))
ax.axis('equal')

plt.show()

This yields:

Blue line intersects clipped shape:TrueGreen line intersects clipped shape:False

Solution 2:

Line crosses the polygon if and only if it crosses one of its edges (ignoring for a second the cases when it passes through a vertex). So, in your case you just need to test all edges of your polygon against your line and see if there's an intersection.

It is easy to test whether an edge (a, b) intersects a line. Just build a line equation for your line in the following form

Ax + By + C = 0

and then calculate the value Ax + By + C for points a and b. If the signs of theses values for a and b are different, then edge (a, b) intersects the line.

All that's left is to work out a way to handle the cases when the line passes through a vertex (endpoint of an edge), but it is easy to do.

Solution 3:

If you don't care too much about efficiency, you can simply test for line intersection given your two reference points and all adjacent point pairs on the polygon. Once you detect an intersection, you know that your line intersects with the polygon.

A good starting point is, as always, wikipedia: http://en.wikipedia.org/wiki/Line-line_intersection

So, lets run through an example

function line-polygon_intersection:
   Given points p0, p1 on plane P(your reference line)
   Given points q0..qn on plane P(the polygon)
   foreach ( qi, qi+1 ) pair of adjacent points:
      ifline( p0, p1 ) intersects line( qi, qi+1 ):
          returntruereturnfalse

And don't forget to cycle around with ( qn, q0 ) to close the poly!

Good luck!

Solution 4:

Isn't there a quick is point in polygon algorithm? Using one, you could determine if exactly one of the points is inside, which might also means intersection. If they both lie outside, one of the other methods is still required.