Еще один алгоритм определения пересечения двух отрезков

[andy_p]

Все эти алгоритмы страдают от неустойчивости решений, ввиду использования арифметики с плавающей точкой. Есть такой раздел науки — exact geometric computation, где рассматриваются подобные вопросы.

[ibrin]

Решаем алгебраически: y=kx+b, P0(x1,y1), P1(x2,y2), P2(x3,y3), P3(x4,y4).
k1=(y1-y2)/(x1-x2)
k2=(y3-y4)/(x3-x4)
b1=(y1x2-y2x1)/(x2-x1)
b2=(y3x4-y4x3)/(x4-x3)
Пересечение прямых:C(x,y)
x=(b2-b1)/(k1-k2)
y=(b1k2-b2k1)/(k2-k1)
Перечение отрезков:
(min(x1,x2)<=x<=max(x1,x2)) && (min(x3,x4)<=x<=max(x3,x4)) && (min(y1,y2)<=y<=max(y1,y2)) && (min(y3,y4)<=y<=max(y3,y4))

[SemenovVV]

Каким будет ваше решение если x1 =x2 или x4 = x3 или k1 = k2 ( деление на 0 )?

[ibrin]

Это же общее решение. Проверить входные данные и промежуточные результаты можно и самостоятельно. Всего 4 варианта:
1. Отрезок Р0Р1 вырождается в точку
2. Отрезок Р2Р3 вырождается в точку
3. Прямые параллельны k1=k2 b1<>b2 — нет решения
4. Прямые совпадают k1=k2 b1=b2 — возможно множество решений

[SemenovVV]

1. Отрезок Р0Р1 вырождается в точку

если это вариант x1 =x2 и y1<>y2
Отрезок не вырождается, отрезок вертикален, k1 = бесконечности

4. Прямые совпадают k1=k2 b1=b2 — возможно множество решений

Решений может и не быть. Отрезки могут лежать на одной линии и не пересекаться.

Я видел задачу в минимизации числа операций ( вычислений сравнений) алгоритма. Уверен это можно сделать лучше чем у меня.
Мне кажется, если прописать ваш алгоритм со всеми проверками, операций не станет меньше.

[ibrin]

Решение со всеми проверками:

#!/usr/bin/python
print "Hello, Python!"
# input data
x1=0.0
y1=0.0
x2=0.0
y2=0.0
x3=0.0
y3=0.0
x4=0.0
y4=0.0
# logic
if (x1<>x2) and (x3<>x4):
    k1=(y1-y2)/(x1-x2)
    b1=(x2*y1-x1*y2)/(x2-x1)
    k2=(y3-y4)/(x3-x4)
    b2=(x4*y3-x3*y4)/(x4-x3)
    if k1<>k2:
        x=(b2-b1)/(k1-k2)
        y=(k2*b1-k1*b2)/(k2-k1)
        if (min(x1,x2)<=x<=max(x1,x2)) and (min(x3,x4)<=x<=max(x3,x4)) and (min(y1,y2)<=y<=max(y1,y2)) and (min(y3,y4)<=y<=max(y3,y4)):
            print "norm-1 C(",x,";",y,")"
        else:
            print "none"
    else:
        if b1==b2:
            if max(min(x1,x2),min(x3,x4))<min(max(x1,x2),max(x3,x4)):
                print "norm multiple solution C(",max(min(x1,x2),min(x3,x4)),"..",min(max(x1,x2),max(x3,x4)),";",max(min(y1,y2),min(y3,y4)),"..",min(max(y1,y2),max(y3,y4)),")"
            else:
                if max(min(x1,x2),min(x3,x4))==min(max(x1,x2),max(x3,x4)):
                    print "norm-2 C(",max(min(x1,x2),min(x3,x4)),";",max(min(y1,y2),min(y3,y4)),")"
                else:
                    print "none"
else:
    if ((x1==x2) and (x3<>x4)) or ((x1<>x2) and (x3==x4)):
        if x3<>x4:
            k=(y3-y4)/(x3-x4)
            b=(x4*y3-x3*y4)/(x4-x3)
            x=x1
        if x1<>x2:
            k=(y1-y2)/(x1-x2)
            b=(x2*y1-x1*y2)/(x2-x1)
            x=x3
        y=k*x+b
        if (min(x1,x2)<=x<=max(x1,x2)) and (min(x3,x4)<=x<=max(x3,x4)) and (min(y1,y2)<=y<=max(y1,y2)) and (min(y3,y4)<=y<=max(y3,y4)):
            print "ex-1 C(",x,";",y,")"
        else:
            print "none"
    else:
        if (x1==x2) and (x3==x4) and (x1==x3):
            if max(min(y1,y2),min(y3,y4))<min(max(y1,y2),max(y3,y4)):
                print "ex multiple solution C(",x1,";",max(min(y1,y2),min(y3,y4)),"..",min(max(y1,y2),max(y3,y4)),")"
            else:
                if max(min(y1,y2),min(y3,y4))==min(max(y1,y2),max(y3,y4)):
                    print "ex-2 C(",x1,";",max(min(y1,y2),min(y3,y4)),")"
                else:
                    print "none"
        else:
            print "none"

[MrShoor]

Чйорт побери. Лучше бы вы не показывали свое решение. Оно же не подлежит поддержке… я даже знаю на какой сайт можно такое отправлять.

[ibrin]

цеж прототип! вычисления занимают отсилы 10 строчек, а всё остальное частные случаи, типа частичного совпадения отрезков, что в общем-то и не пересечение, а общие точки имеются.

[SemenovVV]

проверьте, плиз, параллельные отрезки
например:

x1=1.0
y1=1.0
x2=5.0
y2=5.0
x3=3.0
y3=4.0
x4=4.0
y4=5.0

я не знаком с питоном, запускал на Coding Ground www.tutorialspoint.com/execute_python_online.php

print "none"

не увидел

[ibrin]

мой косяк, забыл else print «none» для k1=k2 & b1<>b2
высылаю патч:

@@ -31,6 +31,7 @@
                     print "norm-2 C(",max(min(x1,x2),min(x3,x4)),";",max(min(y1,y2),min(y3,y4)),")"
                 else:
                     print "none"
+        print "none"
 else:
     if ((x1==x2) and (x3<>x4)) or ((x1<>x2) and (x3==x4)):
         if x3<>x4:

спасибо за тесты!

[ibrin]

Это мой первый код на питоне и патч кривой.
Вот правильный:

@@ -31,6 +31,8 @@
                     print "norm-2 C(",max(min(x1,x2),min(x3,x4)),";",max(min(y1,y2),min(y3,y4)),")"
                 else:
                     print "none"
+        else:
+            print "none"
 else:
     if ((x1==x2) and (x3<>x4)) or ((x1<>x2) and (x3==x4)):
         if x3<>x4:

[0serg]

Это неэффективное решение стандартной и хорошо изученной задачи «в лоб». Учебная задачка для любого приличного студента, какой смысл о ней писать? Есть изящные, красивые и эффективные решения, лучше бы о них написали

[PapaBubaDiop]

Особенно огорчает использование дорогих cos(x) и sin(x), совсем не ценят такты молодые ребята…

[Sayonji]

Там не используются они нигде как вызовы функций, только как объяснение.

[SemenovVV]

Согласен, задача стандартная, написал только как вариант для ранее опубликованного алгоритма «habrahabr.ru/post/267037», не более. Пришлось вспоминать школьный курс математики. Почему вы считаете предложенное решение неэффективным?

[Keyten]

Я придумал, давайте создадим массив пикселей, нарисуем там 2 прямые и поищем близко лежащие точки перебором всех пикселей.

[Zenitchik]

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

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

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

[5nw]

Да, это хороший способ. Но нужно еще учесть случай, когда точка конца одного отрезка будет лежать на прямой другого.
Если формализовать, то получим:
1. Даны два отрезка (x11, y11) — (x12, y12) и (x21, y21) — (x22, y22)
2. Проведем через эти отрезки прямые a1 * x + b1 * y + c1 = 0 и a2 * x + b2 * y + c2 = 0
3. Тогда отрезки пересекаются, если (a1 * x21 + b1 * y21 + c1) * (a1 * x22 + b1 * y22 + c1) <= 0 и
(a2 * x11 + b2 * y11 + c2) * (a2 * x12 + b2 * y12 + c2) <= 0
Все просто и логично

[5nw]

Провести прямую через отрезок (x1, y1) — (x2, y2) можно так
a = y2 — y1;
b = x1 — x2;
c = y1 * x2 — x1 * y2;