无向图环境下求解多边形两点间非最短最内侧连通路径的方法咨询
最内侧连通路径实现方案
该需求的核心是已知平面坐标的简单平面图(墙体无交叉)的面边界路径搜索,和最短路径逻辑完全无关,目标是让路径始终沿指定“房间”的边界行进,避免穿越内部区域。
你之前尝试的绝对最小角度策略的核心问题,是基于全局坐标系计算角度,没有和上一个行进方向绑定,无法保证遍历过程始终沿同一个面的边界走。
核心原理
采用平面图标准的固定相对转向遍历规则,所有转向都是局部计算,不需要全局判断顺逆时针方向,完全适配墙体场景:
- 预处理所有顶点的邻接边,按围绕顶点的逆时针顺序排序
- 从起点出发,每到一个新节点,按照固定的相对转向(顺时针/逆时针)选择下一条边,保证行进过程始终沿同一个面的边界延伸
实现步骤
前提
墙体绘制场景天然满足要求:
- 所有顶点有明确的平面(x,y)坐标
- 边为直线段,无交叉
- 预处理时先移除需要排除的虚线边
预处理
- 遍历所有有效边(排除虚线边),为每个顶点构建初始邻接列表
- 对每个顶点的邻接点按逆时针顺序排序,用叉积比较代替极角计算,避免浮点误差:
对顶点u的两个邻接点v、w,计算向量uv = (v.x-u.x, v.y-u.y)、uw = (w.x-u.x, w.y-u.y)的叉积:- 叉积>0:w在uv的逆时针方向,v排在w前
- 叉积<0:w在uv的顺时针方向,w排在v前
- 叉积=0(共线):按距离u的远近排序即可
- 为每个邻接点建立列表位置索引,方便后续快速查找
路径遍历
从起点出发,每一步的下一条边选择逻辑为:
- 若上一步是从
prev走到curr,先在curr的邻接排序列表里找到prev的位置 - 选顺时针转向规则:下一个点为
prev位置的上一个元素(到列表开头则循环到末尾) - 选逆时针转向规则:下一个点为
prev位置的下一个元素(到列表末尾则循环到开头) - 持续走到终点即可得到对应转向下的面边界路径。
对应示例场景:采用顺时针转向规则遍历,会得到正确路径1-2-3-4-5-6-7;采用逆时针转向规则会得到穿内部的1-2-8-6-7,直接选择符合内侧要求的顺时针方向路径即可。
Lua伪代码参考
-- 顶点结构 Vertex = { id = 0, x = 0, y = 0, neighbors = {}, -- 排序后的邻接点列表 neighbor_index = {} -- 邻接点到列表下标的映射 } -- 邻接点比较函数(逆时针顺序) local function compare_neighbors(u, v, w) local ux, uy = u.x, u.y local vx, vy = v.x - ux, v.y - uy local wx, wy = w.x - ux, w.y - uy local cross = vx * wy - vy * wx if math.abs(cross) > 1e-6 then return cross > 0 else -- 共线时按距离排序 return (vx*vx + vy*vy) < (wx*wx + wy*wy) end end -- 预处理:排除指定边,构建排序后的邻接表 local function preprocess(vertices, edges, exclude_edge) local ea, eb = exclude_edge[1], exclude_edge[2] -- 构建邻接表,排除目标边 for _, e in ipairs(edges) do local a, b = e[1], e[2] local is_exclude = (a == ea and b == eb) or (a == eb and b == ea) if not is_exclude then table.insert(vertices[a].neighbors, vertices[b]) table.insert(vertices[b].neighbors, vertices[a]) end end -- 对每个顶点的邻接列表排序 for _, u in pairs(vertices) do table.sort(u.neighbors, function(v, w) return compare_neighbors(u, v, w) end) -- 构建位置索引 u.neighbor_index = {} for idx, v in ipairs(u.neighbors) do u.neighbor_index[v.id] = idx end end end -- 沿指定转向遍历路径 -- turn_dir: 1=逆时针转向, -1=顺时针转向 local function walk_path(start_id, end_id, turn_dir, vertices) local start_v = vertices[start_id] local end_v = vertices[end_id] -- 从起点的每个邻接点开始试方向 for _, first_next in ipairs(start_v.neighbors) do local path = {start_id, first_next.id} local prev = start_v local curr = first_next -- 最多遍历1000步避免死循环,可根据图规模调整 for step = 1, 1000 do if curr == end_v then return path end -- 查找上一个节点在当前节点邻接表的位置 local prev_idx = curr.neighbor_index[prev.id] -- 计算下一个节点的位置(Lua为1-based索引) local next_idx = (prev_idx - 1 + turn_dir) % #curr.neighbors + 1 local next_v = curr.neighbors[next_idx] table.insert(path, next_v.id) -- 更新遍历状态 prev, curr = curr, next_v -- 回到起点说明该方向走不通,换分支 if curr == start_v then break end end end return nil end
注意事项
- 转向方向无需全局判断,分别测试顺时针、逆时针两个方向,选择路径符合“不穿越房间内部”要求的即可
- 遍历的最大步数阈值可根据实际墙体规模调整,避免异常情况死循环
- 预处理阶段必须先移除需要排除的虚线边,否则会混入错误路径
内容的提问来源于stack exchange,提问作者user1092481290841204
相关产品推荐
相关产品推荐

