python - 集/线交点解决方案

Question

我在 python 中有两个列表，我想知道它们是否在同一个索引处相交。有解决这个问题的数学方法吗？

例如，如果我有 [9,8,7,6,5] 和 [3,4,5,6,7] 我想要一个简单而有效的公式/算法，它发现它们在索引 3 处相交。我知道我可以进行搜索，只是想知道是否有更好的方法。

我知道有一个公式可以通过将 y = mx + b 形式的两条线彼此相减来解决它们，但我的“线”并不是真正的线，因为它仅限于列表中的项目并且它可能有曲线。

任何帮助表示赞赏。

Answer 1

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

...wheresolve_linear_equation找到线段(0,A0)→(1,A1)和之间的交集(0,B0)→(1,B1)。

Answer 3

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