计 算 几 何 课 程 实 验 总 结 报 告 CHazelle [2] 中 的 算 法 其 中 将 平 面 内 的 点 和 直 线 按 一 定 关 系 转 化 为 相 应 的 直 线 和 点, 这 样 就 将 原 先 的 极 角 ( q 与 P 顶 点 所 在 直 线 的 斜 率 ) 转 化 为

计 算 几 何 课 程 实 验 总 结 报 告 基 于 可 见 多 边 形 生 成 算 法 的 PlanarSight 游 戏 罗 必 成, 温 佺, 陈 翔 清 华 大 学 软 件 学 院 1. 实 验 目 的 我 们 组 选 择 的 课 程 实 验 选 题 是 基 于 可 见 多 边 形 生 成 算 法 的 PlanarSight 游 戏 PlanarSight 是 这 样 一 款 小 游 戏, 用 户 可 以 在 窗 口 当 中 随 意 地 绘 制 出 一 个 带 障 碍 物 的 多 边 形 房 间, 并 且 在 多 边 形 房 间 当 中 布 置 一 系 列 的 随 意 走 动 的 Monster 然 后 游 戏 一 开 始, 这 些 Monster 就 开 始 在 房 间 当 中 巡 视, 他 们 有 着 相 应 的 朝 向 和 视 角 大 小 然 后 玩 家 要 用 鼠 标 移 动 控 制 游 戏 的 主 角 Player, 在 不 被 Monster 发 现 ( 也 就 是 不 在 Monster 的 可 视 多 边 形 范 围 内 ) 的 情 况 下 逃 离 这 个 房 间 这 个 游 戏 的 实 现 背 后 所 需 要 的 理 论 基 础 就 是 对 平 面 含 洞 多 边 形 中 的 某 个 点 求 其 可 见 多 边 形, 再 判 断 某 个 点 是 不 是 在 这 个 可 见 多 边 形 内 与 游 戏 联 系 起 来, 还 会 有 动 态 更 新, 计 算 的 需 求 通 过 这 个 项 目 的 研 发, 我 们 希 望 可 以 更 好 地 对 可 见 性 问 题 产 生 深 入 的 理 解 我 们 也 希 望 通 过 这 个 小 游 戏, 从 寓 教 于 乐 的 角 度 出 发, 让 大 家 对 计 算 几 何 问 题 的 研 究 产 生 兴 趣 2. 实 验 原 理 如 上 文 所 述, 我 们 需 要 解 决 的 最 基 本 的 问 题 是 对 于 一 个 平 面 含 洞 多 边 形 P 和 其 中 的 一 点 q, 求 q 关 于 P 的 可 见 多 边 形 我 们 计 划 采 用 的 算 法 是 Asano [1], 算 法 需 要 O(n 2 ) 的 时 间 和 空 间 进 行 预 处 理 ( n 指 的 是 平 面 含 洞 多 边 形 的 边 数 ), 但 仅 需 线 性 时 间 计 算 可 见 多 边 形 下 面 将 介 绍 算 法 的 主 要 三 个 步 骤, 计 算 直 线 排 布, 计 算 三 角 剖 分 以 及 线 性 集 合 算 法 计 算 直 线 排 布 由 于 在 后 面 的 算 法 中 需 要 计 算 多 边 形 P 所 有 顶 点 关 于 q 的 极 角 序, 并 且 一 般 的 排 序 算 法 在 O(nlogn) 时 间 内 完 成 无 法 满 足 线 性 时 间 的 条 件, 因 此 在 这 里 其 参 考 了 1

计 算 几 何 课 程 实 验 总 结 报 告 CHazelle [2] 中 的 算 法 其 中 将 平 面 内 的 点 和 直 线 按 一 定 关 系 转 化 为 相 应 的 直 线 和 点, 这 样 就 将 原 先 的 极 角 ( q 与 P 顶 点 所 在 直 线 的 斜 率 ) 转 化 为 变 换 后 直 线 间 交 点 的 横 坐 标 接 着 需 要 计 算 一 组 直 线 排 布, 如 下 图 所 示, 其 中 的 直 线 由 原 先 多 边 形 P 的 顶 点 转 化 而 来, 我 们 可 以 在 O(n 2 ) 的 时 间 内 计 算 它 们 的 交 点 以 及 将 其 表 示 为 DCEL 的 形 式 当 加 入 一 条 新 的 直 线 L( 由 q 转 化 ) 时, 我 们 可 以 根 据 DECL 表 示 中 边 之 间 的 关 系 在 线 性 时 间 内 得 到 L 与 所 有 直 线 交 点 横 坐 标 的 有 序 关 系, 从 而 得 到 了 多 边 形 P 所 有 顶 点 关 于 q 的 极 角 序 DCEL 是 存 储 平 面 图 信 息 的 一 种 数 据 结 构, 实 验 中 对 DCEL 的 操 作 中, 有 两 个 重 要 的 基 本 操 作, 一 个 是 在 边 上 增 加 一 个 顶 点, 即 边 的 分 割 : DCEL 与 对 偶 图 Doubly Connect Edge List (DCEL) 是 平 面 图 的 一 种 存 储 结 构, 对 偶 图 Arrangement 描 述 了 平 面 内 点 和 线 的 对 应 关 系 实 验 中 将 建 立 平 面 内 的 点 线 与 对 偶 图 中 的 线 点 之 间 的 联 系, 并 通 过 DCEL 的 数 据 存 储 形 式 来 实 现 快 速 查 询 其 他 点 对 于 一 个 点 的 极 角 序 的 算 法, 时 间 复 杂 度 为 O(n)(n 为 点 的 数 量 ) 首 先 使 用 对 偶 图 的 办 法 将 点 转 换 成 直 线 在 平 面 内, 可 以 将 一 个 点 P 1(x 1, y 1) 转 化 为 对 偶 图 中 的 直 线 x 1*X+Yy 1 = 0, 将 另 一 个 点 P 2(x 2, y 2) 转 化 为 对 偶 图 中 的 直 线 x 2*X+Y-y 2 = 0, 联 立 两 个 方 程, 解 得 交 点 坐 标 P(x 0, y 0) 中 x 0 = (y 2-y 1)/(x 2-x 1), 即 为 平 面 内 两 个 点 的 斜 率 ( 如 果 斜 率 不 是 无 穷 的 话 ) 于 是, 平 面 内 点 与 点 之 间 的 斜 率 关 系 就 转 化 为 对 偶 图 中 线 与 线 交 点 横 坐 标 的 关 系 当 我 们 根 据 当 前 点 转 化 成 的 对 偶 图 中 的 直 线, 从 左 向 右 依 次 遍 历 整 个 对 偶 图 时, 根 据 与 当 前 直 线 的 交 点 的 横 坐 标, 即 可 得 到 一 组 点 关 于 一 个 点 的 有 序 的 极 角 序 而 整 个 从 左 向 右 遍 历 的 过 程, 则 基 于 DCEL 这 一 平 面 图 存 储 结 构, 根 据 Zone Theorem, 一 条 直 线 在 对 偶 图 中 穿 过 的 直 线 数 量 为 O(m),(m 为 直 线 的 数 量 ), 保 证 了 构 造 和 查 询 的 效 率 另 一 个 是 链 接 两 个 顶 点, 即 面 的 分 割 : 两 个 重 要 的 对 外 接 口 操 作 是 在 平 面 图 中 插 入 一 条 直 线, 以 及 按 照 从 左 向 右 查 询 一 条 直 线 穿 过 的 所 有 的 直 线 查 询 操 作 与 (1) 中 相 关 联, 如 下 图 所 示 : 由 于 实 验 中 DCEL 存 储 的 是 对 偶 图 中 的 直 线, 而 直 线 是 无 边 界 的, 故 而 需 要 特 殊 处 理 一 下 DCEL 的 存 储 结 构, 如 图 : 2

计 算 几 何 课 程 实 验 总 结 报 告 逻 辑 上 的 DCEL 的 形 式 应 当 为 (b) 图 中 的 形 式, 而 在 程 序 运 算 过 程 中, 为 了 更 简 单 快 捷 地 计 算, 会 在 所 有 直 线 的 外 围 假 想 一 个 非 常 巨 大 的 包 围 盒, 包 含 所 有 直 线 的 交 点 在 预 处 理 阶 段, 根 据 输 入 的 地 图 信 息, 得 到 所 有 点, 将 所 有 点 转 化 为 对 偶 图 中 的 直 线, 通 过 DCEL 建 立 起 平 面 图 结 构 插 入 和 查 询 操 作 类 似, 过 程 DCEL 结 构 中, 点 线 面 都 是 O(n 2 ) 的 空 间 复 杂 度, 时 间 复 杂 度 也 是 O(n 2 ) 1000 个 点 的 测 试 输 入, 在 DCEL 存 储 结 构 中 会 有 近 50 万 个 点,200 万 条 边, 还 有 50 万 个 面 当 点 数 达 到 5000 时,DCEL 存 储 结 构 中 会 有 近 1000 万 个 点,4000 万 条 边, 还 有 1000 万 个 面 而 在 DCEL 中, 每 一 个 点, 边, 面 都 是 一 个 存 储 结 构, 还 会 存 有 其 他 的 信 息, 对 内 存 空 间 要 求 很 高 实 时 运 行 阶 段, 根 据 当 前 需 要 查 询 点 转 化 为 对 偶 图 中 的 直 线, 到 DCEL 结 构 中 按 照 横 坐 标 序 列 从 左 到 右 查 询 所 有 直 线, 得 到 所 有 点 关 于 当 前 点 的 斜 率 的 关 系 再 根 据 获 得 的 斜 率 关 系 以 及 点 与 当 前 要 查 询 点 之 间 的 坐 标 关 系 来 划 分 点 的 极 角 序 为 [0, π) 还 是 [π, 2π) 从 而, 将 一 个 斜 率 有 序 的 数 组 转 化 为 两 个 极 角 有 序 的 数 组, 分 裂 后, 再 按 照 极 角 序, 重 新 排 列 起 来 有 些 情 况 需 要 特 殊 处 理, 如 在 对 偶 图 中 两 条 直 线 平 行 的 情 况, 对 应 于 在 原 二 维 平 面 内, 两 个 点 所 在 直 线 平 行 于 Y 轴 的 情 况 此 种 情 况 下, 对 于 这 些 点 的 斜 率 的 判 断 不 会 在 DCEL 求 解 过 程 中, 而 需 要 在 外 部 单 独 计 算, 好 在 垂 直 情 况 下, 极 角 序 只 有 0 和 π 两 种, 根 据 计 算 的 结 果 直 接 剥 离 开 即 可 还 有 就 是 X 坐 标 相 同 时, 按 照 Y 坐 标 从 小 到 大 的 方 向 去 查 询 我 们 可 以 就 直 线 排 布 的 算 法 进 行 相 关 的 算 法 分 析 首 先 分 析 一 下 预 处 理 阶 段 需 要 的 时 间 和 空 间 复 杂 度, 如 下 图 : 预 处 理 阶 段, 相 对 比 较 耗 时 间, 考 虑 到 平 台 是 C++, 大 量 的 new 操 作 会 极 大 地 降 低 预 处 理 时 间, 我 们 采 用 了 先 批 量 new 后 再 根 据 标 号 取 用 申 请 空 间 的 方 式 来 适 当 提 高 运 行 时 速 度 运 行 时, 考 虑 到 此 种 算 法 空 间 复 杂 度 需 要 O(n 2 ), 有 大 量 的 信 息 常 驻 内 存, 时 间 复 杂 度 为 O(n), 但 是 常 数 操 作 比 较 多 而 如 果 采 用 简 单 暴 力 的 排 序 算 法, 在 计 算 极 角 序 的 时 候 直 接 调 用 C++ 的 std::sort 的 话, 兴 许 会 有 不 一 样 的 效 果, 因 为 sort 的 时 间 复 杂 度, 虽 然 近 似 为 O(nlogn), 但 是 排 序 的 结 构 非 常 简 单, 常 数 也 十 分 地 小, 而 空 间 复 杂 度, 则 相 比 于 DCEL 的 存 储, 也 大 大 的 降 低, 并 且, 很 多 信 息 并 不 需 要 常 驻 内 存 于 是, 在 程 序 中, 我 们 同 时 实 现 了 使 用 std::sort 进 行 的 极 角 排 序 和 采 用 对 偶 DCEL 来 实 现 的 极 角 排 序 实 验 通 过 手 绘 小 数 据, 图 像 处 理 提 取 图 片 边 缘 转 化 为 输 入 点 的 方 式, 对 运 行 时 程 序 进 行 sort 和 DCEL 方 法 的 运 行 时 效 率 比 较 结 果 发 现, 在 很 小 规 模 的 数 据 下 (30 点 以 内 )DCEL 会 稍 微 比 sort 快 一 点, 而 到 了 几 百 几 千 的 数 据,DCEL 与 sort 的 速 度 不 相 上 下, 运 行 时 间 很 小 三 角 剖 分 在 计 算 平 面 上 可 见 多 边 形 的 整 个 算 法 流 程 当 中, 三 角 剖 分 起 到 了 一 个 非 常 重 要 的 地 位 它 为 最 终 线 性 集 合 算 法 生 成 可 见 多 边 形 提 供 了 重 要 的 边 的 拓 扑 排 序 信 3

计 算 几 何 课 程 实 验 总 结 报 告 息 为 了 实 现 线 上 时 间 复 杂 度 为 O(n) 的 平 面 上 可 见 多 边 形 的 生 成 算 法, 三 角 剖 分 部 分 的 算 法 被 分 成 了 预 处 理 阶 段 (Pre-process Phase) 和 执 行 阶 段 (Process Phase) 其 中 预 处 理 阶 段 使 用 时 间 复 杂 度 为 O(nlogn) 的 受 约 束 Delaunay 三 角 剖 分 生 成 算 法, 而 处 理 阶 段 使 用 时 间 复 杂 度 为 O(n) 的 三 角 网 格 更 新 算 法 预 处 理 阶 段 : 预 处 理 阶 段 的 受 约 束 Delaunay 算 法 需 要 完 成 的 事 情 就 是 在 O(nlogn) 的 时 间 复 杂 度 之 内, 对 平 面 上 的 多 边 形 进 行 三 角 剖 分, 要 求 最 终 生 成 的 三 角 剖 分 包 含 所 有 多 边 形 上 的 每 一 条 边, 并 且 最 终 生 成 的 三 角 剖 分 形 成 一 个 原 有 多 边 形 的 凸 包 ( 之 所 以 需 要 生 成 凸 包 是 为 了 方 便 后 面 执 行 阶 段 的 时 候 向 上 方 射 出 一 条 射 线 更 新 三 角 剖 分 时 的 操 作 ) 在 程 序 的 实 现 当 中, 这 一 块 使 用 了 开 源 的 多 边 形 受 约 束 Delaunay 三 角 剖 分 库 poly2tri 来 完 成 poly2tri 的 算 法 思 路 来 源 于 V. Domiter 和 B. Zalik 在 2008 年 3 月 19 日 在 IJGIS 上 发 表 的 论 文 [4] 这 是 一 种 基 于 扫 描 线 的 三 角 剖 分 算 法, 具 体 的 算 法 如 下 所 示 : 初 始 化 : 将 所 有 点 按 Y 坐 标 升 序 排 列, 如 果 Y 坐 标 相 同, 则 按 X 坐 标 升 序 排 列 插 入 两 个 人 工 点 P -1,P -2, 使 得 他 们 位 于 所 有 点 的 下 方, 并 且 对 于 X 坐 标 来 说,P -1 位 于 所 有 点 的 左 侧,P -2 位 于 所 有 点 的 右 侧 这 样 我 们 就 得 到 了 构 造 的 第 一 个 三 角 形,P 0P -1P -2 该 三 角 形 包 含 两 条 前 沿 边 (Advancing Front),P -1P 0 和 P 0P -2 在 最 后 一 步 最 终 确 定 的 时 候, 所 有 与 人 工 点 相 连 的 三 角 形 将 会 被 删 去 这 一 步 结 束 后, 示 意 图 如 下 所 示 : 1. 某 个 顶 点 是 孤 立 的 点, 或 者 是 一 个 下 边 缘 点 时, 顶 点 事 件 (Point Event) 被 触 发 设 该 点 为 P i, 该 点 到 前 沿 边 线 段 上 的 竖 直 方 向 投 影 记 为 P Q, 前 沿 边 线 段 的 左 右 断 点 记 录 为 P L,P R,P L 在 前 沿 边 上 的 左 边 的 临 近 线 段 断 点 P S 此 时 包 含 两 种 情 况 : 1.1 点 P Q 在 PLPR 线 段 上, 并 不 与 端 点 重 合 此 时 新 的 三 角 形 P RP ip L 将 会 被 构 造 出 来, 新 的 前 沿 边 将 会 被 更 新 为 P LP i 和 P ip R 如 下 图 所 示 : 1.2 点 PQ 与 PL 端 点 发 生 重 合 此 时 将 构 成 两 个 新 三 角 形,P LP ip S 和 P LP RP i 如 图 所 示 : 将 前 沿 边 上 其 他 的 对 于 P i 来 说 可 见 的 点 与 P i 相 连 以 构 成 新 的 三 角 形 在 构 成 新 的 三 角 形 的 时 候, 需 要 进 行 必 要 的 角 度 检 查 : i) 新 的 三 角 形 的 边 与 前 沿 边 线 段 之 间 的 夹 角 必 须 小 于 90 度, 否 则 创 建 三 角 形 行 为 将 停 止 如 图 所 示 : 扫 描 : 对 各 个 点 按 Y 轴 正 方 向 进 行 扫 描, 扫 描 时 分 为 这 两 种 情 况 : 4

计 算 几 何 课 程 实 验 总 结 报 告 ii) 前 沿 边 上 线 段 之 间 的 夹 角 如 果 大 于 135 度, 说 明 存 在 盆 状 结 构 (Basins) 该 盆 状 结 构 需 要 被 更 多 新 的 三 角 形 填 充 如 下 图 所 示 : 2. 某 个 顶 点 是 一 个 上 边 缘 点 时, 边 事 件 (Edge Event) 被 触 发 当 扫 描 遇 到 一 个 Y 坐 标 较 大 的 上 边 缘 点 时, 一 条 受 约 束 边 e(constrained Edge) 必 须 被 插 入 到 三 角 剖 分 的 结 果 当 中 在 插 入 这 条 边 的 时 候, 将 会 遇 到 该 条 边 与 目 前 结 果 当 中 的 三 角 形 相 交 的 问 题 对 于 这 种 情 况, 该 算 法 使 用 这 样 的 三 个 步 骤 进 行 处 理 : 2.1 确 定 第 一 个 与 e 相 交 的 三 角 形, 并 按 照 特 定 的 遍 历 方 案, 将 该 条 边 e 所 串 联 的 所 有 三 角 形 标 记 为 需 要 删 除 2.2 删 除 所 有 被 e 相 交 的 串 联 三 角 形 最 复 杂 的 是 第 三 种 情 况,e 与 前 沿 边 有 一 个 或 多 个 交 点 时 此 时 需 要 将 遍 历 方 法 进 行 一 些 转 换 当 前 沿 边 线 段 上 的 点 在 e 的 上 方 时, 遍 历 方 案 将 依 据 被 串 联 的 相 交 三 角 形 进 行 遍 历 ; 当 前 沿 边 线 段 上 的 点 在 e 的 下 方 时, 遍 历 方 案 将 依 据 前 沿 边 线 段 上 的 顶 点 进 行 遍 历 当 所 有 顶 点 和 约 束 边 都 被 扫 描 后, 进 入 最 终 确 定 环 节 : 删 除 所 有 的 与 人 工 点 相 连 的 三 角 形, 添 加 构 成 模 型 凸 包 的 边 框 三 角 形 到 最 终 的 结 果 当 中 这 样 便 完 成 了 约 束 Delaunay 三 角 化 的 扫 描 线 算 法 如 下 图 所 示 : 2.3 将 被 删 除 的 空 白 区 域 重 新 进 行 三 角 剖 分 执 行 阶 段 : 这 里 将 会 面 临 三 种 情 况 第 一 种 情 况 就 是 e 在 前 沿 边 线 段 的 下 方, 这 种 情 况 照 上 述 处 理 办 法 进 行 处 理 即 可 第 二 种 情 况 是 e 在 前 沿 线 段 的 上 方 这 是 最 简 单 的 处 理 情 况 由 于 没 有 任 何 相 交 的 三 角 形, 故 不 需 要 进 行 第 一 步 遍 历 所 有 串 联 的 三 角 形 并 标 记 删 除 的 任 务, 只 需 要 将 e 与 上 沿 边 构 成 的 空 白 区 域 进 行 三 角 剖 分 即 可 如 下 图 所 示 : 预 处 理 阶 段 结 束 以 后, 我 们 得 到 了 一 个 多 边 形 所 在 凸 包 的 受 约 束 Delaunay 三 角 剖 分 前 面 提 到 过, 之 所 以 使 用 多 边 形 所 在 的 凸 包 进 行 三 角 剖 分 的 预 处 理, 是 为 了 执 行 阶 段 的 时 候 射 出 一 条 射 线 对 三 角 网 格 进 行 更 新 更 加 方 便 在 介 绍 执 行 阶 段 的 三 角 网 格 更 新 之 前, 先 对 发 射 一 条 射 线 切 分 三 角 网 格 的 目 的 加 以 解 释 执 行 期 间 的 三 角 剖 分 更 新 是 为 了 给 最 后 的 线 性 集 合 算 法 提 供 多 边 形 线 段 的 拓 扑 顺 序 而 线 性 集 合 算 法 需 要 一 个 角 度 范 围 作 为 横 坐 标 的 输 入, 所 以 我 们 要 把 连 续 的 360 度 空 间 给 划 分 成 一 段 从 0 度 到 360 度 的 空 间, 为 此, 我 们 就 需 要 射 出 一 条 直 线 作 为 0 度 和 360 度 的 划 分 线, 并 且 把 这 条 直 线 相 交 的 所 有 线 段 分 成 两 段 如 下 图 所 示 : 5

计 算 几 何 课 程 实 验 总 结 报 告 三 角 剖 分 更 新 的 过 程 比 较 简 单 首 先 查 找 到 当 前 点 P 所 在 的 三 角 形, 设 为 ABC, 而 P 向 上 垂 直 发 射 一 条 射 线, 交 三 角 形 ABC 的 AB 边 上, 交 点 设 为 P 这 个 时 候, 把 三 角 形 分 为 四 个 三 角 形, 分 别 为 APC,PBC, AP P 和 P BP 如 下 图 所 示 : 需 要 注 意 的 是, 当 这 条 射 线 射 到 某 个 顶 点 上 时, 需 要 跳 过 很 多 个 三 角 形 知 道 射 线 射 到 最 上 的 三 角 形 的 边 界 上, 这 种 退 化 的 情 况 如 下 图 所 示 : 如 果 出 现 了 P 与 A 重 合 的 情 况, 则 三 角 形 AP P 退 化 为 一 条 边 ; 如 果 出 现 了 P 落 在 边 BC 上 的 情 况, 则 三 角 形 PBC 退 化 成 两 条 边, 并 且 切 分 另 一 个 与 三 角 形 ABC 共 边 BC 的 三 角 形 如 下 图 所 示 : 该 循 环 将 一 直 进 行 到 射 线 射 到 一 条 不 与 任 何 三 角 形 公 共 的 边 上 后 终 止 所 以 对 于 多 边 形 可 能 存 在 凹 陷 (Reflex) 的 情 况, 所 以 初 始 三 角 剖 分 要 对 该 多 边 形 的 凸 包 进 行, 从 而 保 证 射 线 射 到 多 边 形 的 边 界 的 时 候, 循 环 就 可 以 终 止 执 行 阶 段 更 新 完 了 所 有 的 三 角 形 以 后, 将 每 一 个 三 角 形 的 每 条 边 作 为 节 点, 建 立 一 个 图 的 偏 序 关 系 建 立 偏 序 关 系 的 方 法 如 下 图 所 示, 首 先 每 个 三 角 网 格 当 中 的 三 角 形 都 可 以 将 空 间 划 分 成 几 个 部 分, 如 图 中 的 R 1,R 2,R 3,R 1,R 2,R 3,l 13,l 31,l 12,l 21,l 23,l 32 等 接 下 来 只 要 循 环 处 理, 将 P 替 换 成 P, 将 三 角 形 ABC 替 换 成 三 角 形 ABC 共 边 AB 的 三 角 形, 然 后 继 续 按 照 上 面 的 对 三 角 形 进 行 细 分 的 方 式 对 下 一 个 三 角 形 继 续 进 行 细 分 如 下 图 所 示 : 6

计 算 几 何 课 程 实 验 总 结 报 告 如 果 此 时 待 求 可 见 多 边 形 的 点 位 于 R 1 的 内 部, 那 么 就 认 为 e 2>e 1,,e 3>e 1,R 2,R 3 的 情 况 类 似 ; 如 果 此 时 待 求 可 见 多 边 形 的 点 位 于 R 1 的 内 部, 那 么 就 认 为 e 2<e 1,,e 3<e 1,R 2,R 3 的 情 况 类 似 ; 如 果 此 时 点 位 于 l 12 上, 那 么 就 认 为 e 2>e 3 根 据 这 种 偏 序 关 系 建 立 一 个 有 向 无 环 图, 最 后 对 该 图 进 行 拓 扑 排 序, 得 到 最 后 的 结 果 就 是 多 边 形 所 有 边 的 拓 扑 顺 序, 为 下 一 步 的 线 性 集 合 算 法 提 供 Y 坐 标 上 的 排 列 信 息 线 性 集 合 并 计 算 可 视 多 边 形 计 算 可 见 多 边 形 的 算 法 利 用 了 之 前 计 算 出 的 顶 点 极 角 序 和 边 的 偏 序 关 系, 其 将 多 边 形 顶 点 的 极 角 序 转 化 为 x 坐 标 ( 如 下 左 图 中 P 11 和 P 12 两 点 均 在 竖 直 的 射 线 上, 其 x 坐 标 均 为 0; 之 后 顶 点 的 极 角 顺 序 为 P 6 P 9 P 3 P 2 依 次 向 后, 因 此 其 x 坐 标 分 别 为 1 2 3 4 等 等 ), 并 将 多 边 形 中 的 边 关 于 输 入 点 的 偏 序 关 系 转 化 为 排 序 的 序 号 值 并 进 一 步 转 化 为 y 坐 标 (P 7P 8=1 P 1P 11=2 P 5P 12=3 以 此 类 推 ), 从 而 将 原 先 如 下 左 图 中 的 求 可 见 多 边 形 问 题 转 化 为 了 右 图 中 对 于 每 个 x 坐 标 求 其 对 应 的 y 值 最 小 的 线 段 这 种 转 化 保 证 了 原 先 图 形 中 线 段 的 遮 挡 关 系, 即 每 个 区 间 对 应 的 最 低 的 线 段 一 定 是 原 图 中 输 入 点 可 见 的 线 段 其 本 质 为 自 底 向 上 遍 历 每 一 条 线 段, 为 每 一 个 x 值 标 记 其 所 对 应 的 最 低 的 线 段 的 y 值, 并 记 录 在 vis 数 组 中, 最 后 将 这 些 线 段 依 次 连 在 一 起 便 得 到 了 可 见 多 边 形 算 法 中 涉 及 两 个 函 数,find 函 数 返 回 包 含 x 的 集 合 中 的 最 大 元 素,link 函 数 将 包 含 x 与 包 含 x+1 的 集 合 合 并 起 来 对 于 上 面 的 例 子, 算 法 如 下 执 行 操 作 : 首 先 遍 历 到 y 值 为 1 和 2 的 线 段, 即 P 7P 8 和 P 1P 11, 根 据 后 边 的 link 操 作 相 应 的 x 值 6 7 和 10 11 会 分 别 组 成 集 合, 同 时 vis[6]=1,vis[10]=2; 下 一 个 循 环 中 遍 历 到 y 值 为 3 的 线 段 P 5P 12, 此 时 8 和 9 会 先 组 成 集 合, 同 时 vis[8] 和 vis[9] 会 记 为 3, 之 后 在 while 循 环 中 x=9 时 link(9) 操 作 会 将 集 合 {8, 9} 与 集 合 {10, 11} 合 并 起 来, 再 执 行 find 时 返 回 11 会 达 到 线 段 的 右 边 界, 循 环 也 就 终 止 了, 这 样 vis[10] 便 保 留 了 之 前 的 值, 即 已 组 成 集 合 (vis 已 被 标 记 ) 的 x 值 不 会 再 次 被 访 问, 也 就 保 证 最 后 求 出 正 确 的 线 段 y 值 上 边 的 算 法 可 以 求 出 一 个 点 关 于 多 边 形 的 整 个 可 见 区 域, 而 我 们 的 程 序 中 需 要 求 出 某 一 视 角 内 的 可 见 多 边 形 因 此 我 们 根 据 视 角 的 左 右 边 界 计 算 出 其 所 在 的 x 区 间, 通 过 输 入 点 和 两 个 边 界 求 出 其 与 所 在 x 区 间 对 应 的 最 小 y 值 线 段 的 两 个 交 点, 之 后 按 vis 数 组 中 的 值 依 次 连 接 相 应 线 段 便 可 得 到 一 定 视 角 范 围 内 的 可 见 多 边 形, 这 个 过 程 同 样 可 在 线 性 时 间 内 完 成 3. 总 结 进 行 转 化 后 可 以 使 用 Gabow [3] 中 的 线 性 集 合 并 算 法 计 算, 在 线 性 时 间 内 得 出 点 q 的 可 见 多 边 形 算 法 的 伪 代 码 如 下 所 示 : 平 面 上 可 见 多 边 形 的 生 成 算 法 当 中 包 含 了 受 约 束 Delaunay 三 角 剖 分, 二 维 凸 包, 对 偶 图,DCEL 数 据 结 构, 线 性 集 合 算 法, 拓 扑 排 序 等 等 经 典 算 法 在 完 成 PlanarSight 这 个 游 戏 的 过 程 当 中, 着 实 地 考 验 了 一 把 我 们 的 编 程 实 际 开 发 能 力 通 过 这 个 课 程 实 验, 我 们 不 仅 对 计 算 几 何 的 相 关 算 法 认 识 地 更 加 深 入, 同 时 结 合 理 论 的 实 践 开 发 能 力 也 得 到 了 有 效 的 提 高 在 完 成 这 个 课 题 实 验 之 后, 我 们 将 会 继 续 就 平 面 上 可 见 多 边 形 这 一 课 题 进 行 进 一 步 的 拓 展 研 究, 争 取 获 得 更 大 的 成 果 7

计 算 几 何 课 程 实 验 总 结 报 告 参 考 文 献 [1] Asano T, Asano T, Guibas L, et al. Visibility of disjoint polygons[j]. Algorithmica, 1986, 1(1-4): 49-63. [2] Chazelle B, Guibas L J, Lee D T. The power of geometric duality[j]. BIT Numerical Mathematics, 1985, 25(1): 76-90. [3] Gabow H N, Tarjan R E. A linear-time algorithm for a special case of disjoint set union[c]//proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983: 246-251. [4] Domiter V, Žalik B. Sweep line algorithm for constrained Delaunay triangulation[j]. International Journal of Geographical Information Science, 2008, 22(4): 449-462. 8

1 PlanarSight 用 户 手 册 1. 在 Visual Studio 中 运 行 项 目 或 直 接 运 行 可 执 行 文 件, 可 打 开 如 下 的 程 序 主 界 面 : 单 击 Import Map 按 钮 可 导 入 地 图, 单 击 Export Map 可 导 出 地 图 ( 如 上 图 当 中 红 色 圈 中 部 分 ) 2. 在 绘 制 的 部 分, 首 先 单 击 Outer Walls 可 绘 制 地 图 外 环, 依 次 用 鼠 标 左 键 单 击 绘 制 区 域 形 成 点, 最 后 单 击 鼠 标 右 键 结 束 单 击 Inner Walls 可 绘 制 地 图 内 环, 绘 制 方 法 与 外 环 相 同, 但 内 环 需 在 外 环 之 内

2 PlanarSight 用 户 手 册 3. 单 击 monsters 可 在 地 图 中 添 加 怪 物 ( 如 下 图 红 色 圈 中 部 分 ), 可 用 鼠 标 左 键 单 击 绘 图 区 的 多 边 形 内 绘 制, 最 后 单 击 鼠 标 右 键 结 束 单 击 Clear 可 以 清 空 整 个 绘 图 区 4. 单 击 Start 后 游 戏 开 始, 怪 物 会 在 迷 宫 中 随 机 行 走, 玩 家 则 会 随 机 生 成 在 迷 宫 中 的 某 个 位 置, 可 用 鼠 标 单 击 表 示 玩 家 的 圆 点 拖 动 玩 家 行 走 躲 避 怪 物 的 追 击 选 中 Visibility Polygon 可 显 示 玩 家 和 怪 物 的 可 视 范 围 ( 如 下 图 红 色 圈 中 部 分 ), 同 时 玩 家 只 能 看 到

3 PlanarSight 用 户 手 册 可 视 范 围 内 以 及 距 离 自 身 一 定 距 离 之 内 的 怪 物, 怪 物 则 会 加 速 追 击 出 现 在 其 视 野 内 的 玩 家 5. 若 玩 家 被 怪 物 发 现 且 怪 物 接 近 玩 家 到 一 定 距 离 之 内, 则 游 戏 结 束 6. 下 面 介 绍 工 具 栏 中 的 一 些 其 他 功 能 选 中 Triangulation, 绘 图 区 将 显 示 三 角 剖 分 的 中 间 结 果 在 此 基 础 上 再 选 中 Mesh Edge Labels, 绘 图 区 将 显 示 三 角 剖 分 中 不 在 多 边 形 中 的 边 的 标 号 如 下 图 红 色 方 框 圈 住 部 分 :

4 PlanarSight 用 户 手 册 7. 选 中 Sorted Segments( 如 下 图 红 色 方 框 圈 住 部 分 ), 绘 图 区 将 显 示 多 边 形 中 线 段 偏 序 关 系 的 排 序 结 果, 距 离 输 入 点 越 近 的 边 越 亮, 反 之 越 暗 8. 选 中 Dual Graph, 绘 图 区 将 显 示 在 使 用 DCEL 求 极 角 序 的 算 法 中 DCEL 中 使 用 的 对 偶 图 选 中 Linear Set, 绘 图 区 将 显 示 线 性 集 合 并 算 法 中 对 顶 点 极 角 序 和 线 段 偏 序 关 系 进 行 转 化 的 结 果 图 如 下 图 红 色 方 框 圈 住 部 分 :

5 PlanarSight 用 户 手 册 9. 在 std::sort 和 DCEL 间 切 换 可 以 选 择 使 用 不 同 的 算 法 计 算 顶 点 极 角 排 序 结 果 ( 如 下 图 红 色 方 框 圈 住 部 分 ) 选 中 3D View 则 可 观 看 地 图 的 三 维 效 果 ( 如 下 图 红 色 圆 圈 圈 住 部 分 ) 10. 最 后 是 一 些 复 杂 地 图 的 运 行 效 果, 例 如 复 杂 的 字 符 形 状 的 内 环 下 的 可 见 多 边 形 效 果 :

6 PlanarSight 用 户 手 册 相 应 的 3D 视 图 下 的 效 果 : 这 是 另 一 组 复 杂 字 体 形 状 的 内 环 与 不 规 则 外 环 构 成 的 多 边 形 内 部 的 可 见 多 边 形 效 果 :

7 PlanarSight 用 户 手 册 相 应 的 3D 视 图 效 果 : 这 是 清 华 大 学 主 楼 门 口 区 域 的 建 筑 物 的 地 图 作 为 内 环 而 构 建 出 来 的 一 个 测 试 用 例, 是 通 过 提 取 地 图 上 的 建 筑 物 物 体 边 界 而 生 成 的 一 个 地 图 :

8 PlanarSight 用 户 手 册 相 应 的 3D 视 图 效 果 :