1

我有两点系列

A = [(18.405316791178798, -22.039859853332942),
 (18.372696520198463, -21.1145),
 (18.746540658574137, -20.1145),
 (18.698714698430614, -19.1145),
 (18.80081378263931, -18.1145),
 (18.838536172339943, -17.1145),
 (18.876258562040572, -16.1145),
 (18.967679510389303, -15.1145),
 (19.004907703822514, -14.1145),
 (19.042135897255729, -13.1145),
 (19.345372798084995, -12.1145),
 (19.391824245372803, -11.598937753853679),
 (19.435471418833544, -11.1145),
 (19.420235820376909, -10.1145),
 (19.423148861774159, -9.1145),
 (19.426061903171416, -8.1145),
 (19.452752569112423, -7.1145),
 (19.489649834463115, -6.1145),
 (19.444635952332344, -5.1145),
 (19.443635102001071, -5.0430597023976906),
 (19.430626347601358, -4.1145),
 (19.421676068414001, -3.1144999999999996),
 (19.362954522948439, -2.1144999999999996),
 (19.346848825989134, -1.1144999999999996),
 (19.359781116687397, -0.1144999999999996),
 (19.396797325132418, 0.69011368336827994)]

B=[(21.7744, -17.859620414326386),
 (22.7744, -17.858000854574556),
 (23.7744, -18.065164294951039),
 (24.7744, -18.051109497755608),
 (25.7744, -18.037054700560173),
 (26.7744, -18.022999903364742),
 (27.7744, -18.008945106169307),
 (28.7744, -18.014846881456318),
 (29.7744, -18.02764295838865),
 (30.7744, -18.098340990366935)]

我确信它们会相交，如果其中一个要从一个头伸出。

现在，我希望找到他们的“潜在”交集。我编写了一个函数，可以找到“已经相交”点系列的交点：

# find the intersection between two line segments
# if none, return None
# else, return sequence numbers in both rep1 and rep2 and the intersection
def _findIntersection(rep1, rep2):
    x_down = [elem[0] for elem in rep1]
    y_down = [elem[1] for elem in rep1]
    x_up = [elem[0] for elem in rep2]
    y_up = [elem[1] for elem in rep2]
    for m in xrange(len(x_down)-1):
        p0 = np.array([x_down[m], y_down[m]])
        p1 = np.array([x_down[m+1], y_down[m+1]])
        for n in xrange(len(x_up)-1):
            q0 = np.array([x_up[n], y_up[n]])
            q1 = np.array([x_up[n+1], y_up[n+1]])
            try: # to ignore the parallel cases
                params = np.linalg.solve(np.column_stack((p1-p0, q0-q1)), q0-p0)
                if np.all((params >= 0) & (params <= 1)):
                    return m, n, ((p0+params[0]*(p1-p0))[0], (p0+params[0]*(p1-p0))[1])
            except:
                pass

所以，我认为我需要找出需要扩展哪个点系列的哪一端。只要我知道这一点，我可以简单地扩展它并找到与现有的交集_findIntersection()。

在这个问题中，我们可以有把握地假设两个点序列大致都是直线，这意味着只存在一个交点。

我正在使用 Python，但也非常欢迎任何通用解决方案！

4

2 回答 2

3

我认为这样做的一种方法是找到两条线的功能，然后使用这些功能，找到交点。这是我使用 numpy 的方法（假设线条是线性的）：

import numpy as np

def find_func(x,y):
    return np.polyfit(x, y, 1)

def find_intersect(funcA, funcB):
    a = funcA[0]-funcB[0]
    b = funcB[1]-funcA[1]
    x = b / a 
    assert np.around(find_y(funcA,x),3) == np.around(find_y(funcB,x),3)
    return x, find_y(funcA,x)

def find_y(func, x):
    return func[0] * x + func[1]


#find fits
func_A = find_func(A[:,1],A[:,0])
func_B = find_func(B[:,1],B[:,0])

#find intersection
x_intersect, y_intersect = find_intersect(func_A, func_B)

这是近似线性交点的绘制输出：

近似交点

于 2013-11-10T12:36:45.573 回答
2

首先，获取每个点系列的回归线。通过将线的各自点系列的端点投影到线本身上，将线转换为线段 s1 和 s2。

从线性代数的角度来看问题，两条线段是向量。除非它们是平行的或共线的，否则将每个向量与给定的系数相乘将导致它们一直延伸到交点。因此，您需要找到系数 alpha 和 beta 使得alpha * s1 = beta * s2. 换句话说，求解线性方程alpha * s1 + beta * (-s1) = 0，就像您已经对各个线段所做的那样。

您需要注意三种情况。

  1. 如果 alpha 和 beta 的绝对值都小于或等于 1，则交点在两条线段内。
  2. 如果一个绝对值 <=1 但另一个绝对值 >1，则交点 i 仅位于两条线段之一（例如 s2）内。将该线段的向量乘以刚刚得到的系数，然后加上向量的原点，得到交点。然后，您可以确定另一条线段（在本例中为 s1）中的哪个端点更靠近交点；越近的就是要延伸的那一个。
  3. 如果两个绝对值都 > 1，只需将 s1 与 (alpha / beta) 相乘，然后将 s1[0] 添加到该交点即可。找到交点后，只需在每条线段上找到离它最近的端点。这些是点系列必须从其扩展的两个端点。
于 2013-11-10T14:17:24.490 回答