You need to enable JavaScript to run this app. 无向图环境下求解多边形两点间非最短最内侧连通路径的方法咨询
优惠活动
大模型
产品
解决方案
定价
更多

无向图环境下求解多边形两点间非最短最内侧连通路径的方法咨询

最内侧连通路径实现方案

该需求的核心是已知平面坐标的简单平面图(墙体无交叉)的面边界路径搜索,和最短路径逻辑完全无关,目标是让路径始终沿指定“房间”的边界行进,避免穿越内部区域。
你之前尝试的绝对最小角度策略的核心问题,是基于全局坐标系计算角度,没有和上一个行进方向绑定,无法保证遍历过程始终沿同一个面的边界走。

核心原理

采用平面图标准的固定相对转向遍历规则,所有转向都是局部计算,不需要全局判断顺逆时针方向,完全适配墙体场景:

  • 预处理所有顶点的邻接边,按围绕顶点的逆时针顺序排序
  • 从起点出发,每到一个新节点,按照固定的相对转向(顺时针/逆时针)选择下一条边,保证行进过程始终沿同一个面的边界延伸

实现步骤

前提

墙体绘制场景天然满足要求:

  • 所有顶点有明确的平面(x,y)坐标
  • 边为直线段,无交叉
  • 预处理时先移除需要排除的虚线边

预处理

  1. 遍历所有有效边(排除虚线边),为每个顶点构建初始邻接列表
  2. 对每个顶点的邻接点按逆时针顺序排序,用叉积比较代替极角计算,避免浮点误差:
    对顶点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的远近排序即可
  3. 为每个邻接点建立列表位置索引,方便后续快速查找

路径遍历

从起点出发,每一步的下一条边选择逻辑为:

  • 若上一步是从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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.30 14:15:07