Determine if a line segment intersects a polygon

Question

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 see if any intersect but is there a better way?

I've read this one post How can I determine whether a 2D Point is within a Polygon? which gives me some ideas for seeing whether the point is within a polygon but I need to see if it has passed over/intersected it.

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: True
Green 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:
      if line( p0, p1 ) intersects line( qi, qi+1 ):
          return true
   return false

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

Good luck!

Comments

[ThorSummoner]

Does this work with 3D geometry? (Or even N-denominational geometry?)