最近的交点指向python中的许多行 [英] nearest intersection point to many lines in python

问题描述

我需要一个很好的算法来计算最接近 python 中的线集合的点，最好是使用最小二乘法.我在一个不起作用的 python 实现上发现了这篇文章:

这里是噪声测试数据的生成器

n = 6P0 = np.stack((np.array([5,5])+3*np.random.random(size=2) for i in range(n)))a = np.linspace(0,2*np.pi,n)+np.random.random(size=n)*np.pi/5.0P1 = np.array([5+5*np.sin(a),5+5*np.cos(a)]).T

I need a good algorithm for calculating the point that is closest to a collection of lines in python, preferably by using least squares. I found this post on a python implementation that doesn't work:

Finding the centre of multiple lines using least squares approach in Python

And I found this resource in Matlab that everyone seems to like... but I'm not sure how to convert it to python:

https://www.mathworks.com/matlabcentral/fileexchange/37192-intersection-point-of-lines-in-3d-space

I find it hard to believe that someone hasn't already done this... surely this is part of numpy or a standard package, right? I'm probably just not searching for the right terms - but I haven't been able to find it yet. I'd be fine with defining lines by two points each or by a point and a direction. Any help would be greatly appreciated!

Here's an example set of points that I'm working with:

initial XYZ points for the first set of lines

array([[-7.07107037,  7.07106748,  1. ],
       [-7.34818339,  6.78264559,  1. ],
       [-7.61352972,  6.48335745,  1. ],
       [-7.8667115 ,  6.17372055,  1. ],
       [-8.1072994 ,  5.85420065,  1. ]])

the angles that belong to the first set of lines

[-44.504854, -42.029223, -41.278573, -37.145774, -34.097022]

initial XYZ points for the second set of lines

array([[ 0., -20. ,  1. ],
       [ 7.99789129e-01, -19.9839984,  1. ],
       [ 1.59830153e+00, -19.9360366,  1. ],
       [ 2.39423914e+00, -19.8561769,  1. ],
       [ 3.18637019e+00, -19.7445510,  1. ]])

the angles that belong to the second set of lines

[89.13244, 92.39087, 94.86425, 98.91849, 99.83488]

The solution should be the origin or very near it (the data is just a little noisy, which is why the lines don't perfectly intersect at a single point).

解决方案

Here's a numpy solution using the method described in this link

def intersect(P0,P1):
    """P0 and P1 are NxD arrays defining N lines.
    D is the dimension of the space. This function 
    returns the least squares intersection of the N
    lines from the system given by eq. 13 in 
    http://cal.cs.illinois.edu/~johannes/research/LS_line_intersect.pdf.
    """
    # generate all line direction vectors 
    n = (P1-P0)/np.linalg.norm(P1-P0,axis=1)[:,np.newaxis] # normalized

    # generate the array of all projectors 
    projs = np.eye(n.shape[1]) - n[:,:,np.newaxis]*n[:,np.newaxis]  # I - n*n.T
    # see fig. 1 

    # generate R matrix and q vector
    R = projs.sum(axis=0)
    q = (projs @ P0[:,:,np.newaxis]).sum(axis=0)

    # solve the least squares problem for the 
    # intersection point p: Rp = q
    p = np.linalg.lstsq(R,q,rcond=None)[0]

    return p

Works

Edit: here is a generator for noisy test data

n = 6
P0 = np.stack((np.array([5,5])+3*np.random.random(size=2) for i in range(n)))
a = np.linspace(0,2*np.pi,n)+np.random.random(size=n)*np.pi/5.0
P1 = np.array([5+5*np.sin(a),5+5*np.cos(a)]).T

这篇关于最近的交点指向python中的许多行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！