решение пересечения множества / линии

Question

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

Например, если у меня есть [9,8,7,6,5] и [3,4,5,6,7], я бы хотел простую и эффективную формулу / алгоритм, который находит, что по индексу 3 они пересекаются , Я знаю, что могу сделать поиск, просто задаваясь вопросом, есть ли лучший способ.

Я знаю, что есть формула для решения двух строк в форме y = mx + b путем вычитания их друг от друга, но моя «линия» на самом деле не является строкой, поскольку она ограничена элементами в списке и может кривые.

Любая помощь приветствуется.

Answer 1

Вы можете взять теоретико-множественное пересечение координат в обоих списках:

intersecting_points = set(enumerate(list1)).intersection(set(enumerate(list2)))

... перечисление дает вам итерируемую совокупность индексов и значений - другими словами, (0,9), (1,8), (2,7) и т. Д.

http://docs.python.org/library/stdtypes.html#set-types-set-frozenset

... имеет смысл? Конечно, это не даст вам геометрическое пересечение - например, [1,2] пересекается с [2,1] при [x = 0,5, y = 1,5] - если это то, что вы хотите, то вам нужно решить линейные уравнения на каждом интервале.

Answer 2

from itertools import izip
def find_intersection(lineA, lineB):
  for pos, (A0, B0, A1, B1) in enumerate(izip(lineA, lineB, lineA[1:], lineB[1:])):
    #check integer intersections
    if A0 == B0: #check required if the intersection is at position 0
      return pos
    if A1 == B1: #check required if the intersection is at last position
      return pos + 1
    #check for intersection between points
    if (A0 > B0 and A1 < B1) or
       (A0 < B0 and A1 > B1):
      #intersection between pos and pos+1!
      return pos + solve_linear_equation(A0,A1,B0,B1)
  #no intersection
  return None

... где solve_linear_equation находит пересечение между сегментами (0,A0)→(1,A1) и (0,B0)→(1,B1).

Answer 3

import itertools

def intersect_at_same_index(seq1, seq2):
    return (
        idx
        for idx, (item1, item2)
        in enumerate(itertools.izip(seq1, seq2))
        if item1 == item2).next()

Возвращает индекс, в котором две последовательности имеют одинаковые элементы, и поднимает StopIteration, если все пары элементов различны. Если вам не нравится это поведение, заключите оператор return в оператор try, а в предложении except StopIteration верните свой любимый индикатор ошибки (например, -1, None…)

Answer 4

Я предполагаю, что одно измерение в вашем списке предполагается, например, [9,8,7,6,5] высоты в x1, x2, x3, x4, x5 не так ли? в этом случае, как ваш список будет представлять кривые, такие как у = 0?

В любом случае я не думаю, что может быть какое-либо сокращение для вычисления пересечения общих или случайных кривых, лучшее решение - сделать эффективный поиск.