set / line intersection solution

Question

I have two lists in python and I want to know if they intersect at the same index. Is there a mathematical way of solving this?

For example if I have [9,8,7,6,5] and [3,4,5,6,7] I'd like a simple and efficient formula/algorithm that finds that at index 3 they intersect. I know I could do a search just wondering if there is a better way.

I know there is a formula to solve two lines in y = mx + b form by subtracting them from each other but my "line" isn't truly a line because its limited to the items in the list and it may have curves.

Any help is appreciated.

Answer 1

I assume one dimension in your list is assumed e.g. [9,8,7,6,5] are heights at x1,x2,x3,x4,x5 right? in that case how your list will represent curves like y=0 ?

In any case I don't think there can be any shortcut for calculating intersection of generic or random curves, best solution is to do a efficient search.

Answer 2

You could take the set-theoretic intersection of the coordinates in both lists:

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

...enumerate gives you an iterable of tuples of indexes and values - in other words, (0,9),(1,8),(2,7),etc.

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

...make sense? Of course, that won't truly give you geometric intersection - for example, [1,2] intersects with [2,1] at [x=0.5,y=1.5] - if that's what you want, then you have to solve the linear equations at each interval.

Answer 3

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

...where solve_linear_equation finds the intersection between segments (0,A0)→(1,A1) and (0,B0)→(1,B1).

Answer 4

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()

This will return the index where the two sequences have equal items, and raise a StopIteration if all item pairs are different. If you don't like this behaviour, enclose the return statement in a try statement, and at the except StopIteration clause return your favourite failure indicator (e.g. -1, None…)