无穿越物体的TSP路径规划：多形状适配的路径优化需求

问题背景 #

现有一组构成立方体表面的网格点集合，使用结合2-Opt优化的TSP算法生成遍历路径时，出现路径穿越立方体内侧的情况。尝试过将不同表面点间距离设为无穷大，导致无可行路径；限制单轴移动仅适用于立方体，无法适配其他形状。

解决方案思路 #

核心是用物体表面的测地距离代替欧氏直线距离，让TSP算法基于表面最短路径进行优化，从根源避免穿越。同时优化初始路径生成逻辑，配合2-Opt时的有效性判断，保证路径仅沿表面行进。

关键步骤 #

• 点集去重：原始点集存在大量重复点，先去重减少计算量，避免路径重复遍历同一位置。
• 计算测地距离矩阵：对于多面体表面的任意两点，计算沿表面的最短路径长度（测地距离），而非直线距离。以立方体为例：
  • 若两点在同一表面（某一坐标轴坐标完全相同），测地距离为两点的平面欧氏距离；
  • 若两点不在同一表面，计算所有可能的表面绕行路径长度，取最小值。
• 基于测地距离的TSP优化：将距离矩阵替换为测地距离矩阵，用最近邻算法生成初始路径，再通过2-Opt优化表面路径总长度，自然规避穿越问题。

实现代码 #

import numpy as np

def deduplicate_points(points):
    """去除重复点，保留唯一坐标"""
    _, idx = np.unique(points.round(decimals=6), axis=0, return_index=True)
    return points[np.sort(idx)]

def cube_geodesic_distance(p1, p2):
    """计算立方体表面两点的测地距离，立方体边长为100"""
    # 判断是否在同一表面
    if p1[0] == p2[0]:
        # Y-Z平面
        return np.linalg.norm(p1[1:] - p2[1:])
    elif p1[1] == p2[1]:
        # X-Z平面
        return np.linalg.norm(p1[[0,2]] - p2[[0,2]])
    elif p1[2] == p2[2]:
        # X-Y平面
        return np.linalg.norm(p1[:2] - p2[:2])
    else:
        # 不在同一表面，计算所有绕行路径的最短长度
        L = 100
        # 三种绕行路径
        d1 = np.linalg.norm(p1 - [p2[0], p1[1], p1[2]]) + np.linalg.norm([p2[0], p1[1], p1[2]] - p2)
        d2 = np.linalg.norm(p1 - [p1[0], p2[1], p1[2]]) + np.linalg.norm([p1[0], p2[1], p1[2]] - p2)
        d3 = np.linalg.norm(p1 - [p1[0], p1[1], p2[2]]) + np.linalg.norm([p1[0], p1[1], p2[2]] - p2)
        return min(d1, d2, d3)

def build_geodesic_dist_matrix(points, distance_func):
    """构建测地距离矩阵"""
    n = len(points)
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(i+1, n):
            dist = distance_func(points[i], points[j])
            dist_matrix[i][j] = dist
            dist_matrix[j][i] = dist
    return dist_matrix

def tsp_2opt_geodesic(points, distance_func):
    # 去重处理
    points = deduplicate_points(points)
    n = len(points)
    if n <= 1:
        return points

    # 构建测地距离矩阵
    dist_matrix = build_geodesic_dist_matrix(points, distance_func)

    # 最近邻生成初始路径
    unvisited = set(range(n))
    curr_point = 0
    tour = [curr_point]
    unvisited.remove(curr_point)
    while unvisited:
        next_point = min(unvisited, key=lambda x: dist_matrix[curr_point, x])
        tour.append(next_point)
        unvisited.remove(next_point)
        curr_point = next_point

    # 2-Opt优化（基于测地距离）
    improved = True
    while improved:
        improved = False
        for i in range(n-2):
            for j in range(i+2, n):
                old_dist = dist_matrix[tour[i], tour[i+1]] + dist_matrix[tour[j], tour[(j+1)%n]]
                new_dist = dist_matrix[tour[i], tour[j]] + dist_matrix[tour[i+1], tour[(j+1)%n]]
                if new_dist < old_dist:
                    tour[i+1:j+1] = reversed(tour[i+1:j+1])
                    improved = True
    return points[np.array(tour)]

# 使用示例
if __name__ == "__main__":
    # 原始点集
    raw_points = np.array([
        [  0., 100., 100.], [  0., 100.,  50.], [  0., 100.,   0.],
        [ 50., 100., 100.], [ 50., 100.,  50.], [ 50., 100.,   0.],
        [100., 100., 100.], [100., 100.,  50.], [100., 100.,   0.],
        [100.,   0.,   0.], [100.,  50.,   0.], [100., 100.,   0.],
        [100.,   0.,  50.], [100.,  50.,  50.], [100., 100.,  50.],
        [100.,   0., 100.], [100.,  50., 100.], [100., 100., 100.],
        [  0.,   0.,   0.], [  0.,  50.,   0.], [  0., 100.,   0.],
        [  0.,   0.,  50.], [  0.,  50.,  50.], [  0., 100.,  50.],
        [  0.,   0., 100.], [  0.,  50., 100.], [  0., 100., 100.],
        [  0.,   0., 100.], [  0.,  50., 100.], [  0., 100., 100.],
        [ 50.,   0., 100.], [ 50.,  50., 100.], [ 50., 100., 100.],
        [100.,   0., 100.], [100.,  50., 100.], [100., 100., 100.],
        [  0.,   0.,   0.], [  0.,  50.,   0.], [  0., 100.,   0.],
        [ 50.,   0.,   0.], [ 50.,  50.,   0.], [ 50., 100.,   0.],
        [100.,   0.,   0.], [100.,  50.,   0.], [100., 100.,   0.],
        [  0.,   0., 100.], [  0.,   0.,  50.], [  0.,   0.,   0.],
        [ 50.,   0., 100.], [ 50.,   0.,  50.], [ 50.,   0.,   0.],
        [100.,   0., 100.], [100.,   0.,  50.], [100.,   0.,   0.]
    ])
    # 生成无穿越路径
    path = tsp_2opt_geodesic(raw_points, cube_geodesic_distance)
    print("生成的无穿越路径：")
    print(path)

适配其他形状的扩展方法 #

要适配其他多面体或曲面形状，只需替换cube_geodesic_distance函数为对应形状的测地距离计算函数：

• 规则多面体（如四面体、正八面体）：可通过展开表面为平面，计算平面内直线距离的最小值；
• 复杂曲面：可使用数值方法（如快速行进法Fast Marching Method）计算两点间的测地距离。

内容的提问来源于stack exchange，提问作者A. Vreeswijk