集/线交点解

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

...enumerate 为您提供索引和值的元组的可迭代 - 换句话说， (0,9),(1,8),(2,7 ），ETC。

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

我假设你的列表中的一个维度是假设的，例如 [9,8,7,6,5] 的高度为 x1,x2,x3,x4,x5，对吧？在这种情况下，您的列表将如何表示像 y=0 这样的曲线？

无论如何，我认为计算通用或随机曲线的交集没有任何捷径，最好的解决方案是进行有效的搜索。

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

这将返回两个序列具有相同项目的索引，如果所有项目对都不同，则引发 StopIteration。如果您不喜欢这种行为，请将 return 语句括在 try 语句中，并在 except StopIteration 子句中返回您最喜欢的失败指示符（例如 -1、None...）