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

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

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

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

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

Обновить:

 FMc01 окт. 2010 г., 13:38

Ответы на вопрос(3)

Пользователь @ 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)
 charles03 июн. 2013 г., 10:44
Очень простой и элегантный, но он плохо справляется с колинеарностью, и, следовательно, для этой цели требуется больше кода.
 Zsolt Safrany10 нояб. 2014 г., 11:34
Для решения, которое также обрабатывает коллинеарность, проверьтеgeeksforgeeks.org/check-if-two-given-line-segments-intersect
Решение Вопроса

Уравнение прямой:

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;

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

 OMG_peanuts01 окт. 2010 г., 15:36
Это не так сложно, я написал много (несущественных?) Промежуточных шагов в целях понимания. Основные моменты к инструментам: проверка существования взаимного интервала, вычисление A1, A2, b1, b2 и Xa, а затем проверка того, что Xa включен во взаимный интервал. Это все :)
 aneuryzm02 окт. 2010 г., 11:30
Вы правы, извините, я много лет не занимаюсь математикой :)
 aneuryzm01 окт. 2010 г., 15:28
Хорошо, спасибо, я пойду через код. Вау не сложно? Я думал, что это не было таким долгим решением. Но если это единственный ... ну, давайте сделаем это.
 dmitri26 авг. 2013 г., 09:51
Формула A1 * x + b1 = y не обрабатывает вертикальные линии, поэтому вертикальные сегменты должны обрабатываться отдельно с помощью этого метода.
 rbaleksandar09 сент. 2016 г., 08:23
Да, я только что узнал, чтоy ставит проблему. Например, если у нас есть отрезок[[-4, 12], [12, -4]] and then another one which goes VERTICALLY (that is no change along the ось x`)[[-4, -4], [-4, 10]] Я до сих пор на перекрестке[-4, 12], Хотя это верно для линии (то есть, если мы посмотрим на ее продолжение), это, безусловно, не относится к сегменту, который даже физически не пересекает другой.
 lynxoid28 мая 2013 г., 23:20
если A1 == A2 и b1 == b2, сегменты располагаются друг над другом и имеют бесконечно много пересечений
 rbaleksandar09 сент. 2016 г., 08:42
Проверьтеэта почта мой, если у вас есть время. Я использую правило Крамера (которое немного отличается от вашего решения) для пересечения, однако фильтрация для сегментов без взаимных пропусков находится в начале, поэтому то, что происходит потом, не имеет значения.
 inkredibl22 окт. 2012 г., 19:49
A1 - A2 никогда не будет нулевым, потому что, если (A1 == A2) вернулось бы до этого вычисления в этом случае.
 aneuryzm01 окт. 2010 г., 12:33
Сегменты, это сегменты, извините. Не могли бы вы обновить свой ответ с учетом сегментов?
 Corvin14 янв. 2016 г., 08:36
Кажется, вы пропускаете проверку, если Ya принадлежит Y проекциям. Как у вас есть, вы бы упустили случай, когда сегменты лежат друг на друге - абсцисса пересечения будет в проекциях сегментов, но ордината не будет, и вы, не проверив ординату, вернули бы истину. Также, проверка того, что интервал существует, кажется неправильной Похоже, вы только проверяете, что сегмент A находится слева от сегмента B, но не проверяете другой случай. Это все еще не имеет значения, хотя, так как вы проверяете включение Xa позже

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

Идея состоит в том, чтобы рассматривать один сегмент как «якорь» и разделять второй сегмент на 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);
}

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

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

правильный: Нет коллинеарных точек. Сегменты пересекают друг друга "из стороны в сторону".неподходящий: Один сегмент только «касается» другого (по крайней мере, одна из точек коллинеарна закрепленному сегменту).
 Miguel15 окт. 2011 г., 03:15
+1 Я видел десятки ответов на эту проблему, но это, безусловно, самый ясный, простой и самый эффективный, который я видел. :)
 Jochen Ritzel01 окт. 2010 г., 21:12
+1 В значительной степени моя идея тоже. Если вы просто думаете о том, где находятся точки по отношению друг к другу, вы можете решить, должны ли их сегменты пересекаться или нет, не вычисляя ничего.
 Liran02 окт. 2010 г., 12:58
@ Патрик, на самом деле нет. В зависимости от того, какой из сегментов является «якорем», в этом случае обе точки являются либо OnLeft, либо OnRight. (См. Мой обновленный ответ).
 aneuryzm02 окт. 2010 г., 11:11
и @ THC4k Хм, это на самом деле не ясно. Для примера проверьте изображение, которое я добавил к вопросу: 2 точки - «OnLeft» и «OnRight», но 2 сегмента не пересекаются.

Ваш ответ на вопрос