Определите, находится ли точка в полигоне или пройдена
Я пытаюсь выяснить, как это сделать, если у меня есть вектор (строка, состоящая из 2 точек) на 2d-плоскости, как я могу определить, прошел ли он через многоугольник?
Я знаю, что могу взять каждую строку, которая составляет многоугольник, и посмотреть, пересекаются ли они, но есть ли лучший способ?
Я прочитал этот пост. Как определить, находится ли 2D-точка внутри многоугольника? который дает мне некоторые идеи для того, чтобы увидеть, находится ли точка в полигоне, но мне нужно проверить, переместила ли она ее / пересекла ее.
Я не очень интересуюсь спецификой технологии, я, вероятно, буду реализовывать в python.
ура
Дэвид
- Найти эквидистантные точки между двумя координатами
- Несоответствие результатов между cv.MinAreaRect2 и ArcGIS (программное обеспечение ГИС). Возможная ошибка?
- Как равномерно распределить окружность эллипса?
- Как проверить, эффективно ли декартовы координаты прямоугольника?
- Пересечения 3D-полигонов в python
Если вы хотите использовать библиотеку 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), чтобы закрыть poly!
Удачи!
Разве нет быстрой точки в алгоритме полигонов? Используя один, вы можете определить, находится ли одна из точек внутри, что также может означать пересечение. Если они оба лежат снаружи, все еще требуется один из других методов.