如何找到给定 dims+1 点的任意维球体的中心和半径

Question

给定一个 N 维点向量。该向量的大小为 N+1。是否有一种通用算法可以使用球体与这些点中的每一个相交的那些点来找到 ND 球体的中心和半径？

Answer 1

同样的问题在mathematics stackexchange上被问过，得到了建设性的回答：

Does a set of n+1 points that affinely span R^n lie on a unique (n-1)-sphere?

这是 python/numpy 中该答案中描述的算法的实现。

import numpy as np

def find_sphere_through_points(points):
    n_points, n_dim = points.shape
    if (n_points != n_dim + 1):
        raise ValueError('Number of points must be equal to 1 + dimension')
    a = np.concatenate((points, np.ones((n_points, 1))), axis=1)
    b = (points**2).sum(axis=1)
    x = np.linalg.solve(a, b)
    center = x[:-1] / 2
    radius = x[-1] + center@center
    return center, radius

为了测试这个方法，我们可以使用这个相关问题中描述的方法在球体表面生成随机点：

Generate a random sample of points distributed on the surface of a unit spher

import numpy as np

def sample_spherical(npoints, ndim=3, center=None):
    vec = np.random.randn(npoints, ndim)
    vec /= np.linalg.norm(vec, axis=1).reshape(npoints,1)
    if center is None:
        return vec
    else:
        return vec + center

n = 5
center = np.random.rand(n)
points = sample_spherical(n+1, ndim=n, center=center)

guessed_center, guessed_radius = find_sphere_through_points(points)

print('True center:\n    ', center)
print('Calc center:\n    ', guessed_center)
print('True radius:\n    ', 1.0)
print('Calc radius:\n    ', guessed_radius)

# True center:
#      [0.18150032 0.94979547 0.07719378 0.26561175 0.37509931]
# Calc center:
#      [0.18150032 0.94979547 0.07719378 0.26561175 0.37509931]
# True radius:
#      1.0
# Calc radius:
#      0.9999999999999997

Answer 2

以三点为圆心，令(X, Y)及其半径R求得如下：

(X - X0)² + (Y - Y0)² = R²
(X - X1)² + (Y - Y1)² = R²
(X - X2)² + (Y - Y2)² = R²

然后减去pair-wise就消去R,

(2X - X0 - X1)(X1 - X0) + (2Y - Y0 - Y1)(Y1 - Y0) = 0
(2X - X0 - X2)(X2 - X0) + (2Y - Y0 - Y2)(Y2 - Y0) = 0

这是两个未知数的两个线性方程组，给出了中心的坐标（实际上我们构造了两个平分线的交点）。半径来自第一个方程。

这立即推广到 D 维度。

如何找到给定 dims+1 点的任意维球体的中心和半径

How to find the center and radius of an any dimensional sphere giving dims+1 points

c++

math

triangulation