Определите, пересекает ли линейный сегмент многоугольник

Если вам нужна библиотека Python для геометрических операций, обратите внимание на shapely. Это делает это так же просто, как someline.intersects(somepolygon).

Вот быстрый пример пересечений, буфера и отсечения (с красивым сюжетом ... Я использую descartes , чтобы легко преобразовывать красивые многоугольники в патчи matplotlib.).

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()

Это дает:

Blue line intersects clipped shape: True
Green line intersects clipped shape: False

Линия пересекает многоугольник тогда и только тогда, когда пересекает одно из его ребер (игнорируя на секунду случаи, когда она проходит через вершину). Итак, в вашем случае вам просто нужно проверить все края вашего многоугольника относительно вашей линии и посмотреть, есть ли пересечение.

Легко проверить, пересекает ли край (a, b) линию. Просто создайте линейное уравнение для своей линии в следующей форме

Ax + By + C = 0

а затем вычислить значение Ax + By + C для точек a и b. Если знаки этих значений для a и b различаются, то край (a, b) пересекает линию.

Осталось только разработать способ обработки случаев, когда линия проходит через вершину (конечную точку ребра), но это легко сделать.

Если вас не слишком заботит эффективность, вы можете просто проверить пересечение линий с учетом ваших двух контрольных точек и всех смежных пар точек на многоугольнике. Как только вы обнаружите пересечение, вы узнаете, что ваша линия пересекается с многоугольником.

Как всегда, хорошей отправной точкой является википедия: http://en.wikipedia.org/wiki/Line-line_intersection

Итак, давайте рассмотрим пример.

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

И не забывайте циклически перемещаться с помощью (qn, q0), чтобы закрыть поли!

Удачи!

Разве в алгоритме многоугольника нет быстрой точки? Используя одну из них, вы можете определить, находится ли внутри ровно одна из точек, что также может означать пересечение. Если они оба лежат снаружи, по-прежнему требуется один из других методов.