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

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

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

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

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

обновление:

17 60
python mathjax

17 ответов:

уравнение прямой имеет вид:

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

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

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

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

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

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

и мы могли бы сказать, что Xa входит в :

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 включенными в ИА:

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;

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

37

пользователь @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)
53

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

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

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

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

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

обновление

следующие функции должны иллюстрировать идею (источник:вычислительная геометрия В C).
замечание: в этом примере предполагается использование целых чисел. Если вы используете некоторое представление с плавающей запятой вместо этого (что, очевидно, может усложнить ситуацию), тогда вы должны определить некоторое значение epsilon, чтобы указать "равенство" (в основном для 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);
}

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

  • правильный: нет точек. Сегменты пересекают каждый другие "из стороны в сторону".
  • неправильное: один сегмент только "касается" другого (по крайней мере, один из точки коллинеарны к якорный сегмент).
24

предположим, что два сегмента имеют конечные точки 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

15

на основе Лиран это и Grumdrig это!--3--> отличные ответы вот полный код 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
4

у вас есть два отрезка. Определите один сегмент по конечным точкам 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. Теперь сделайте тот же тест для другая линия, ЭБ. Он имеет нормальный вектор N_A. Сравнивать признаки

dot(C-A,N_A)

и

dot(D-A,N_A)

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

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

3

вот код на 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));

}

3

вот еще один код 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))
2

для сегментов 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
1

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 неравны, то отрезки линии пересекаются. В зависимости от того, хотите ли вы рассматривать линии, которые касаются, как "пересекающиеся" или нет, вы можете адаптировать свои условия.

1

Я думал, что внесу хороший быстрый решение:

struct Pt {
    var x: Double
    var y: Double
}

struct LineSegment {
    var p1: Pt
    var p2: Pt
}

func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {

    if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
        if (ls2.p2.x-ls2.p1.x == 0) {
            //both lines are vertical and parallel
            return false
        }

        let x = ls1.p1.x

        let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
        let c2 = ls2.p1.y-slope2*ls2.p1.x

        let y = x*slope2+c2 // y intersection point

        return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
    }

    if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2

        let x = ls2.p1.x

        let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
        let c1 = ls1.p1.y-slope1*ls1.p1.x

        let y = x*slope1+c1 // y intersection point

        return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2

    }

    let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
    let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)

    if (slope1 == slope2) { //segments are parallel
        return false
    }

    let c1 = ls1.p1.y-slope1*ls1.p1.x
    let c2 = ls2.p1.y-slope2*ls2.p1.x

    let x = (c2-c1)/(slope1-slope2)

    return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
        ((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
    //validate that x is between x1,x2 in both segments

}
1

мы также можем решить эту проблему, используя векторы.

давайте определим сегменты, как [start, end]. Учитывая два таких сегмента [A, B] и [C, D] что оба имеют ненулевую длину, мы можем выбрать одну из конечных точек, которые будут использоваться в качестве опорной точки, так что мы получим три вектора:

x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]

оттуда мы можем искать пересечение, вычисляя t и u в p + t*r = u*q. Немного поиграв с уравнением, получаем:

t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]

таким образом, функция это:

def intersects(a, b):
    p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
    q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
    r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]

    t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
        if (q[0]*r[1] - q[1]*r[0]) != 0 \
        else (q[1]*p[0] - q[0]*p[1])
    u = (p[0] + t*r[0])/q[0] \
        if q[0] != 0 \
        else (p[1] + t*r[1])/q[1]

    return t >= 0 and t <= 1 and u >= 0 and u <= 1
1

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

alpha = float(y2 - y1) / (x2 - x1).

Если этот коэффициент равен для Line1 и Line2, это означает, что линия параллельна. Если нет, значит они пересекутся.

если они параллельны, то вы должны доказать, что они не совпадают. Для этого вы вычисляете 

beta = y1 - alpha*x1

Если бета одинакова для Line1 и Line2, это означает, что вы пересекаете линию, как они есть равный

если они являются сегментом, вам все равно придется вычислить альфа и бета, как описано выше для каждой строки. Затем вы должны проверить, что (бета1 - бета2) / (альфа1 - альфа2) больше, чем min(x1_line1, x2_line1) и меньше, чем максимальная(x1_line1, x2_line1)

0

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

0

Это то, что у меня есть для AS3, не знаю много о python, но концепция есть

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }
0

реализовано на JAVA. Однако кажется, что это не работает для ко-линейных линий (ака сегменты линии, которые существуют внутри друг друга L1(0,0)(10,10) L2(1,1)(2,2)

public class TestCode
{

  public class Point
  {
    public double x = 0;
    public double y = 0;
    public Point(){}
  }

  public class Line
  {
    public Point p1, p2;
    public Line( double x1, double y1, double x2, double y2) 
    {
      p1 = new Point();
      p2 = new Point();
      p1.x = x1;
      p1.y = y1;
      p2.x = x2;
      p2.y = y2;
    }
  }

  //line segments
  private static Line s1;
  private static Line s2;

  public TestCode()
  {
    s1 = new Line(0,0,0,10);
    s2 = new Line(-1,0,0,10);
  }

  public TestCode(double x1, double y1, 
    double x2, double y2,
    double x3, double y3,
    double x4, double y4)
  {
    s1 = new Line(x1,y1, x2,y2);
    s2 = new Line(x3,y3, x4,y4);
  }

  public static void main(String args[])
  {
     TestCode code  = null;
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         0,1,0,10);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         5,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,10,0,
                         0,0,15,0);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }

////////////////////////////
     code = new TestCode(0,0,10,10,
                         1,1,5,5);
     if( intersect(code) )
     { System.out.println( "OK COLINEAR: INTERSECTS" ); }
     else
     { System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         -1,-1,0,10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE END: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -10,10,10,-10);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         -3,-2,50,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(-10,-10,10,10,
                         50,-2,-3,-2);
     if( intersect(code) )
     { System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); }
     else
     { System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,0,10,
                         1,0,1,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,2,10,2,
                         0,10,10,10);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,10,5,13.75,
                         0,18.75,10,15);
     if( intersect(code) )
     { System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); }
     else
     { System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         2,-1,2,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); }
////////////////////////////
     code = new TestCode(0,0,1,1,
                         -1,-10,-5,10);
     if( intersect(code) )
     { System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); }
     else
     { System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); }
  }

  public static boolean intersect( TestCode code )
  {
    return intersect( code.s1, code.s2);
  }

  public static boolean intersect( Line line1, Line line2 )
  {
    double i1min = Math.min(line1.p1.x, line1.p2.x);
    double i1max = Math.max(line1.p1.x, line1.p2.x);
    double i2min = Math.min(line2.p1.x, line2.p2.x);
    double i2max = Math.max(line2.p1.x, line2.p2.x);

    double iamax = Math.max(i1min, i2min);
    double iamin = Math.min(i1max, i2max);

    if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) )
      return false;

    double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x );
    double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x );

    if( m1 == m2 )
        return false;

    //b1 = line1[0][1] - m1 * line1[0][0]
    //b2 = line2[0][1] - m2 * line2[0][0]
    double b1 = line1.p1.y - m1 * line1.p1.x;
    double b2 = line2.p1.y - m2 * line2.p1.x;
    double x1 = (b2 - b1) / (m1 - m2);
    if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) )
        return false;
    return true;
  }
}
выход 
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
OK SLOPE END: INTERSECTS
OK SLOPE Intersect(0,0): INTERSECTS
OK SLOPE Line2 VERTIAL: INTERSECTS
OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS
OK PARALLEL VERTICAL: DO NOT INTERSECT
OK PARALLEL HORIZONTAL: DO NOT INTERSECT
OK PARALLEL SLOPE=.75: DO NOT INTERSECT
OK SEPERATE SEGMENTS: DO NOT INTERSECT
OK SEPERATE SEGMENTS 2: DO NOT INTERSECT
0

решено, но все же почему бы не с python... :)

def islineintersect(line1, line2):
    i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
    i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
    ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
    if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
        return False
    m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
    m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
    if m1 == m2:
        return False
    b1 = line1[0][1] - m1 * line1[0][0]
    b2 = line2[0][1] - m2 * line2[0][0]
    x1 = (b2 - b1) / (m1 - m2)
    if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
        return False
    return True

Это:

print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])

выход:

True

и так:

print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])

выход:

False
-2