Как я могу проверить, пересекаются ли два сегмента?
Как я могу проверить, пересекаются ли 2 сегмента?
У меня есть следующие данные:
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
Мне нужно написать небольшой алгоритм на Python, чтобы определить, пересекаются ли две линии.
Обновить:
26 ответов
Уравнение прямой:
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;
В дополнение к этому, вы можете проверить при запуске, что две из четырех предоставленных точек не равны, чтобы избежать всего этого тестирования.
Пользователь @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)
Вам не нужно точно вычислять, где пересекаются сегменты, а только понимать , пересекаются ли они вообще. Это упростит решение.
Идея состоит в том, чтобы рассматривать один сегмент как "якорь" и разделять второй сегмент на 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);
}
Конечно, при использовании этих функций необходимо помнить, что каждый сегмент лежит "между" другим сегментом (поскольку это конечные сегменты, а не бесконечные линии).
Кроме того, используя эти функции, вы можете понять, есть ли у вас правильное или неправильное пересечение.
- Правильно: нет коллинеарных точек. Сегменты пересекают друг друга "из стороны в сторону".
- Неправильно: один сегмент только "касается" другого (по крайней мере, одна из точек коллинеарна закрепленному сегменту).
Предположим, что два сегмента имеют конечные точки 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
Вот решение с использованием точечных произведений:
# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
dx0 = s0[1][0]-s0[0][0]
dx1 = s1[1][0]-s1[0][0]
dy0 = s0[1][1]-s0[0][1]
dy1 = s1[1][1]-s1[0][1]
p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
return (p0*p1<=0) & (p2*p3<=0)
Вот визуализация в Desmos: Пересечение отрезка линии
Проверить, пересекаются ли линейные сегменты, очень просто с помощью библиотеки Shapely, используя intersects метод:
from shapely.geometry import LineString
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False
Это мой способ проверки пересечения линии и места пересечения. Давайте использовать от x1 до x4 и от y1 до y4
Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}
Затем нам нужны векторы для их представления
dx1 = X2 - X1
dx2 = X4 - X4
dy1 = Y2 - Y1
dy2 = Y4 - Y3
Теперь посмотрим на определитель
det = dx1 * dy2 - dx2 * dy1
Если определитель равен 0,0, то отрезки параллельны. Это может означать, что они перекрываются. Если они перекрываются только в конечных точках, тогда существует одно решение для пересечения. В противном случае решений будет бесконечное количество. Что является вашей точкой пересечения с бесконечным множеством решений? Так что это интересный частный случай. Если вы заранее знаете, что линии не могут перекрываться, вы можете просто проверить,det == 0.0и если это так, просто скажите, что они не пересекаются, и готово. В противном случае, давайте продолжим
dx3 = X3 - X1
dy3 = Y3 - Y1
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
Теперь, если det, det1 и det2 равны нулю, тогда ваши линии коллинеарны и могут перекрываться. Если det равен нулю, а det1 или det2 нет, то они не коллинеарны, но параллельны, поэтому пересечения нет. Итак, что остается, если det равен нулю, это проблема 1D, а не 2D. Нам нужно будет проверить один из двух способов, в зависимости от того, равно ли dx1 нулю (чтобы избежать деления на ноль). Если dx1 равен нулю, просто проделайте ту же логику со значениями y, а не x ниже.
s = X3 / dx1
t = X4 / dx1
Это вычисляет два масштабатора, так что если мы масштабируем вектор (dx1, dy1) по s, мы получаем точку (x3, y3), а по t мы получаем (x4, y4). Итак, если s или t находится между 0,0 и 1,0, то точка 3 или 4 находится на нашей первой строке. Отрицательное значение будет означать, что точка находится за началом нашего вектора, а> 1.0 означает, что она находится впереди конца нашего вектора. 0.0 означает, что он находится в (x1, y1), а 1.0 означает, что он находится в (x2, y2). Если и s, и t < 0,0 или оба> 1,0, то они не пересекаются. И это касается особого случая параллельных линий.
Сейчас если det != 0.0 тогда
s = det1 / det
t = det2 / det
if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0)
return false // no intersect
На самом деле это похоже на то, что мы делали выше. Теперь, если мы пройдем вышеуказанный тест, наши отрезки линии пересекаются, и мы можем довольно легко вычислить пересечение следующим образом:
Ix = X1 + t * dx1
Iy = Y1 + t * dy1
Если вы хотите глубже понять, что делает математика, изучите правило Крамера.
На основе превосходных ответов Liran и Grumdrig приведен полный код 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
Вот еще один код 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))
У вас есть два отрезка. Определите один сегмент по конечным точкам 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?)
Вам по-прежнему нужно беспокоиться о отрезках линии, которые лежат вдоль одной и той же бесконечной линии, или о том, действительно ли одна точка падает на другой отрезок линии. Хороший код будет обслуживать все возможные проблемы.
Вот код 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));
}
Ответ Georgy, безусловно, наиболее понятен. Пришлось разобраться с этим, так как пример brycboe, хотя и простой, имел проблемы с коллинеарностью.
Код для тестирования:
#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# https://stackru.com/questions/3838329/how-can-i-check-if-two-segments-intersect
from shapely.geometry import LineString
class Point:
def __init__(self,x,y):
self.x = x
self.y = y
def ccw(A,B,C):
return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def ShapelyIntersect(A,B,C,D):
return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))
a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)
'''
Test points:
b(0,1) c(1,1)
a(0,0) d(1,0)
'''
# F
print(intersect(a,b,c,d))
# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))
# F
print(intersect(a,d,b,c))
# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))
print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))
Мы также можем решить эту проблему, используя векторы.
Давайте определим сегменты как [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
Откапывая старую ветку и изменяя код Грумдрига...
def cross_prod(A,B,C):
return (B.x-A.x) * (C.y-B.y) - (B.y-A.y) * (C.x-B.x)
def segments_intersect(A,B,C,D):
#function result excludes collinear
return cross_prod(A,C,D) * cross_prod(B,C,D) < 0 and
cross_prod(C,A,B) * cross_prod(D,A,B) < 0
Изменить: я только что понял, что этот код похож на код BenMan95.
Для сегментов 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
Я думал, что внесу хорошее решение Swift:
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
}
если кто-то хочет сделать C-подобную скорость поиска пересечений нескольких строк, вы можете использовать этот код, выполненный вnumbaиpython
Примечание
аргумент epsilon должен быть пропорционален расстоянию между строками. Кроме того, импорт толькоimport numbaиimport numpy as np
@numba.njit('float64[:,::1], float64[::1], float64', fastmath=True)
def nb_isBetween(line_ab, c, epsilon):
"""
:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param c: point to check like --> np.array([731362.47087528, 9746708.78767337])
:param epsilon:
:return: check if points is on line or not netween point a and b
"""
a, b = line_ab
a_x, a_y = a
b_x, b_y = b
c_x, c_y = c
crossproduct = (c_y - a_y) * (b_x - a_x) - (c_x - a_x) * (b_y - a_y)
# compare versus epsilon for floating point values, or != 0 if using integers
if abs(crossproduct) > epsilon:
return False
dotproduct = (c_x - a_x) * (b_x - a_x) + (c_y - a_y) * (b_y - a_y)
if dotproduct < 0:
return False
squaredlengthba = (b_x - a_x) * (b_x - a_x) + (b_y - a_y) * (b_y - a_y)
if dotproduct > squaredlengthba:
return False
return True
@numba.njit('float64[:,::1], float64[:,::1]', fastmath=True)
def nb_get_line_intersect(line_ab, line_cd):
"""
:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param line_cd: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:return: get point of intersection, if the points in on line ab or cd returns the point if not retunrs 0
"""
A, B = line_ab
C, D = line_cd
# a1x + b1y = c1
a1 = B[1] - A[1]
b1 = A[0] - B[0]
c1 = a1 * (A[0]) + b1 * (A[1])
# a2x + b2y = c2
a2 = D[1] - C[1]
b2 = C[0] - D[0]
c2 = a2 * (C[0]) + b2 * (C[1])
# determinant
det = a1 * b2 - a2 * b1
# parallel line
if det == 0:
return np.array([np.nan, np.nan])
# intersect point(x,y)
x = ((b2 * c1) - (b1 * c2)) / det
y = ((a1 * c2) - (a2 * c1)) / det
#check if x and y area in the line segment interval
if nb_isBetween(line_ab, np.array([x, y]), epsilon=0.001) and nb_isBetween(line_cd, np.array([x, y]), epsilon=0.001):
return np.array([x, y])
else:
return np.array([np.nan, np.nan])
@numba.njit('float64[:, :, ::1], float64[:, :, ::1]', parallel=True, fastmath=True)
def nb_get_line_intersect(m_ramales_lines, interference_lines):
"""
:param m_ramales_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:param interference_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:return: m_ramales_lines x interference_lines x 2
"""
#empty matrix to fill
m_ramales_interference = np.empty(shape=(len(m_ramales_lines), len(interference_lines), 2))
for pos1 in range(len(m_ramales_lines)):
line_ab = m_ramales_lines[pos1]
for pos2 in numba.prange(len(interference_lines)):
# interference line
line_cd = interference_lines[pos2].T
# get crossing point
cross_point = nb_get_line_intersect(line_ab.copy(), line_cd.copy())
#fill 2D array
m_ramales_interference[pos1, pos2] = cross_point
return m_ramales_interference
Используя решение OMG_Peanuts, я перевел на SQL.(Скалярная функция HANA)
Спасибо OMG_Peanuts, отлично работает. Я использую круглую землю, но расстояния небольшие, поэтому я считаю, что это нормально.
FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
IN LONG_A1 DOUBLE,
IN LAT_A2 DOUBLE,
IN LONG_A2 DOUBLE,
IN LAT_B1 DOUBLE,
IN LONG_B1 DOUBLE,
IN LAT_B2 DOUBLE,
IN LONG_B2 DOUBLE)
RETURNS RET_DOESINTERSECT DOUBLE
LANGUAGE SQLSCRIPT
SQL SECURITY INVOKER AS
BEGIN
DECLARE MA DOUBLE;
DECLARE MB DOUBLE;
DECLARE BA DOUBLE;
DECLARE BB DOUBLE;
DECLARE XA DOUBLE;
DECLARE MAX_MIN_X DOUBLE;
DECLARE MIN_MAX_X DOUBLE;
DECLARE DOESINTERSECT INTEGER;
SELECT 1 INTO DOESINTERSECT FROM DUMMY;
IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY;
SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
IF MA = MB THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
END IF;
SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
-- Max of Mins
IF LAT_A1 < LAT_A2 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 > LAT_B1 THEN -- MAX(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 > LAT_B2 THEN -- MAX(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 < LAT_A1 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 > LAT_B1 THEN -- MAX(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 > LAT_B2 THEN -- MAX(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
END IF;
-- Min of Max
IF LAT_A1 > LAT_A2 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 < LAT_B1 THEN -- MIN(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 < LAT_B2 THEN -- MIN(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 > LAT_A1 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 < LAT_B1 THEN -- MIN(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 < LAT_B2 THEN -- MIN(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
END IF;
IF XA < MAX_MIN_X OR
XA > MIN_MAX_X THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
RET_DOESINTERSECT := :DOESINTERSECT;
END;
Так как вы не упоминаете, что хотите найти точку пересечения линии, проблема становится проще для решения. Если вам нужна точка пересечения, то ответ OMG_peanuts - более быстрый подход. Однако, если вы просто хотите узнать, пересекаются ли линии или нет, вы можете сделать это, используя уравнение линии (ax + by + c = 0). Подход заключается в следующем:
Начнем с двух отрезков: отрезка 1 и отрезка 2.
segment1 = [[x1,y1], [x2,y2]] segment2 = [[x3,y3], [x4,y4]]Проверьте, не являются ли два отрезка линии ненулевой длиной и разные отрезки.
Начиная с этого момента, я предполагаю, что два сегмента имеют ненулевую длину и различны. Для каждого отрезка линии вычислите наклон линии, а затем получите уравнение линии в виде 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);Теперь все, что осталось, это разные случаи. Если f = 0 для любой точки, то две линии касаются одной точки. Если f1_1 и f1_2 равны или f2_1 и f2_2 равны, то линии не пересекаются. Если f1_1 и f1_2 неравны, а f2_1 и f2_2 неравны, то отрезки линии пересекаются. В зависимости от того, хотите ли вы считать линии, которые касаются "пересекающимися" или нет, вы можете адаптировать свои условия.
Одно из вышеперечисленных решений сработало так хорошо, что я решил написать полную демонстрационную программу с использованием wxPython. Вы должны иметь возможность запускать эту программу так: python "ваше имя файла"
# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.
import wx
class Point:
def __init__(self, newX, newY):
self.x = newX
self.y = newY
app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0
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)
def is_intersection(p1, p2, p3, p4):
return intersect(p1, p2, p3, p4)
def drawIntersection(pc):
mp2 = Point(highestX, mp.y)
if is_intersection(p1, p2, mp, mp2):
pc.DrawText("intersection", 10, 10)
else:
pc.DrawText("no intersection", 10, 10)
def do_paint(evt):
pc = wx.PaintDC(frame)
pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
pc.DrawLine(mp.x, mp.y, highestX, mp.y)
drawIntersection(pc)
def do_left_mouse(evt):
global mp, highestX
point = evt.GetPosition()
mp = Point(point[0], point[1])
highestX = frame.Size[0]
frame.Refresh()
frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()
Вот некоторый код Python, который защищен от всех краевых случаев коллинеарности и проблем с ошибками округления.
epsilon = 0.000001
def is_intersecting(x1, y1, x2, y2, x3, y3, x4, y4):
c_area = area(x1, y1, x2, y2, x3, y3)
d_area = area(x1, y1, x2, y2, x4, y4)
if abs(c_area) < epsilon:
if abs(x3-x1) < epsilon:
if min(y1,y2)-epsilon < y3 < max(y1,y2)+epsilon:
return True
else:
if min(x1,x2)-epsilon < x3 < max(x1,x2)+epsilon:
return True
if abs(d_area) > epsilon:
return False
if abs(d_area) < epsilon:
if abs(x4-x1) < epsilon:
if min(y1,y2)-epsilon < y4 < max(y1,y2)+epsilon:
return True
else:
if min(x1,x2)-epsilon < x4 < max(x1,x2)+epsilon:
return True
if abs(c_area) > epsilon:
return False
if abs(x3-x1) < epsilon:
return (y1 < y3) != (y1 < y4)
else:
return (x1 < x3) != (x1 < x4)
if (c_area > 0) == (d_area > 0):
return False
a_area = area(x3, y3, x4, y4, x1, y1)
b_area = area(x3, y3, x4, y4, x2, y2)
return (a_area > 0) != (b_area > 0)
def area(x1, y1, x2, y2, x3, y3):
return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)
Если ваши данные определяют линию, вам просто нужно доказать, что они не параллельны. Для этого вы можете вычислить
alpha = float(y2 - y1) / (x2 - x1).
Если этот коэффициент равен и для Line1, и для Line2, это означает, что линия параллельна. Если нет, значит, они будут пересекаться.
Если они параллельны, вы должны доказать, что они не одинаковы. Для этого вы вычисляете
beta = y1 - alpha*x1
Если бета одинакова для Line1 и Line2, это означает, что вы пересекаете линию, поскольку они равны
Если они сегментные, вам все равно придется вычислять альфа и бета, как описано выше для каждой строки. Затем вы должны проверить, что (beta1 - beta2) / (alpha1 - alpha2) больше Min(x1_line1, x2_line1) и меньше Max(x1_line1, x2_line1)
Это то, что у меня есть для 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();
}
Вычислите точку пересечения линий, лежащих на ваших сегментах (это в основном означает решение системы линейных уравнений), затем проверьте, находится ли она между начальной и конечной точками ваших сегментов.
Реализовано в 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
Решено, но все же почему бы не с 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