计算几何专题

计 算 几 何 专 题 姚 金 宇

概 述 特 点 思 考 繁 琐 编 程 繁 琐 细 节 繁 琐 如 何 把 握 需 要 在 平 时 将 计 算 几 何 的 相 关 子 问 题 透 彻 研 究 模 板 的 代 码 一 定 要 规 范 赛 场 上 重 点 想 思 路, 不 能 将 时 间 花 在 纠 缠 细 节 上 ( 否 则 finish egg )

简 单 的 解 析 几 何 元 素 点 与 直 线 点 到 直 线 距 离 ( 扩 展 : 平 行 线 间 距 离 ) 直 线 平 移 角 夹 角 : 点 积 余 弦 定 理 圆 圆 的 方 程 两 圆 位 置 关 系 ( 外 离 外 切 相 交 内 切 内 含 同 心 )

问 题 1: 线 段 相 交 二 维 平 面 内 线 段 规 范 相 交 的 判 定 两 条 线 段 恰 有 唯 一 一 个 不 是 端 点 的 公 共 点

线 段 相 交 : 解 析 几 何 方 法 列 直 线 方 程 Ax+By+C=0 解 二 元 一 次 方 程 组, 求 交 点 判 断 交 点 是 否 符 合 要 求 无 解 情 况 : 平 行 无 穷 多 解 : 共 线 唯 一 解 : 判 断 是 否 分 别 在 两 条 线 段 上

解 析 方 法 的 弊 端 浮 点 除 法 浮 点 误 差 运 算 效 率 额 外 判 断 交 点 我 们 只 需 要 得 到 是 否 相 交 的 判 断, 不 需 要 知 道 交 点

线 段 相 交 : 计 算 几 何 方 法 两 条 线 段 相 交 时, 每 条 线 段 两 个 端 点 都 在 另 一 条 线 段 的 异 侧 如 何 判 断 异 侧 有 向 线 段 判 断 一 个 点 是 在 有 向 线 段 的 左 边 还 是 右 边 添 加 一 条 辅 助 向 量 若 要 判 断 P 的 相 对 位 置, 只 要 判 断 向 量 P 1 P 在 向 量 P 1 P 2 的 顺 时 针 还 是 逆 时 针

向 量 的 叉 积 叉 积 公 式 向 量 a 到 b 逆 时 针 旋 转 时, 叉 积 >0 向 量 a 到 b 逆 时 针 旋 转 时, 叉 积 <0 共 线 时, 叉 积 =0 叉 积 的 本 质 : 有 向 面 积

叉 积 的 作 用 求 凸 多 边 形 面 积 三 角 剖 分 有 向 面 积 求 任 意 多 边 形 面 积

线 段 相 交 : 计 算 几 何 方 法 规 范 相 交 的 计 算 几 何 判 定 P 和 P 在 向 量 P 1 P 2 的 异 侧, 即 且 P 1 和 P 2 在 向 量 PP 的 异 侧, 即

非 规 范 相 交

非 规 范 相 交 ( 续 ) 它 们 没 有 被 判 断 为 规 范 相 交 是 因 为 它 们 在 叉 乘 过 程 中, 都 至 少 有 一 次 叉 乘 结 果 是 0 但 是 叉 乘 结 果 为 0 并 不 一 定 就 是 非 规 范 相 交 因 为 叉 乘 结 果 为 0 表 示 是 某 个 点 在 某 向 量 所 在 的 直 线 上 如 下 情 况 也 可 能 使 叉 乘 结 果 是 0, 尽 管 它 们 并 不 是 非 规 范 相 交 或 者 规 范 相 交

非 规 范 相 交 的 判 断 某 个 端 点 P 在 另 外 一 条 线 段 P1P2 所 在 的 直 线 上 即 P1P2 P1P=0 且 该 端 点 P 在 线 段 P 1 P 2 上 即 min(p 1.x, P 2.x) P.x max(p 1.x, P 2.x) 且 min(p 1.y, P 2.y) P.y max(p 1.y, P 2.y)

点 积 公 式 向 量 的 点 积

点 积 的 作 用 在 已 知 P 在 P 1 P 2 所 在 直 线 上 时, 判 断 点 积 的 符 号 即 可 知 道 是 否 在 线 段 P 1 P 2 上 若 PP1 PP2<0, 则 P 在 P1P2 内 部 若 PP1 PP2>0, 则 P 在 P1P2 外 部 若 PP1 PP2=0, 则 P 与 P1 或 P2 重 合

问 题 2: 点 与 多 边 形 的 位 置 关 系 位 置 关 系 讨 论 点 在 形 内 点 在 形 外 点 在 边 界 上

观 察

射 线 法 通 常 取 x 轴 正 方 向 为 射 线 方 向 奇 数 次 相 交, 则 在 形 内 偶 数 次 相 交, 则 在 形 外 有 没 有 特 殊 情 况?

射 线 法 的 特 殊 情 况

解 决 办 法 缩 点 法 随 机 法 平 移 法 不 够 优 美? 其 他 方 法 转 角 法 : 需 要 反 三 角 函 数 开 根 浮 点 除 法 的 计 算 因 此 实 际 运 算 的 速 度 慢 很 多

问 题 3: 求 凸 包 凸 多 边 形 整 个 图 形 在 任 一 条 边 的 一 侧 凸 包 对 于 一 个 平 面 点 集 或 者 一 个 多 边 形, 它 的 凸 包 指 的 是 包 含 它 的 最 小 凸 图 形 或 最 小 凸 区 域

凸 包 求 法 : 卷 包 裹 法 从 最 左 边 的 最 低 点 P 0 开 始 找 一 个 点 P 1, 使 得 P 0 为 起 点 的 水 平 方 向 的 射 线 到 P 0 P 1 的 角 度 最 小 然 后 找 下 一 个 点 P 2, 使 得 P 2 P 1 到 P 1 P 0 角 度 最 小 则 P 0 P 1 P m 是 凸 包 上 的 顶 点

卷 包 裹 法 细 节 及 效 率 分 析 实 际 比 较 的 时 候, 不 一 定 要 用 角 度 来 衡 量 可 以 采 用 叉 乘 来 判 断 : 只 要 知 道 相 对 的 方 向 ( 顺 时 针 还 是 逆 时 针 ) 就 可 以 比 如 判 断 AC1 比 AC2 的 夹 角 小, 只 要 判 断 AC1 在 AC2 的 右 边 这 样 每 次 查 找 需 要 O(n) 的 时 间 复 杂 度 因 此 总 的 时 间 复 杂 度 为 O(n2)

Graham-Scan 法 Graham-Scan 算 法 每 一 步 是 得 到 一 个 临 时 凸 包 只 要 当 前 点 在 上 一 条 边 的 左 手 方 向, 就 加 入 这 个 点 否 则 回 溯, 直 到 新 的 点 在 左 手 方 向 为 止

Graham-Scan 法 用 水 平 序 先 按 y 坐 标 排 y 相 同 的 按 x 坐 标 排 2 次 扫 描 先 从 第 1 个 点 即 0 开 始 到 最 后 1 个 点 即 9 得 到 右 链 再 从 最 后 1 个 点 即 9 开 始 到 第 1 个 点 即 0, 不 包 括 已 经 在 右 链 的 点 时 间 复 杂 度 O(nlogn)

凸 包 的 应 用 凸 包 的 性 质 左 链 右 链 单 调 性 应 用 问 题 点 与 凸 包 的 位 置 关 系 : 形 内 和 形 外 直 线 与 凸 包 的 位 置 关 系 : 最 近 点 和 最 远 点

小 结 解 析 方 法 点 积 叉 积 判 断 线 段 相 交 面 积 求 法 点 与 多 边 形 的 位 置 关 系 求 解 凸 包 凸 包 应 用

例 :Open-air shopping malls(2009 宁 波 赛 区 ) 平 面 上 有 n 个 圆, 给 定 他 们 各 自 的 圆 心 和 半 径 保 证 任 意 两 个 圆 不 会 互 相 重 叠 现 在 求 一 个 大 圆, 它 的 圆 心 与 某 个 给 定 圆 的 圆 心 重 合, 且 对 于 每 一 个 给 定 的 圆, 大 圆 至 少 覆 盖 该 圆 面 积 的 一 半 请 求 得 满 足 要 求 的 大 圆 的 最 小 半 径

例 :Open-air shopping malls(2009 宁 波 赛 区 ) 困 难 问 题 : 直 接 求 满 足 要 求 的 最 小 半 径 简 单 问 题 : 已 知 一 个 半 径, 要 判 断 它 是 否 覆 盖 了 给 定 圆 的 至 少 一 半 面 积 性 质 : 当 圆 心 确 定, 若 半 径 r 的 圆 可 以 覆 盖 每 一 个 给 定 圆 至 少 一 半 的 面 积, 那 么 对 于 半 径 R>r 的 圆, 都 可 以 覆 盖 至 少 一 半 的 面 积 算 法 : 二 分 答 案

例 :Open-air shopping malls(2009 宁 求 两 圆 的 相 交 面 积 波 赛 区 )

例 :Open-air shopping malls(2009 宁 算 法 流 程 枚 举 圆 心 位 置 O i 波 赛 区 ) 二 分 查 找, 求 得 对 于 当 前 圆 心 位 置, 满 足 要 求 的 最 小 半 径 r i 记 录 上 述 所 有 r i 中 的 最 小 值, 并 且 输 出 结 果 时 间 复 杂 度 O(n 2 logn)

例 :Rotational Painting(2010 杭 州 赛 区 ) 有 一 块 均 匀 厚 度 的 多 边 形 玻 璃 板, 现 在 需 要 将 它 稳 定 地 竖 直 放 置, 求 有 多 少 种 不 同 的 放 置 方 法 题 目 描 述 中 的 图 1 和 图 2 分 别 表 示 两 个 多 边 形 的 所 有 放 置 方 法, 而 图 3 中 的 两 种 放 法 我 们 认 为 是 不 稳 定 的

例 :Rotational Painting(2010 杭 州 赛 稳 定 的 定 义 区 ) 多 边 形 玻 璃 板 的 重 心 向 水 平 面 作 垂 线 时, 垂 足 落 在 支 撑 边 所 在 的 线 段 上 ( 不 包 括 线 段 端 点 )

例 :Rotational Painting(2010 杭 州 赛 区 ) 对 多 边 形 支 撑 边 的 枚 举 由 于 有 可 能 出 现 凹 多 边 形, 因 此 可 供 选 择 的 支 撑 边 包 括 该 多 边 形 的 凸 包 的 所 有 边 重 心 的 求 法 有 向 质 量 ( 回 顾 有 向 面 积 )

例 :Rotational Painting(2010 杭 州 赛 重 心 的 求 法 区 ) 对 于 三 顶 点 坐 标 为 (x 1,y 1 ) (x 2,y 2 ) 及 (x 3,y 3 ) 的 三 角 形, 其 重 心 公 式 为 : x o =(x 1 +x 2 +x 3 )/3 y o =(y 1 +y 2 +y 3 )/3 多 边 形 三 角 剖 分 有 向 面 积 作 为 质 量 ( 有 向 质 量 )

例 :Rotational Painting(2010 杭 州 赛 总 结 求 出 多 边 形 凸 包 ; 区 ) 求 出 多 边 形 重 心 坐 标 ; 由 重 心 向 每 一 条 凸 包 边 所 在 直 线 引 垂 线, 通 过 垂 足 的 位 置 判 断 该 凸 包 边 能 否 作 为 支 撑 边 并 在 枚 举 过 程 中 统 计 符 合 条 件 的 支 撑 边 ( 即 摆 放 方 法 ) 的 个 数

例 :Shade of Hallelujah Mountain(2010 福 州 赛 区 ) 给 出 一 个 点 光 源 一 个 凸 多 面 体 和 一 个 平 面, 保 证 多 面 体 和 光 源 处 在 平 面 的 同 一 侧, 要 求 平 面 上 阴 影 的 面 积

例 :Shade of Hallelujah Mountain(2010 福 州 赛 区 ) 本 题 的 解 题 过 程 可 以 分 为 两 步 第 一 步 首 先 求 出 凸 多 面 体 的 每 个 顶 点 在 平 面 上 的 投 影 第 二 步 将 平 面 旋 转 到 x-y 平 面, 用 二 维 凸 包 求 出 阴 影 面 积 大 小 当 然 也 可 以 求 出 阴 影 多 边 形 以 后 用 三 维 凸 包 算 面 积

例 :Shade of Hallelujah Mountain(2010 福 州 赛 区 ) 第 一 步 ( 空 间 解 析 几 何 ) 求 顶 点 在 凸 多 面 体 投 影 这 一 步 相 当 于 求 射 线 和 平 面 的 交 射 线 可 以 看 成 起 点 加 向 量 的 形 式, 即 (x s,y s,z s )+t(dx,dy,dz) t 0 的 形 式, 联 立 平 面 方 程 ax+by+cz=d 可 以 求 出 交 点 位 置 在 求 交 点 结 束 以 后, 我 们 可 以 知 道, 当 交 点 个 数 为 0 时, 阴 影 大 小 为 0; 当 交 点 个 数 等 于 多 面 体 顶 点 个 数 的 时 候, 阴 影 面 积 是 有 限 值 ; 否 则 阴 影 面 积 是 无 限 的 第 二 步 ( 空 间 解 析 几 何 ) 旋 转 平 面 这 一 步 在 题 目 的 提 示 中 有 比 较 详 细 的 介 绍, 没 有 准 备 三 维 旋 转 公 式 的 参 赛 选 手 也 是 有 足 够 的 知 识 去 解 决 这 道 题 的 第 三 步 ( 计 算 几 何 ) 求 凸 包 O(nlogn)

例 :Tornado(2008 北 京 赛 区 ) 平 面 上 一 个 质 点 从 点 (x t1,y t1 ) 开 始, 以 速 度 v t 在 点 (x t1,y t1 ) 到 (x t2,y t2 ) 之 间 做 往 返 匀 速 直 线 运 动 另 一 个 质 点 从 点 (x w1,y w1 ) 开 始, 以 速 度 v w 沿 着 从 (x w1,y w1 ) 为 端 点 的 某 射 线 方 向 作 匀 速 直 线 运 动 设 两 个 质 点 在 运 动 过 程 中 最 近 的 距 离 为 d 给 定 两 个 阈 值 d l 和 d w, 若 d<d l 则 输 出 Dangerous ; 若 d>d w 则 输 出 Miss ; 否 则 输 出 Perfect

例 :Tornado(2008 北 京 赛 区 ) 相 对 运 动

例 :Tornado(2008 北 京 赛 区 ) 求 质 点 B 到 折 线 的 最 近 距 离 求 质 点 B 到 两 组 等 距 平 行 线 段 的 最 近 距 离

例 :Tornado(2008 北 京 赛 区 ) 特 殊 情 况 沿 射 线 走 的 质 点 速 度 为 0 的 情 况 沿 线 段 来 回 走 的 质 点 速 度 为 0 的 情 况 沿 线 段 来 回 走 的 质 点 运 行 的 线 段 长 度 为 0 的 情 况

例 :Ancient vending machine(2009 宁 波 赛 区 ) 有 一 枚 多 边 形 的 硬 币, 以 及 平 面 上 一 个 多 边 形 的 孔 洞 要 求 判 断 能 否 做 到 : 在 孔 洞 上 方 为 硬 币 选 择 好 一 个 位 置 后 松 手, 让 硬 币 竖 直 下 落, 硬 币 会 穿 过 孔 洞 ( 假 定 硬 币 的 初 始 角 度 可 以 随 意 调 整, 而 且 硬 币 下 落 过 程 中 在 任 何 方 向 都 不 会 发 生 旋 转 ) 实 际 上 就 是 要 问 是 否 存 在 该 硬 币 的 一 个 平 面 投 影, 该 投 影 否 能 完 全 被 多 边 形 孔 洞 包 含 孔 洞 和 硬 币 都 有 可 能 是 凹 多 边 形 的, 但 都 不 会 自 交

例 :Ancient vending machine(2009 宁 波 赛 区 )

例 :Ancient vending machine(2009 宁 波 赛 区 ) 硬 币 径 直 下 投 的 分 析 最 佳 的 投 硬 币 方 案 一 定 是 垂 直 下 投

例 :Ancient vending machine(2009 宁 波 赛 区 ) 求 硬 币 多 边 形 最 短 的 垂 直 投 影 线 段 的 长 度 l max 最 短 距 离 的 两 条 平 行 切 线, 其 中 一 条 一 定 平 行 于 某 条 凸 包 边

例 :Ancient vending machine(2009 宁 波 赛 区 ) 求 孔 洞 多 边 形 长 度 最 长 且 完 全 在 孔 洞 内 部 的 线 段 长 度 L min 一 定 有 两 个 多 边 形 的 顶 点 在 这 样 的 最 长 线 段 上

例 :Ancient vending machine(2009 宁 波 赛 区 ) 求 得 某 条 直 线 在 多 边 形 内 部 的 最 长 段

例 :Ancient vending machine(2009 宁 波 赛 区 ) 求 得 上 述 两 个 问 题 之 后, 若 l max <=L min, 则 原 问 题 有 解, 硬 币 是 legal 的 ; 否 则 原 问 题 无 解, 硬 币 是 illegal 的 整 个 算 法 的 时 间 复 杂 度 是 O(n 4 ).

例 :Gunshots(2010 杭 州 赛 区 ) 平 面 上 有 M 个 任 意 多 边 形 ( 可 凹 且 可 自 交 ), 以 及 N 条 射 线 保 证 任 何 两 个 多 边 形 之 间 可 以 用 一 条 直 线 完 全 分 离, 任 一 射 线 的 端 点 和 任 一 多 边 形 之 间 也 可 以 用 一 条 直 线 完 全 分 离 对 于 每 一 条 射 线, 若 其 与 某 些 多 边 形 相 交, 求 出 交 点 距 离 射 线 端 点 最 近 的 多 边 形 编 号 ; 若 没 有 于 任 何 多 边 形 相 交, 输 出 MISS

例 :Gunshots(2010 杭 州 赛 区 ) we assume that any two polygons can be completely separated by a line. Also each start point of the gunshot can be separated from each polygon by a line. ( 我 们 假 设 任 意 两 个 多 边 形 都 可 以 被 一 条 直 线 完 整 分 离 并 且 任 一 射 线 起 点 和 任 一 多 边 形 都 可 以 被 一 条 直 线 完 全 分 开 )

例 :Gunshots(2010 杭 州 赛 区 ) 判 断 射 线 与 凸 包 是 否 相 交 判 断 直 线 与 凸 包 是 否 相 交

例 :Gunshots(2010 杭 州 赛 区 ) 利 用 凸 包 左 右 链 斜 率 单 调 性 降 低 时 间 复 杂 度

- THE END - Thank you for your attention!

例 :POJ 2972 Laser-ball (Northeastern Europe 2004, Western Subregion) 题 目 大 意 : 在 平 面 上 有 N(<=100) 块 镜 子, 镜 子 看 作 是 线 段, 双 面 反 光, 镜 子 之 间 互 不 相 交 激 光 威 力 有 限, 至 多 反 射 K(<=10) 次, 允 许 在 同 一 面 镜 子 上 反 射 多 次, 并 且 保 证 N^K<=1e6 激 光 可 以 贴 着 镜 子 传 播, 并 且 在 激 光 与 目 标 点 误 差 小 于 1e-4 的 时 候 认 为 是 击 中 激 光 从 (0,0) 发 射, 问 是 否 能 够 击 中 (X,Y) 点? 如 果 可 以, 给 出 一 种 方 案 思 考 : 反 射 到 底 表 示 什 么?N^K 的 值 又 有 什 么 意 义?

例 :Laser-ball 题 目 只 要 求 求 出 一 种 方 案, 因 此 我 们 从 镜 面 反 射 的 物 理 意 义 来 处 理 这 道 题 很 明 显, 题 目 意 思 中 的 N^K<=1e6 就 是 枚 举 的 一 个 提 示, 而 且 镜 子 可 以 多 次 反 射, 降 低 了 很 多 需 要 处 理 的 繁 杂 情 况

例 :Laser-ball 每 多 一 次 镜 面 反 射, 对 每 面 镜 子 相 当 于 多 出 了 一 个 目 标 点 因 此, 多 一 次 镜 面 反 射 总 目 标 点 的 数 目 就 翻 了 N 倍 题 目 限 定 了 N^K<=1e6, 就 意 味 着 就 算 不 去 除 任 何 重 复 计 算 的 情 况, 时 间 复 杂 度 依 然 能 够 承 受

例 :Laser-ball 因 此, 我 们 列 举 出 所 有 经 过 至 多 K 次 镜 面 反 射 之 后 目 标 点 可 能 存 在 的 位 置 算 出 这 些 就 完 了 吗? NO! 必 须 对 这 些 位 置 进 行 验 证, 能 否 成 功 击 中 目 标? 验 证 的 方 法 则 是 模 拟

例 :POJ 3502 Flight Safety (Northwestern Europe 2007) 题 目 大 意 : 给 定 了 若 干 多 边 形 大 陆 和 一 条 折 线 段 航 线, 问 在 航 线 上 距 离 陆 地 最 远 的 点 距 离 陆 地 的 距 离

例 :Flight safety 思 考 : 距 离 大 陆 最 远 的 点 有 什 么 特 点? 如 何 在 能 找 到 这 个 点? 不 断 扩 展 原 来 的 大 陆 的 边 界, 那 么 最 后 一 个 被 覆 盖 的 点 一 定 是 距 离 大 陆 最 远 的 点 二 分 扩 展 的 大 小, 然 后 模 拟 扩 展 的 结 果, 检 验 覆 盖 的 结 果

例 :POJ 3433 Road accident (Northeastern Europe 2005, Far-eastern Subregion)

例 :Road accident 题 目 大 意 : 有 两 辆 车 子 行 驶 在 路 上 现 在 已 知 初 始 时 车 辆 左 前 方 和 左 后 方 的 坐 标, 车 子 的 宽 度, 车 子 行 进 的 方 向 以 及 速 度 车 子 被 看 作 是 矩 形, 并 根 据 位 置 划 分 为 4 个 区 域 求 两 车 撞 击 的 时 候 到 底 是 哪 两 个 区 域 相 撞? 同 时 相 撞 时 取 编 号 小 的 思 考 : 车 子 怎 样 才 算 相 撞? 车 子 相 撞 的 状 态 究 竟 有 多 少 种?

例 :Road accident 通 过 刚 刚 的 描 述, 本 题 的 麻 烦 之 处 在 于 模 拟 两 车 相 撞 的 过 程, 在 两 车 都 运 动 的 时 候, 无 法 直 观 地 计 算 出 相 撞 的 情 况 经 典 物 理 方 法 : 选 择 相 对 参 考 系, 令 一 台 车 子 固 定 不 动, 再 来 分 析 另 一 台 车 子 的 情 况

例 :Road accident 然 后, 讨 论 车 子 相 撞 时 候 的 样 子 点 对 点? 点 对 线? 线 对 线? 依 次 枚 举 各 种 情 况 下 两 车 相 撞 的 时 间, 选 择 其 中 最 小 的 一 个, 那 就 是 两 车 真 正 相 撞 的 情 况