我现在需要实现一个函数，计算两点间的最短LineString路径，约束条件是：两点之间可能存在一个n边形，路径不能穿过多边形内部，只能经过多边形的边或者在外部区域移动。

示例参数：

• 起点 start=(2,0)
• 终点 end=(0,1)
• 多边形 poly=[(1,0),(1,1),(1,2),(2,1)]
  预期输出是2.41（大概是√2 + 1，也就是从(2,0)到(1,1)再到(0,1)的路径长度）

我已经写了开头的代码，但后面完全不知道怎么推进了：

from shapely.geometry import LineString, Polygon, Point
def shortest_linestring(start, end, poly):
    poly = Polygon(poly)
    p1 = Point(start)
    p2 = Point(end)

恳请各位大佬给我一些思路提示！

思路提示 #

其实这个问题本质是**可见图（Visibility Graph）**的经典应用，我给你拆解几个关键步骤，一步步来就清晰了：

• 第一步：先判断直接连线是否可行
  先检查起点到终点的直线是否完全合法——也就是这条线要么在多边形外部，要么刚好沿着多边形的边，完全不穿入内部。用Shapely可以这么判断：

  direct_line = LineString([start, end])
  if not poly.contains(direct_line) and not direct_line.crosses(poly):
      # 直接连线合法，返回长度即可
      return round(direct_line.length, 2)
  

  这里要注意区分crosses（穿过多边形内部）和touches（仅接触边界）的区别，避免误判。

• 第二步：构建可见图的节点集合
  如果直接连线不行，那最短路径必然是由起点、终点、多边形的所有顶点这些点之间的合法线段拼接而成的（这是可见图的核心结论：避开凸/凹多边形的最短路径，一定是这些关键点的组合）。所以先把这些点都收集起来：

  nodes = [start, end] + list(poly.exterior.coords)
  # 去重，避免多边形顶点重复或者起点/终点刚好是多边形顶点的情况
  nodes = list(set(nodes))
  

• 第三步：判断任意两点间的可见性
  对每一对节点，判断它们之间的连线是否合法（不穿入多边形内部）。写一个辅助函数来做这件事：

  def is_visible(point_a, point_b, poly):
      line = LineString([point_a, point_b])
      # 情况1：连线完全在多边形内部，直接不可见
      if poly.contains(line):
          return False
      # 情况2：连线和多边形内部相交（排除仅接触边界的情况）
      intersection = line.intersection(poly)
      # 合法的交集只能是空（完全在外部）、单个点（接触顶点）、或者线段（沿着多边形边）
      return intersection.is_empty or isinstance(intersection, (Point, LineString))
  

  这里要多测试几种边界情况，比如两个点都是多边形顶点，它们之间的边本身属于多边形，这时候应该返回True。

• 第四步：用最短路径算法求解
  把可见图转换成加权图，每个节点是坐标，边的权重是两点间的直线距离，然后用Dijkstra算法找最短路径。推荐用networkx库来简化这个过程：

  import networkx as nx
  
  # 创建无向加权图
  G = nx.Graph()
  # 添加所有节点
  for idx, node in enumerate(nodes):
      G.add_node(idx, pos=node)
  # 添加可见的边
  for i in range(len(nodes)):
      for j in range(i+1, len(nodes)):
          if is_visible(nodes[i], nodes[j], poly):
              distance = Point(nodes[i]).distance(Point(nodes[j]))
              G.add_edge(i, j, weight=distance)
  # 找到起点和终点在节点列表中的索引
  start_idx = nodes.index(start)
  end_idx = nodes.index(end)
  # 计算最短路径长度并保留两位小数
  shortest_length = nx.shortest_path_length(G, source=start_idx, target=end_idx, weight='weight')
  return round(shortest_length, 2)
  

  这样得到的结果就和示例预期的2.41一致了。

• 第五步：处理特殊场景
  比如起点/终点刚好在多边形的边上或者顶点上，这时候要确保判断可见性的时候不会误判；还有多边形是凹多边形的情况，可见图的构建要覆盖所有顶点，不能遗漏。

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