迪杰斯特拉（dijkstra）算法+真实经纬度，自定义地图道路实现最短路径导航

适用于地图中的自定义道路并非记录在官方道路数据库中的道路例如自定义多条作业路线等需要自定义window.ALL_ROADS——全部道路格式为道路经纬度集合复杂度n²取决于过滤后的可用道路数量#前端算法 #求最短路径 #道路导航/** * 计算多道路路径规划 * 起点吸附到道路终点按距离排序自动寻找最短路径 * 支持道路类型过滤支持多起点择优支持道路交叉自动打断连通 * 原创代码真实经纬度自定义地图道路dijkstra算法实现 * param {number} startLng - 起点经度 * param {number} startLat - 起点纬度 * param {number} endLng - 终点经度 * param {number} endLat - 终点纬度 * param {string} roadType - 道路类型 roadNarrow/roadMedium/roadLarge * param {number} startThresholdMeter - 起点吸附半径 米 * param {number} endThresholdMeter - 终点吸附半径 预留暂未使用 * returns {Array} 路径坐标数组 [lng,lat,lng,lat,...] */ async function computeMultiRoadPath( startLng, startLat, endLng, endLat, roadType, startThresholdMeter 80, endThresholdMeter 3000 ) { try { // 获取全局道路数据 const ALL_ROADS window.ALL_ROADS || []; // 根据道路类型过滤 const filteredRoads ALL_ROADS.filter(road { if (roadType roadNarrow) return true; if (roadType roadMedium) return road.type roadMedium || road.type roadLarge; if (roadType roadLarge) return road.type roadLarge; return true; }); // 无道路直接返回空 if (!filteredRoads.length) return []; /** * 扁平坐标数组转点数组 [[lng,lat],...] * param {Array} flat - [lng,lat,lng,lat,...] * returns {Array} */ const flatToPoints flat { const r []; for (let i 0; i flat.length; i 2) r.push([flat[i], flat[i 1]]); return r; }; /** * 点数组转回扁平坐标 * param {Array} pts - [[lng,lat],...] * returns {Array} */ const pointsToFlat pts { const r []; pts.forEach(p { r.push(p[0]); r.push(p[1]); }); return r; }; /** * 计算两点真实距离 米 * param {Array} a - [lng,lat] * param {Array} b - [lng,lat] * returns {number} */ const realDistance (a, b) { const dx b[0] - a[0]; const dy (b[1] - a[1]) * Math.cos((a[1] b[1]) / 2 * Math.PI / 180); return Math.hypot(dx, dy) * 111000; }; /** * 点到线段的投影计算 * param {Array} p - 点 * param {Array} a - 线段起点 * param {Array} b - 线段终点 * returns {Object} {dist, pt} */ const pointToSegment (p, a, b) { const A p[0] - a[0], B p[1] - a[1], C b[0] - a[0], D b[1] - a[1]; const dot A * C B * D, lenSq C * C D * D; if (lenSq 1e-12) return { dist: realDistance(p, a), pt: [...a] }; const t Math.max(0, Math.min(1, dot / lenSq)); return { dist: realDistance(p, [a[0] t * C, a[1] t * D]), pt: [a[0] t * C, a[1] t * D] }; }; /** * 点投影到整条道路 * param {Array} pt - 点 * param {Array} roadPoints - 道路点集 * returns {Object} */ const projectPointToRoad (pt, roadPoints) { let minDist 999999, bestPt null; for (let i 0; i roadPoints.length - 1; i) { const r pointToSegment(pt, roadPoints[i], roadPoints[i 1]); if (r.dist minDist) { minDist r.dist; bestPt r.pt; } } return { dist: minDist, pt: bestPt }; }; /** * 将点插入到路径最合适的位置 * param {Array} path - 路径点集 * param {Array} pt - 待插入点 */ const insertPointInPath (path, pt) { let bestIdx 1, minD 999999; for (let i 0; i path.length - 1; i) { const d pointToSegment(pt, path[i], path[i 1]).dist; if (d minD) { minD d; bestIdx i 1; } } path.splice(bestIdx, 0, [...pt]); }; /** * 计算两条线段是否相交 * param {Array} a1 * param {Array} a2 * param {Array} b1 * param {Array} b2 * returns {Array|null} */ const segmentIntersection (a1, a2, b1, b2) { const ccw (p, q, r) (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]); const o1 ccw(a1, a2, b1), o2 ccw(a1, a2, b2), o3 ccw(b1, b2, a1), o4 ccw(b1, b2, a2); if (o1 * o2 0 || o3 * o4 0) return null; const den (a1[0] - a2[0]) * (b1[1] - b2[1]) - (a1[1] - a2[1]) * (b1[0] - b2[0]); if (Math.abs(den) 1e-12) return null; const t ((a1[0] - b1[0]) * (b1[1] - b2[1]) - (a1[1] - b1[1]) * (b1[0] - b2[0])) / den; return [a1[0] t * (a2[0] - a1[0]), a1[1] t * (a2[1] - a1[1])]; }; // 起点终点坐标 const start [startLng, startLat]; const end [endLng, endLat]; // 构造道路点集数据 const roadData filteredRoads.map(r ({ id: r.id, pts: flatToPoints(r.coords), type: r.type })); // 道路两两求交点插入交点实现道路连通 // 复杂度从 O(R²·P) 优化为 O(Rf²·P)Rf为过滤后道路数量大幅减少计算量 const roadCount roadData.length; for (let i 0; i roadCount; i) { const r1 roadData[i]; for (let j i 1; j roadCount; j) { const r2 roadData[j]; let cross null; outer: for (let a 0; a r1.pts.length - 1; a) { for (let b 0; b r2.pts.length - 1; b) { cross segmentIntersection(r1.pts[a], r1.pts[a 1], r2.pts[b], r2.pts[b 1]); if (cross) break outer; } } if (cross) { insertPointInPath(r1.pts, cross); insertPointInPath(r2.pts, cross); } } } // 获取所有有效起点在吸附半径内 const validStartPoints []; for (const road of roadData) { const proj projectPointToRoad(start, road.pts); if (proj.pt proj.dist startThresholdMeter) { validStartPoints.push({ road, pt: proj.pt }); } } if (validStartPoints.length 0) return []; // 获取所有终点候选 const endCandidates []; for (const road of roadData) { const proj projectPointToRoad(end, road.pts); if (proj.pt) { endCandidates.push({ road: road, pt: proj.pt, dist: proj.dist }); } } if (endCandidates.length 0) return []; // 按距离从小到大排序优先尝试最近终点 endCandidates.sort((a, b) a.dist - b.dist); let bestPath []; let bestDist 9999999; // 依次尝试每个终点直到找到可达的最短路径 for (const ec of endCandidates) { // 深拷贝道路避免多次迭代互相影响 const tempRoads JSON.parse(JSON.stringify(roadData)); const sPts validStartPoints.map(sp ({ road: tempRoads.find(r r.id sp.road.id), pt: sp.pt })); const endRoad tempRoads.find(r r.id ec.road.id); const endPt ec.pt; // 把起点和终点插入对应道路 sPts.forEach(sp insertPointInPath(sp.road.pts, sp.pt)); insertPointInPath(endRoad.pts, endPt); // 构建图节点和边 const nodeMap new Map(); const edges []; let nid 0; // 生成点唯一标识 const getKey p p[0].toFixed(6) , p[1].toFixed(6); // 获取或创建节点 const getNode p { const k getKey(p); if (!nodeMap.has(k)) nodeMap.set(k, { id: nid, pt: p }); return nodeMap.get(k); }; // 构建路网边 tempRoads.forEach(r { for (let i 0; i r.pts.length - 1; i) { const n1 getNode(r.pts[i]), n2 getNode(r.pts[i 1]); const l realDistance(n1.pt, n2.pt); edges.push({ from: n1.id, to: n2.id, len: l }); edges.push({ from: n2.id, to: n1.id, len: l }); } }); // 邻接表 const adj Array.from({ length: nid }, () []); edges.forEach(e adj[e.from].push({ to: e.to, len: e.len })); const endNode getNode(endPt); // 对每个起点执行 Dijkstra 找最短路径 for (const sp of sPts) { const startNode getNode(sp.pt); const dist new Array(nid).fill(9999999); const prev new Array(nid).fill(null); const heap [[0, startNode.id]]; dist[startNode.id] 0; while (heap.length) { heap.sort((a, b) a[0] - b[0]); const [d, u] heap.shift(); if (u endNode.id) break; if (d dist[u]) continue; adj[u].forEach(v { if (dist[v.to] d v.len) { dist[v.to] d v.len; prev[v.to] u; heap.push([dist[v.to], v.to]); } }); } // 不可达则跳过 if (dist[endNode.id] 9999999) continue; // 不是更优路径则跳过 if (dist[endNode.id] bestDist) continue; // 回溯生成路径 const path []; let cur endNode.id; while (cur ! null) { const node [...nodeMap.values()].find(n n.id cur); if (node) path.unshift(node.pt); cur prev[cur]; } // 更新最优路径 bestDist dist[endNode.id]; bestPath path; } // 找到可达路径就退出 if (bestPath.length 0) { break; } } // 返回扁平坐标数组 return pointsToFlat(bestPath); } catch (e) { console.error(路径计算出错, e); return []; } }