Определить, находится ли точка в многоугольнике или пройдена через

Question

Я пытаюсь выяснить, как лучше всего это сделать, если у меня есть вектор (линия, состоящая из 2 точек) на 2-й плоскости, как я могу определить, прошел ли он через многоугольник?

Я знаю, что могу взять каждую линию, которая составляет многоугольник, и посмотреть, пересекаются ли какие-либо, но есть ли лучший путь?

Я прочитал этот пост Как я могу определить, находится ли 2D-точка внутри многоугольника? , который дает мне некоторые идеи, чтобы увидеть, находится ли точка внутри многоугольника, но мне нужно посмотреть, если это прошел / пересек его.

Меня не особо интересуют технические особенности, я, вероятно, буду внедрять их на python.

Приветствия

David

Answer 1

Если вам нужна библиотека 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

Answer 2

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

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

Ax + By + C = 0

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

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

Answer 3

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

Хорошей отправной точкой, как всегда, является Википедия: 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), чтобы закрыть поли!

Удачи!

Answer 4

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