集合与直线交点的解法

Question

我在Python里有两个列表，我想知道它们在相同的索引位置是否有相同的元素。有没有什么数学方法可以解决这个问题呢？

比如说，如果我有两个列表：[9,8,7,6,5] 和 [3,4,5,6,7]，我想要一个简单高效的公式或算法，能找到它们在索引3的位置是相同的。我知道可以通过搜索来找，但我在想有没有更好的方法。

我知道有一种公式可以通过相减来解决两个y = mx + b形式的直线问题，但我的“直线”其实并不是真正的直线，因为它只限于列表里的元素，而且可能会有曲线。

任何帮助都非常感谢。

Answer 1

我假设你列表中的一个维度是固定的，比如说 [9,8,7,6,5] 代表的是在 x1, x2, x3, x4, x5 这些位置的高度，对吧？那么在这种情况下，你的列表是怎么表示像 y=0 这样的曲线的呢？

无论如何，我觉得没有什么简单的方法可以用来计算一般或随机曲线的交点，最好的办法就是进行高效的搜索。

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

你可以把两个列表中坐标的交集拿出来：

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

...enumerate会给你一个可遍历的元组，里面包含索引和对应的值，也就是说，它会像这样返回(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] - 如果你想要这样的结果，那你就得在每个区间里解线性方程。