numpy 查找与4个点等距的点

xesrikrc  于 11个月前  发布在  其他
关注(0)|答案(4)|浏览(110)

这段代码需要很长的时间来找到一个点。有没有更好的方法来找到一个点,是等距的4个给定的点?公差为0.5是罚款。

import numpy as np

# Define the four 3D points as (x, y, z) coordinates
point1 = np.array([1, 2, 3])
point2 = np.array([3, 4, 5])
point3 = np.array([5, 6, 7])
point4 = np.array([7, 8, 9])

# Set a tolerance for distance equality
tolerance = 0.5

# Calculate the initial average point
average_point = np.mean([point1, point2, point3, point4], axis=0)

while True:
    distances = np.linalg.norm(average_point - np.array([point1, point2, point3, point4]), axis=1)
    max_distance = np.max(distances)
    min_distance = np.min(distances)

    if max_distance - min_distance <= tolerance:
        break

    # Update the average point by moving it closer to the farthest point
    farthest_point = np.argmax(distances)
    average_point = average_point + 0.5 * (point1 - average_point)

print("Average point with relatively equal distances:", average_point)

字符串

wljmcqd8

wljmcqd81#

你也可以用代数方法来解决这个问题,而不是通过几何或优化/最小化。
如果这些点是不同的,并且位于一个球体上,那么它们有一个唯一的等距点。对于不同的点,这是可以的,除非至少有三个点位于一条线上(原始帖子中的情况)或者所有四个点都是共面的。
设中心为(a,b,c),半径为R,则四个点(x,y,z)中的每一个满足
x1c 0d1x的数据
它会增殖并重新排列,



现在,为了消除R(以及中心坐标a,B,c中的二次项),从点0减去点1的方程,从点0减去点2的方程,从点0减去点3的方程。你得到三个方程,可以写成矩阵方程



求解(例如通过高斯消去法)中心(a,b,c),然后代入任何原始方程得到R。
如果矩阵不可逆,也就是说矩阵的行列式为零,则解失败。如果两行是彼此的倍数(直线上的三个点),或者一行是其他两行的线性组合(点共面),则会发生这种情况。

import numpy as np
import math

def GaussElimination( A, b ):
    SMALL = 1.0e-10
    n = len( A[0] )
    x = np.zeros( n )

    for i in range( n - 1 ):
        # Pivot: swap rows to get largest value in column i
        r = i
        maxA = abs( A[i,i] )
        for k in range( i + 1, n ):
            val = abs( A[k,i] )
            if val > maxA: r, maxA = k, val
        if r != i:
            A[i,i:], A[r,i:] = A[r,i:].copy(), A[i,i:].copy()
            b[i], b[r] = b[r], b[i]
   
        # Row operations to make upper-triangular
        pivot = A[i,i]
        if ( abs( pivot ) < SMALL ): return A, False       # Singular matrix
        for r in range( i + 1, n ):                        # On lower rows
            multiple = A[r,i] / pivot                      # Multiple of row i to clear element in ith column
            A[r,i:] -= multiple * A[i,i:]
            b[r]    -= multiple * b[i]
        if abs( A[n-1,n-1] ) < SMALL: return A, False      # Singular matrix

    # Back-substitute
    for i in range( n-1, -1, -1 ): x[i] = ( b[i] - np.sum( A[i,i+1:] * x[i+1:] ) ) / A[i,i]

    return x, True

####################################################################################################

pts = [ np.array( [ 10.0,  2.0,  3.0 ] ),                       # list of points
        np.array( [  3.0, 40.0,  5.0 ] ),
        np.array( [ 50.0,  6.0,  7.0 ] ),
        np.array( [  7.0,  8.0, 90.0 ] ) ]

A = np.zeros( ( 3, 3 ) )                                        # set up matrix equation for centre
b = np.zeros( 3 )
for i in range( 1, 4 ):
    for j in range( 3 ): A[i-1,j] = pts[0][j] - pts[i][j]
    b[i-1] = 0.5 * np.sum( pts[0] ** 2 - pts[i] ** 2 )

centre, ok = GaussElimination( A, b )                           # solve for centre
if ok:
    R = math.sqrt( np.sum( ( pts[0] - centre ) ** 2 ) )         # find radius (i.e. common distance)
    print( "Centre = ", centre, "\nDistance = ", R )
else:
    print( "Can't find point" )

字符串
对于@aerobiomat提供的案例:

Centre =  [24.10963855 22.04056225 45.86305221] 
Distance =  49.375573718630044

编辑对于那些喜欢库例程的人

如果你更喜欢使用numpy矩阵求解器,那么它要短得多:

import numpy as np
import math

pts = [ np.array( [ 10.0,  2.0,  3.0 ] ),                       # list of points
        np.array( [  3.0, 40.0,  5.0 ] ),
        np.array( [ 50.0,  6.0,  7.0 ] ),
        np.array( [  7.0,  8.0, 90.0 ] ) ]

A = np.zeros( ( 3, 3 ) )                                        # set up matrix equation for centre
b = np.zeros( 3 )
for i in range( 1, 4 ):
    for j in range( 3 ): A[i-1,j] = pts[0][j] - pts[i][j]
    b[i-1] = 0.5 * np.sum( pts[0] ** 2 - pts[i] ** 2 )

try:
    centre = np.linalg.solve( A, b )                            # solve for centre
    R = math.sqrt( np.sum( ( pts[0] - centre ) ** 2 ) )         # find radius (i.e. common distance)
    print( "Centre = ", centre, "\nDistance = ", R )
except np.linalg.LinAlgError:
    print( "Can't find point" )

ergxz8rk

ergxz8rk2#

这个问题一般没有解,但可以使用最小化方法获得近似值。
如果这些点是:

>>> points = np.array([[10,  2,  3],
...                    [ 3, 40,  5],
...                    [50,  6,  7],
...                    [ 7,  8, 90]])

字符串
误差函数可以定义为距离的方差:

>>> def distance_error(x, pts):
...     dist = np.sqrt(np.sum((pts - x) ** 2, axis=1))
...     return np.var(dist)


然后,最佳点p可以通过最小化误差函数来找到:

>>> from scipy.optimize import minimize
>>> p = minimize(distance_error, x0=(0,0,0), args=points).x
>>> p
array([24.10963833, 22.04056223, 45.86305227])


距离是:

>>> np.sqrt(np.sum((points - p)**2, axis=1))
array([49.3755737 , 49.37557368, 49.37557388, 49.37557358])

mcdcgff0

mcdcgff03#

为什么要使用循环?让我向你展示如何在2D中做到这一点:


的数据
你需要找到点ABC之间相同距离的点。为了做到这一点,你需要AB的垂直平分线,你还需要AC的垂直平分线,两者的交点给你点D,这就是解决方案。
为了证明后者,我们以D为圆心画了一个圆,正如你所看到的,这个圆包含了点ABC,证明了D与这三个起点的距离是相同的。
只要将这个推理扩展到3D,你就有了解决方案,正如你所看到的,不需要循环。

yvt65v4c

yvt65v4c4#

这个基于两个平分线相交的方法不太好用。@Dominique你能看一下吗?

import numpy as np

# Define the four 3D points as (x, y, z) coordinates
point1 = np.array([10, 2, 3])
point2 = np.array([3, 40, 5])
point3 = np.array([50, 6, 7])
point4 = np.array([7, 8, 90])

# Calculate the midpoint of a line segment between two points
def midpoint(point1, point2):
    return (point1 + point2) / 2

# Calculate the direction vector of the line
def direction_vector(point1, point2):
    return point2 - point1

# Calculate the negative reciprocal of the slopes in 3D
def perpendicular_slopes_3d(point1, point2):
    return -direction_vector(point1, point2)

# Calculate the equation of the perpendicular bisector in 3D
def perpendicular_bisector_3d(point1, point2):
    mid = midpoint(point1, point2)
    perp_slope = perpendicular_slopes_3d(point1, point2)
    return (mid, perp_slope)

# Calculate the perpendicular bisectors for each pair of points
bisector12 = perpendicular_bisector_3d(point1, point2)
bisector34 = perpendicular_bisector_3d(point3, point4)

# Solve for the intersection point in 3D
mid1, dir1 = bisector12
mid2, dir2 = bisector34

# Calculate the intersection point by finding the point of closest approach between the two lines
dir1_normalized = dir1 / np.linalg.norm(dir1)
dir2_normalized = dir2 / np.linalg.norm(dir2)

# Parameters for the lines
t1 = np.dot(mid2 - mid1, dir1_normalized) / np.dot(dir1_normalized, dir1_normalized)
t2 = np.dot(mid2 - mid1, dir2_normalized) / np.dot(dir2_normalized, dir2_normalized)

intersection_point = mid1 + t1 * dir1_normalized

# Calculate distances between the intersection point and all given points in 3D
distances = [np.linalg.norm(intersection_point - point) for point in [point1, point2, point3, point4]]

# Print the distances
for i, point in enumerate([point1, point2, point3, point4]):
    print(f"Distance between intersection and point {i + 1}: {distances[i]}")

# Print the intersection point
print("Intersection point in 3D:", intersection_point)

字符串
其结果

Distance between intersection and point 1: 3.9156307702153543
Distance between intersection and point 2: 34.77545347409085
Distance between intersection and point 3: 40.885458802402674
Distance between intersection and point 4: 86.8545619404054
Intersection point in 3D: [9.29158317 5.84569138 3.20240481]

相关问题