CODEWITHSUNDEEP
pythongeometrypolygon
David Bramer
David Bramer

Reputation: 71

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

Upvotes: 7

Views: 22968

Answers (5)

Twistios_Player
Twistios_Player

Reputation: 444

This answer is based on an answer by Joe Kington to this question. I have modified the code such that it is working with Python 3. There also was the problem that the current implementation of shaply/numpy/matplotlib is not compatible with the code. There also was another problem with descartes. This version does not depend on descartes. I have tried to reproduce the same look.

# https://stackoverflow.com/questions/6050392/determine-if-a-line-segment-intersects-a-polygon
# modified for python 3, incl. fixes
import numpy as np
import matplotlib.pyplot as plt
import shapely.geometry

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.coords.xy), color='blue', linewidth=3, solid_capstyle='round')
ax.plot(*np.array(line2.coords.xy), color='green', linewidth=3, solid_capstyle='round')
plt.fill(*np.array(clipped_shape.boundary.coords.xy), facecolor=(0.49,0.49,1), edgecolor=(0.49,0.49,1), linewidth=3)
ax.axis('equal')

plt.show()

Upvotes: 0

Joe Kington
Joe Kington

Reputation: 284602

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

enter image description here

Upvotes: 22

karmakaze
karmakaze

Reputation: 36134

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.

Upvotes: 0

AnT stands with Russia
AnT stands with Russia

Reputation: 320481

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.

Upvotes: 3

dusktreader
dusktreader

Reputation: 4055

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!

Upvotes: 2

Related Questions