Как я могу проверить, пересекаются ли два сегмента?

Question

Как проверить, пересекаются ли 2 сегмента?

У меня есть следующие данные:

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ] 

Мне нужно написать небольшой алгоритм на python, чтобы определить, пересекаются ли две линии.

Обновление:

Answer 1

Пользователь @ i_4_got указывает на эту страницу с очень эффективным решением на Python.Я воспроизвожу это здесь для удобства (так как это сделало бы меня счастливым иметь это здесь):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

Answer 2

Уравнение линии:

f(x) = A*x + b = y

Для сегмента он точно такой же, за исключением того, что x включен в интервал I.

Если у вас есть два сегмента, определенные следующим образом:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

Абсцесс Xa потенциальной точки пересечения (Xa, Ya) должен содержаться в обоих интервалах I1 и I2, определяемых следующим образом:

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

И мы можем сказать, что Ха входит в:

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Теперь нам нужно проверить, существует ли этот интервал Ia:

if (max(X1,X2) < min(X3,X4))
    return false; // There is no mutual abcisses

Итак, у нас есть две строки формулы и взаимный интервал. Ваши формулы строки:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

Поскольку мы получили две точки по сегментам, мы можем определить A1, A2, b1 и b2:

A1 = (Y1-Y2)/(X1-X2) // Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4) // Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

Если сегменты параллельны, то A1 == A2:

if (A1 == A2)
    return false; // Parallel segments

Точка (Xa, Ya), стоящая на обеих линиях, должна проверить обе формулы f1 и f2:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2) // Once again, pay attention to not dividing by zero

Последнее, что нужно сделать, это проверить, что Xa включен в Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) ||
     (Xa > min( max(X1,X2), max(X3,X4) )) )
    return false; // intersection is out of bound
else
    return true;

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

Answer 3

Вам не нужно точно вычислять , где пересекает сегменты, но понимает только , пересекаются ли вообще.Это упростит решение.

Идея состоит в том, чтобы рассматривать один сегмент как «якорь» и разделять второй сегмент на 2 точки.
Теперь вам нужно найти относительное положение каждой точки, чтобы«привязанный» сегмент (OnLeft, OnRight или Collinear).
После этого для обеих точек убедитесь, что одна из точек - OnLeft, а другая - OnRight (или, возможно, включает коллинеарную позицию, если вы хотите включить Неподходящие также пересечения).

Затем вы должны повторить процесс с ролями якоря и отдельных сегментов.

Пересечение существует тогда и только тогда, когда одна из точекOnLeft, а другой OnRight.См. эту ссылку для более подробного объяснения с примерами изображений для каждого возможного случая.

Реализация такого метода будет намного проще, чем фактическая реализация метода, который находит точку пересечения (учитывая многоугольникслучаи, которые вам также придется обрабатывать).

Обновление

Следующие функции должны иллюстрировать идею (источник: Вычислительная геометрия в C ).
Примечание: В этом примере предполагается использование целых чисел.Если вместо этого вы используете некоторое представление с плавающей запятой (что, очевидно, может усложнить ситуацию), вам следует определить некоторое значение эпсилона, чтобы указать «равенство» (в основном для оценки IsCollinear).

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Конечно, при использовании этих функций необходимо помнить, что каждый сегмент лежит «между» другим сегментом (поскольку это конечные сегменты, а не бесконечные линии).

Кроме того, используя эти функции, вы можете понять, есть ли у вас правильное или неправильное перекресток.

• Правильное: Коллинеарные точки отсутствуют.Сегменты пересекают друг друга «из стороны в сторону».
• Неправильно : один сегмент только «касается» другого (по крайней мере одна из точек коллинеарна закрепленному сегменту).

Answer 4

Предположим, что два сегмента имеют конечные точки A, B и C, D. Численно надежный способ определения пересечения состоит в проверке знака четырех определителей:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

Для пересечения каждый определитель слева должен иметь противоположный знак справа, но не должно быть никакой связи между двумя линиями. В основном вы проверяете каждую точку сегмента относительно другого сегмента, чтобы убедиться, что они лежат на противоположных сторонах линии, определенной другим сегментом.

Смотрите здесь: http://www.cs.cmu.edu/~quake/robust.html

Answer 5

Основанный на превосходных ответах Лирана и Грамдрига здесь приведен полный код Python, чтобы проверить, пересекаются ли закрытые сегменты.Работает для коллинеарных сегментов, сегментов, параллельных оси Y, вырожденных сегментов (дьявол в деталях).Предполагает целочисленные координаты.Координаты с плавающей точкой требуют модификации теста на равенство точек.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True

Answer 6

У вас есть два отрезка.Определите один сегмент по конечным точкам A и B, а второй - по конечным точкам C и D. Есть хороший трюк, чтобы показать, что они должны пересекаться, В пределах границ сегментов.(Обратите внимание, что сами линии могут пересекаться за пределы сегментов, поэтому вы должны быть осторожны. Хороший код также будет следить за параллельными линиями.)

Хитрость заключается в том, чтобы проверить, что точки A и B должны быть на линиипротивоположные стороны линии CD, и что точки C и D должны лежать на противоположных сторонах линии AB.

Поскольку это домашняя работа, я не дам вам явного решения.Но простой тест, чтобы увидеть, на какую сторону линии падает точка, состоит в использовании точечного произведения.Таким образом, для данной строки CD вычислите вектор нормали к этой строке (я назову это N_C.) Теперь просто протестируйте знаки этих двух результатов:

dot(A-C,N_C)

и

dot(B-C,N_C)

Если эти результаты имеют противоположные знаки, то A и B являются противоположными сторонами линии CD.Теперь сделайте тот же тест для другой строки, AB.Имеет нормальный вектор N_A.Сравните знаки

dot(C-A,N_A)

и

dot(D-A,N_A)

Я оставлю вам решать, как вычислять нормальный вектор.(В 2-й, это тривиально, но будет ли ваш код беспокоиться о том, являются ли точки A и B разными точками? Аналогично ли различаются точки C и D?)

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

Answer 7

Вот еще один код Python, чтобы проверить, пересекаются ли замкнутые сегменты. Это переписанная версия кода C ++ в http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/. Эта реализация охватывает все особые случаи (например, все коллинеарные точки).

def on_segment(p, q, r):
    '''Given three colinear points p, q, r, the function checks if 
    point q lies on line segment "pr"
    '''
    if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
        q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
        return True
    return False

def orientation(p, q, r):
    '''Find orientation of ordered triplet (p, q, r).
    The function returns following values
    0 --> p, q and r are colinear
    1 --> Clockwise
    2 --> Counterclockwise
    '''

    val = ((q[1] - p[1]) * (r[0] - q[0]) - 
            (q[0] - p[0]) * (r[1] - q[1]))
    if val == 0:
        return 0  # colinear
    elif val > 0:
        return 1   # clockwise
    else:
        return 2  # counter-clockwise

def do_intersect(p1, q1, p2, q2):
    '''Main function to check whether the closed line segments p1 - q1 and p2 
       - q2 intersect'''
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if (o1 != o2 and o3 != o4):
        return True

    # Special Cases
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 and on_segment(p1, p2, q1)):
        return True

    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 and on_segment(p1, q2, q1)):
        return True

    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 and on_segment(p2, p1, q2)):
        return True

    # p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 and on_segment(p2, q1, q2)):
        return True

    return False # Doesn't fall in any of the above cases

Ниже приведена тестовая функция для проверки ее работы.

import matplotlib.pyplot as plt

def test_intersect_func():
    p1 = (1, 1)
    q1 = (10, 1)
    p2 = (1, 2)
    q2 = (10, 2)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (10, 0)
    q1 = (0, 10)
    p2 = (0, 0)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (-5, -5)
    q1 = (0, 0)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

    p1 = (0, 0)
    q1 = (1, 1)
    p2 = (1, 1)
    q2 = (10, 10)
    fig, ax = plt.subplots()
    ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
    ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
    print(do_intersect(p1, q1, p2, q2))

Answer 8

Вот код C, чтобы проверить, находятся ли две точки на противоположных сторонах отрезка. Используя этот код, вы можете проверить, пересекаются ли два сегмента.

// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {

//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize

// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;

// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
        cout<<"collinear points"<<endl;

return(SIGN(proj1) != SIGN(proj2));

}

Answer 9

Поскольку вы не упоминаете, что хотите найти точку пересечения линии, проблему становится проще решить. Если вам нужна точка пересечения, то ответ OMG_peanuts - более быстрый подход. Однако, если вы просто хотите узнать, пересекаются ли линии или нет, вы можете сделать это, используя уравнение линии (ax + by + c = 0). Подход заключается в следующем:

1. Начнем с двух отрезков: отрезка 1 и отрезка 2.

   segment1 = [[x1,y1], [x2,y2]]
   segment2 = [[x3,y3], [x4,y4]]
   

2. Проверьте, не являются ли два отрезка линии ненулевой линией и различны ли отрезки.

3. С этого момента я предполагаю, что два сегмента имеют ненулевую длину и различны. Для каждого отрезка линии вычислите наклон линии, а затем получите уравнение линии в виде ax + by + c = 0. Теперь вычислите значение f = ax + by + c для двух точек другой отрезок (повторите то же самое для другого отрезка).

   a2 = (y3-y4)/(x3-x4);
   b1 = -1;
   b2 = -1;
   c1 = y1 - a1*x1;
   c2 = y3 - a2*x3;
   // using the sign function from numpy
   f1_1 = sign(a1*x3 + b1*y3 + c1);
   f1_2 = sign(a1*x4 + b1*y4 + c1);
   f2_1 = sign(a2*x1 + b2*y1 + c2);
   f2_2 = sign(a2*x2 + b2*y2 + c2);
   

4. Теперь все, что осталось, это разные случаи. Если f = 0 для любой точки, то две линии касаются одной точки. Если f1_1 и f1_2 равны или f2_1 и f2_2 равны, то линии не пересекаются. Если f1_1 и f1_2 неравны , а f2_1 и f2_2 неравны, то отрезки линии пересекаются. В зависимости от того, хотите ли вы считать линии, которые касаются, «пересекающимися» или нет, вы можете адаптировать свои условия.

Answer 10

для сегментов AB и CD: найдите наклон CD

slope=(Dy-Cy)/(Dx-Cx)

, протяните CD по A и B и возьмите расстояние до CD, идущего прямо вверх

dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

проверьтеони на противоположных сторонах

return dist1*dist2<0