从 SVG 路网到融合最短路径规划算法

在停车场导航、商场室内导览等场景中，常需要在一张 SVG 矢量图上高亮显示两点之间的最短路径。核心任务是将视觉上的道路转换成一张无向加权图，再用 Dijkstra 算法求解。实际工程里，SVG 数据常存在坐标浮点抖动、起终点不在道路上、路径分割后产生退化线段等问题。若不在图构建和寻路环节做好容错，算法极易跑偏甚至崩溃。

本文以 Paper.js 作为几何操作基础，去除所有框架特定干扰，聚焦于**最短路径算法**和**图构建的容错处理**，适合需要将 SVG 路网转为图并执行最短路径计算的开发者直接参考。

---

## 从道路线条提取图结构

SVG 中的道路通常被组织在一个 Group 内，包含多条 `Path`。每条 `Path` 由若干 `Segment`（线段顶点）组成。提取策略是：**将所有线段端点作为图的节点，线段长度作为边的权重**。

以下函数遍历道路组中的所有路径，构造节点集合和邻接表。

```javascript
function getMap(mapPath) {
  const points = {}         // 节点名 → Point 对象
  const pointsMapFast = {}  // 邻接表：{ 节点名: [{ to, weight }] }

mapPath.forEach(path => {
    path.segments.forEach(segment => {
      const currName = pName(segment.point, points)
      points[currName] = segment.point.clone()

if (segment.previous) {
        const prevName = pName(segment.previous.point, points)
        points[prevName] = segment.previous.point.clone()
        const weight = segment.point.subtract(segment.previous.point).length
        if (weight > 0.01) {   // 过滤极短线，避免冗余节点
          addEdge(pointsMapFast, currName, prevName, weight)
          addEdge(pointsMapFast, prevName, currName, weight)
        }
      }

if (segment.next) {
        const nextName = pName(segment.next.point, points)
        points[nextName] = segment.next.point.clone()
        const weight = segment.next.point.subtract(segment.point).length
        if (weight > 0.01) {
          addEdge(pointsMapFast, currName, nextName, weight)
          addEdge(pointsMapFast, nextName, currName, weight)
        }
      }
    })
  })

return { points, pointsMapFast, pointNames: Object.keys(points) }
}

function addEdge(graph, from, to, weight) {
  if (!graph[from]) graph[from] = []
  graph[from].push({ to, weight })
}
```

### 容错核心：浮点坐标去重

若直接使用原始坐标作为节点名，`1.00001` 和 `1.00000` 会被当作两个不同点，导致原本连通的道路断裂。因此使用 `pName` 函数对坐标进行舍入和邻近点合并：

```javascript
function pName(p, pointMap) {
  const x = p.x.toFixed(5)
  const y = p.y.toFixed(5)
  let name = `${x}_${y}`

// 检查是否已存在距离 < 2 单位的邻近节点
  for (let key in pointMap) {
    if (pointMap[key].getDistance(new Point(x, y)) < 2) {
      return key   // 复用已有节点名
    }
  }
  return name
}
```

此处同时应用两个策略：  
- **`toFixed(5)`** 吸收微小的浮点误差；  
- **距离阈值 `2`** 将物理上非常靠近的端点视为同一个节点，避免图被不必要地割裂。阈值可根据地图尺寸调整，过小易漏合并，过大则可能误合并不同道路。

---

## 起终点接入道路网

电梯、车位等兴趣点通常不在道路线上，需要将它们投影到路网中，并确保连接线真正成为图的一部分。

### 寻找最近道路点

在道路 Group 上对目标点进行最近点查询：

```javascript
function getNearestPointOnGroup(roadGroup, targetPoint) {
  let minDist = Infinity
  let nearest = null
  roadGroup.children.forEach(path => {
    const loc = path.getNearestPoint(targetPoint)
    const dist = loc.getDistance(targetPoint)
    if (dist < minDist) {
      minDist = dist
      nearest = loc
    }
  })
  return nearest
}
```

### 生成接入线段并分割道路

从兴趣点向最近道路点方向延伸一小段，构成一条线段；然后将该线段与原有道路求交点，在交点处将道路一分为二，接入点便真正“嵌”进了路网。

```javascript
function createConnectLine(fromPoint, roadNearest) {
  const dir = roadNearest.subtract(fromPoint).normalize().multiply(0.2)
  const endPoint = roadNearest.add(dir)
  return new Path({
    segments: [[fromPoint.x, fromPoint.y], [endPoint.x, endPoint.y]]
  })
}

function mergeLinesIntoRoad(connectLine, roadGroup) {
  roadGroup.children.forEach(roadPath => {
    if (roadPath.intersects(connectLine)) {
      const intersections = roadPath.getIntersections(connectLine)
      if (intersections.length > 0) {
        const newPath = roadPath.splitAt(intersections[0])
        if (newPath && newPath.segments.length >= 2) {
          roadGroup.addChild(newPath)   // 有效新路径加入路网
        }
        // 原路径若退化则移除
        if (roadPath.segments.length < 2) {
          roadPath.remove()
        }
      }
    }
  })
}
```

**容错要点**：分割后必须检查新路径是否至少包含两个点，长度不足的路径属于退化数据，不应留在路网中。同时，若原路径只剩一个点，也应及时清除。

---

## Dijkstra 最短路径算法

图构建完成且起终点正确接入后，即可使用经典的 Dijkstra 算法计算最短路径。以下是一个带容错处理的实现。

```javascript
function dijkstra(graph, start, end) {
  // 节点存在性检查
  if (!graph[start] || !graph[end]) {
    return { success: false, message: '起点或终点不在路网中' }
  }
  if (start === end) {
    return { success: true, path: [start], distance: 0 }
  }

const distances = {}
  const previous = {}
  const visited = new Set()

for (let node in graph) {
    distances[node] = Infinity
    previous[node] = null
  }
  distances[start] = 0

const totalNodes = Object.keys(graph).length
  for (let i = 0; i < totalNodes; i++) {
    // 从未访问节点中选择距离最小的
    let minNode = null
    let minDist = Infinity
    for (let node in graph) {
      if (!visited.has(node) && distances[node] < minDist) {
        minDist = distances[node]
        minNode = node
      }
    }

if (minNode === null) break     // 无可达节点，提前结束
    visited.add(minNode)

// 松弛相邻边
    (graph[minNode] || []).forEach(neighbor => {
      if (!visited.has(neighbor.to)) {
        const newDist = distances[minNode] + neighbor.weight
        if (newDist < distances[neighbor.to]) {
          distances[neighbor.to] = newDist
          previous[neighbor.to] = minNode
        }
      }
    })
  }

// 不可达检查
  if (distances[end] === Infinity) {
    return { success: false, message: '无法到达终点（非连通图）' }
  }

// 回溯路径
  const path = []
  let current = end
  while (current) {
    path.unshift(current)
    current = previous[current]
  }

return { success: true, path, distance: distances[end] }
}
```

**算法中的容错点**：  
- 起终点不存在时直接返回错误，避免无效计算。  
- 循环中当 `minNode` 为 `null` 时提前退出，防止死循环。  
- 检查最终距离是否为 `Infinity`，处理非连通图的情况。

---

## 总结

将 SVG 地图用于最短路径导航，关键在于三个环节的正确性和鲁棒性：

1. **从线条精确提取图结构**——通过坐标舍入和邻近点合并，避免因浮点误差导致的图断裂。  
2. **兴趣点接入路网**——依靠最近点投影与路径分割，确保起终点真正成为图节点。  
3. **Dijkstra 算法**——在标准实现基础上加入边界条件检查，从容应对缺失节点、非连通图等异常。