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