Пересечение двух строк по начальным и конечным точкам в python

Question

У меня здесь довольно простой вопрос. Я хочу найти, пересекаются ли две линии на одномерной плоскости. Я знаю два простых способа решить эту проблему, но мне хотелось знать, есть ли у Python более элегантный способ решить эту проблему?

Ex:

x = [1, 10] # 1 = begin, 10 = end 
y = [15, 20] 
z = [5, 12] 

#Method 1: Works. Is quick. Lots of typing. 
def is_intersect_1(a, b): 
    bool_check = False 
    if a[0] <= b[0] <= a[1] or \ 
    a[0] <= b[1] <= a[1] or \ 
    b[0] <= a[0] <= b[1] or \ 
    b[0] <= a[1] <= b[1]: 
     bool_check = True 
    return bool_check 

is_intersect_1(x,y) # False 
is_intersect_1(x,z) # True 

#Method 2: Quicker to write. Simpler to read. Uses more memory and is slower. 

def is_intersect_2(a, b): 
    bool_check = False 
    if set(range(a[0], a[1]+1)).intersection(set(range(b[0], b[1])): 
     bool_check = True 
    return bool_check 

is_intersect_2(x,y) # False 
is_intersect_2(x,z) # True 

Answer 1

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

class Interval(object): 
    """ Representation of a closed interval from 'a' to 'b'. """ 
    def __init__(self, a, b): 
     self.a, self.b = (a, b) if a < b else (b, a) # make a min & b max 

    def intersects(self, other): 
     return self.b >= other.a and self.a <= other.b 

    def __str__(self): 
     return '[{0.a:>{w}}, {0.b:>{w}}]'.format(self, w=2) 

testcases = ((Interval(1, 5), Interval(11, 14)), # xxxxx 
                #   xxxxx 
      (Interval(1, 9), Interval(7, 15)), # xxxxxxxxx 
                #  xxxxxxxxx 
      (Interval(5, 9), Interval(1, 15)), #  xxxxx 
                # xxxxxxxxxxxxxxx 
      (Interval(0, 15), Interval(5, 9))) # xxxxxxxxxxxxxxx 
                #  xxxxx 

for I1, I2 in testcases: 
    print('{} {:^7} intersect with {}'.format(
          I1, "does" if I1.intersects(I2) else "doesn't", I2)) 

Выход:

[ 1, 5] doesn't intersect with [11, 14] 
[ 1, 9] does intersect with [ 7, 15] 
[ 5, 9] does intersect with [ 1, 15] 
[ 0, 15] does intersect with [ 5, 9] 

Answer 2

Я не пытался измерить производительность, но я думаю, что это понятнее и, вероятно, будет быстрее - это торгует «или» потенциально двух дополнительных «тройные сравнения «для двух сравнений (мин. и макс.):

>>> x = [1,10] 
>>> y = [20,15] 
>>> z = [5,12] 
>>> def intersects (a, b): 
... c = [min (b), max(b)] 
... return (c[0] < a[0] < c[1]) or (c[0] < a[1] < c[1]) 
... 
>>> intersects (x, y) 
False 
>>> intersects (x, z) 
True 

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

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

Отредактировано отсюда. Я свернул блокнот ipython, чтобы проверить производительность. Первый метод в начальном столбце на самом деле быстрее основан на выборке интервалов, генерируемых случайным образом в диапазоне от -100 до 100. Шахта сравнивала в 827 микросекунд на петлю через 1000 сравнений по сравнению с 527.

К сожалению, тестирование показало, что первый метод в сообщении не срабатывает.

[59, -35] [89, -9] Ложные

f = intersects2 
for x in w: 
    print (v, x, f(x, v))  

[59, -35] [89, -9] Ложные

[59, -35] [76, 89] False

Answer 3

Этот вопрос оказался более интересным, чем я ожидал. Для меня оригинальное решение выглядело слишком сложным. Я не доверяю сложным, поэтому я попробовал свои силы в решении, которое было проще и легко доказуемо правильным. Я должен был оставить сравнение менее или равно, а не меньше. После игры, чтобы сравнить скорости двух, я случайно, на испытании только двух условий, обнаружил, что исходное решение было ошибочным. Я также узнал, что хотя мое решение - с упомянутой коррекцией - было медленнее предлагаемого решения.

Предлагаемое решение не позволяет выполнить 5 из 24 возможных случаев. Я оставляю это автору для исправления его функции. Я даже не пытался определить, где произошла его ошибка. Но я предлагаю следующую функцию, которая будет использоваться для тестирования.

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

В следующем коде передайте предлагаемую функцию test_intersection. Это вызовет исключение, если даже один из 24 возможных случаев не удастся. Мое решение, и модификация, предложенная с использованием кортежа внутри, проходит все 24. Исходное решение выходит из строя 5 случаев. После публикации этого, я понимаю, что есть некоторые дополнительные случаи, которые можно добавить. ([3,4], [3,7]), ([3,7], [3,7]), ([4,7], [3,7]), а также варианты, интервалы "линий назад.

def test_intersection (f): 
    assert not f ([1,2], [3,7]) 
    assert  f ([1,3], [3,7]) 
    assert  f ([1,4], [3,7]) 
    assert  f ([4,5], [3,7]) 
    assert  f ([4,8], [3,7]) 
    assert  f ([7,9], [3,7]) 
    assert not f ([8,9], [3,7]) 
    assert not f ([2,1], [3,7]) 
    assert  f ([3,1], [3,7]) 
    assert  f ([4,1], [3,7]) 
    assert  f ([5,4], [3,7]) 
    assert  f ([8,4], [3,7]) 
    assert  f ([9,7], [3,7]) 
    assert not f ([9,8], [3,7]) 
    assert not f ([1,2], [7,3]) 
    assert  f ([1,3], [7,3]) 
    assert  f ([1,4], [7,3]) 
    assert  f ([4,5], [7,3]) 
    assert  f ([4,8], [7,3]) 
    assert  f ([7,9], [7,3]) 
    assert not f ([8,9], [7,3]) 
    assert not f ([2,1], [7,3]) 
    assert  f ([3,1], [7,3]) 
    assert  f ([4,1], [7,3]) 
    assert  f ([5,4], [7,3]) 
    assert  f ([9,7], [7,3]) 
    assert not f ([9,8], [7,3])