Python 3中寻找三维立方体里离n个点最远的点

我明白你遇到的问题——用Voronoi图得到的顶点经常跑到立方体外面，没法直接用。其实这个问题本质上是一个带约束的优化问题，我们可以用数值优化的方法直接求解，不需要复杂的数学推导，下面给你一套可直接运行的代码，还有详细的解释。

问题定义 #

先明确一下：我们要在指定的三维立方体范围内，找到一个点，使得这个点到所有已知点的最小距离尽可能大（也就是这个点是立方体内离所有已知点都最远的“最远点”）。如果你的需求是找到到某个已知点距离最大的点，那其实直接取立方体的顶点中离该点最远的那个就行，但我猜你要的是前者——离所有已知点的最近距离最大的点，这也是Voronoi图相关的典型问题。

可直接运行的代码 #

import numpy as np
from scipy.optimize import minimize

def find_farthest_point_in_cube(known_points, cube_bounds):
    """
    在指定立方体内找到离所有已知点最小距离最大的点
    
    参数:
        known_points: 已知点的numpy数组，形状为(n, 3)，n是已知点数量
        cube_bounds: 立方体的边界，形状为(3, 2)，每个维度是[min, max]，比如[[0,1], [0,1], [0,1]]表示单位立方体
    返回:
        best_point: 最优点的坐标，形状为(3,)
        max_min_distance: 该点到所有已知点的最小距离
    """
    # 立方体的边界约束
    x_min, x_max = cube_bounds[0]
    y_min, y_max = cube_bounds[1]
    z_min, z_max = cube_bounds[2]
    bounds = [(x_min, x_max), (y_min, y_max), (z_min, z_max)]
    
    # 目标函数：我们要最大化最小距离，等价于最小化负的最小距离
    def objective(x):
        # x是[px, py, pz]，计算到所有已知点的距离
        distances = np.linalg.norm(known_points - x, axis=1)
        # 返回负的最小距离，因为minimize是求最小值
        return -np.min(distances)
    
    # 初始猜测点：选立方体的中心
    initial_guess = np.array([(x_min+x_max)/2, (y_min+y_max)/2, (z_min+z_max)/2])
    
    # 求解优化问题，用SLSQP方法（支持边界和不等式约束，这里我们只需要边界约束）
    result = minimize(objective, initial_guess, method='SLSQP', bounds=bounds)
    
    # 提取结果
    best_point = result.x
    max_min_distance = -result.fun
    
    return best_point, max_min_distance

# ------------------- 示例使用 -------------------
if __name__ == "__main__":
    # 生成5个随机已知点（在单位立方体内）
    np.random.seed(42)
    known_points = np.random.rand(5, 3)
    
    # 定义立方体边界：这里用单位立方体[0,1]^3，你可以改成自己的范围
    cube_bounds = [[0, 1], [0, 1], [0, 1]]
    
    # 寻找最优解
    best_point, max_dist = find_farthest_point_in_cube(known_points, cube_bounds)
    
    print(f"找到的最优点坐标: {best_point.round(4)}")
    print(f"该点到所有已知点的最小距离: {max_dist.round(4)}")

代码解释 #

1. 边界设置：cube_bounds定义了立方体在x、y、z三个维度的范围，你可以根据自己的需求修改。
2. 目标函数：我们把“最大化最小距离”转化为“最小化负的最小距离”，因为scipy.optimize.minimize只能求最小值。
3. 初始猜测：选立方体的中心作为初始点，这个点通常能让优化快速收敛到最优解。
4. 优化方法：用SLSQP方法，它支持边界约束，非常适合这类带范围限制的优化问题。

为什么Voronoi图不行？ #

Voronoi图的顶点是到多个已知点距离相等的点，但这些顶点不一定在立方体内。如果想用Voronoi的思路，你可以：

• 先计算所有Voronoi顶点
• 把那些在立方体外的顶点投影到立方体的表面/内部
• 再把立方体的8个顶点、6个面的中心、12条棱的中心都加入候选点
• 最后计算所有候选点到已知点的最小距离，选最大的那个

不过这种方法需要处理很多边缘情况（比如投影的逻辑），不如直接用数值优化来得简单可靠。

补充说明 #

如果你的需求是找到立方体内到某个特定已知点距离最大的点，那更简单：直接计算立方体的8个顶点到该点的距离，选最大的那个就行，代码示例：

def farthest_vertex_to_point(target_point, cube_bounds):
    x_min, x_max = cube_bounds[0]
    y_min, y_max = cube_bounds[1]
    z_min, z_max = cube_bounds[2]
    # 生成立方体的8个顶点
    vertices = np.array([
        [x_min, y_min, z_min],
        [x_min, y_min, z_max],
        [x_min, y_max, z_min],
        [x_min, y_max, z_max],
        [x_max, y_min, z_min],
        [x_max, y_min, z_max],
        [x_max, y_max, z_min],
        [x_max, y_max, z_max]
    ])
    # 计算距离
    distances = np.linalg.norm(vertices - target_point, axis=1)
    # 找到最远的顶点
    farthest_idx = np.argmax(distances)
    return vertices[farthest_idx], distances[farthest_idx]

内容的提问来源于stack exchange，提问作者Theo