《基于凸剖分的点在多边形内的高效判定.pdf》由会员分享，可在线阅读，更多相关《基于凸剖分的点在多边形内的高效判定.pdf（6页珍藏版）》请在金锄头文库上搜索。
1、!第!卷!第期!#$年月基 于 凸 剖 分 的 点 在 多 边 形 内 的 高 效 判 定李!静&!)!王 文 成&!吴 恩 华&!&4中 国 科 学 院 软 件 研 究 所 计 算 机 科 学 国 家 重 点 实 验 室 !北 京&%!4澳 门 大 学 科 技 学 院 计 算 机 与 信 息 科 学 系 !澳 门 %)4中 国 科 学 院 研 究 生 院 !北 京&)3!*$&!$&收 稿 !$&$!)收 修 改 稿! 国 家 自 然 科 学 基 金 项 目 批 准 号 #*)#&$-国 家 )九 七 三 *计 划 项 目 批 准 号 #!H9)&!&!$-国 家 )八 六 三 *计 划 项
2、 目 批 准 号 #!*FF&)*$和N?L难 问 题&)!为 此 !我 们采 用 下 面 的 方 法 进 行 凸 剖 分 !使 所 生 成 的 凸 多 边 形不 是 很 多4该 方 法 是 #先 用 文 献 &中 方 法 将 多 边形 剖 分 成 一 些 单 调 多 边 形 !再 用 与 文 献 &中 单 调多 边 形 三 角 化 类 似 的 方 法 将 各 个 单 调 多 边 形 凸 剖分4建 立 二 叉 树 来 管 理 剖 分 的 凸 多 边 形 时 !我 们 用一 些 与 凸 多 边 形 的 边 共 线 的 直 线 作 为 分 割 直 线 !迭代 地 进 行 空 间 剖 分 !直 至
3、叶 节 点 只 包 含 一 个 凸 多 边形 !在 此 !分 割 直 线 存 储 在 相 应 的 中 间 结 点 中 !而与 分 割 直 线 相 交 的 凸 多 边 形 在 其 左 右 子 树 中 均 包含4为 使 二 叉 树 尽 可 能 平 衡 !即 每 次 分 割 的 左 右 子树 中 包 含 数 目 相 近 的 凸 多 边 形 !且 使 树 的 高 度 尽 可能 低 以 提 高 检 测 速 度 !我 们 设 计 了 下 面 的 参 数 来 选择 分 割 直 线4假 设 用 一 条 分 割 直 线 分 出 的 左 侧 集 合-右 侧集 合J-相 交 集 合?中 所 包 含 的 凸 多 边
4、形 个 数 分别 为%-!%J!%?+&$纯 净 度 #由 于?中 的 元 素 同 时 在 左 -右 子树 中 !因 此 它 的 容 量 越 大 !整 棵 树 冗 余 就 越 多 !使得 树 的 高 度 较 大 %反 之 !则 树 的 高 度 较 小+故 定 义)纯 净 度 *以 考 察 一 个 分 叉 方 案 中?的 容 量 !其 计算 公 式 是7BL:?M?8:?$&%-(%J%-(%J(%?!该 值 越大 !则 相 关 的 冗 余 就 越 少+!$平 衡 度 #节 点 总 数 相 同 的 树 !若 其 各 个 节点 的 左 右 子 树 越 平 衡 !则 整 棵 树 的 高 度 就 越
5、低+因此 定 义 )平 衡 度 *以 考 察 左 -右 子 树 是 否 平 衡 !其计 算 公 式 是;B9-/-75?M?8:?$&G%-)%J%-(%J!该 值 越 大 !则 越 平 衡+显 然 !平 衡 度 和 纯 净 度 的 值 越 高 !则 建 立 的 树结 构 越 好+但 这 两 个 参 数 的 变 化 不 是 协 调 的+为此 !对 一 条 分 割 边 相 关 的 平 衡 度 和 纯 净 度 !我 们 取其 中 数 值 较 少 的 那 个 值 作 为 衡 量 该 边 可 选 作 分 割 直线 的 依 据 !称 为 选 择 度BD?/?5C.67M?8:?$+于 是 !挑 选 分
6、割 直 线 时 !我 们 对 当 前 结 点 中 的所 有 凸 多 边 形 的 边 进 行 检 测 !为 与 每 条 边 共 边 的 直线 计 算 它 的 选 择 度 !并 以 选 择 度 值 最 高 的 那 条 直 线作 为 当 前 节 点 的 分 割 直 线+以 图&为 例 !为 根 节 点的 左 子 树 选 择 分 割 直 线 时 它 的 凸 多 边 形 集 合&7&!)8$!线 段W=对 应 的 参 数7BW= &!.)!;BW=&!所 以 其 选 择 度BW= &;BW=%而 线 段c=的 参 数7Bc=&!;Bc=&!.)!所 以 其 选 择 度为Bc=&;Bc=+这 里BW=/B
7、c=!故 选 择 线 段c=所 在 直 线 为 该 节 点 的 分 割 直 线+根 据 我 们 的 方 法选 择 分 割 直 线 所 建 立 的 二 叉 树&5$!显 然 比 图&;$中 的 二 叉 树 要 质 量 高 !因 为 它 的 叶 节 点 少 !高 度 低+图!凸 多 边 形 的 二 叉 树 组 织 示 意 图中 间 节 点 记 录 相 关 分 割 直 线 所 在 的 边 !叶 子 节 点 记 录 对 应 的 凸 多 边 形-$多 边 形 的 凸 部 分 %;$非 优 化 的 二 叉 树 %5$优 化 的 二 叉 树*33!第!卷!第期!#$年月!挑 选 分 割 直 线 时 !如 各
8、 条 候 选 分 割 直 线 的 选 择度 都 很 低 !则 意 味 着 此 时 继 续 构 造 子 树 已 无 价 值 !因 为 层 次 的 加 深 与 树 的 不 平 衡 将 带 来 较 大 的 负 面 影响 !不 利 于 检 测 效 率 的 提 高+对 此 !我 们 就 将 该 节点 作 为 叶 节 点+直 观 的 讲 !如 果 一 个 节 点 值 得 继 续分 割 !那 么 其?所 含 的 凸 多 边 形 不 应 多 于 该 节 点所 有 凸 多 边 形 的 一 半 !并 且 其-和J所 含 的 凸 多边 形 数 目 应 相 当+因 此 !我 们 以+#作 为 评 判 是 否继 续 划
9、 分 的 选 择 度 阈 值 !称 之 为 分 割 阈 值 !即 当 所有 候 选 直 线 的 选 择 度 低 于+#时 就 停 止 分 割+该 阈值 的 有 效 性 得 到 了 大 量 实 验 的 验 证+!三 叉 树 形 式 的 实 现按 上 述 方 式 建 立 二 叉 树 时 !与 分 割 直 线 相 交 的凸 多 边 形 会 在 其 左 右 子 树 中 都 出 现4这 样 !就 增 加了 冗 余 !会 增 加 树 的 高 度 和 建 树 时 间4为 降 低 开销 !我 们 对 二 叉 树 组 织 进 行 三 叉 树 的 实 现 !即 #位于 分 割 直 线 两 边 的 凸 多 边 形
10、分 别 生 成 两 个 子 结 点称 为 左 -右 子 树 $!而 与 分 割 直 线 相 交 的 凸 多 边 形再 生 成 一 个 子 结 点 称 为 中 间 子 树 $4显 然 !该 三 叉树 的 本 质 还 是 二 叉 树 !依 然 适 于 进 行 二 分 查 找4!近 似 选 择 分 割 直 线为 每 个 中 间 节 点 选 择 分 割 直 线 时 !如 果 考 察 所有 候 选 直 线 是 十 分 耗 时 的4根 据 概 率 理 论 !只 要 检测 一 定 量 的 候 选 者 就 可 找 到 一 条 足 够 好 的 分 割 直线 !尽 管 它 不 一 定 是 最 佳 的 !但 所 构
11、 造 的 树 仍 能 很好 地 加 速 判 定 计 算4为 此 !我 们 为 选 择 度 设 置 另 外一 个 阈 值 !称 为 近 似 阈 值 %然 后 从 候 选 直 线 中 进 行随 机 的 选 择 考 察 !一 旦 某 条 直 线 的 选 择 度 超 过 近 似阈 值 就 以 它 为 分 割 直 线 !不 再 继 续 考 察4从 上 面 的讨 论 可 知 !近 似 阈 值 应 大 于 分 割 阈 值 !即4#4针对 阈 值 变 化 的 实 验 表 明 !预 处 理 时 间 随 阈 值 的 增 大而 增 大 !并 在4#之 后 急 剧 上 升 !而 空 间 和 判 定时 间 则 随 之
12、减 少4这 是 因 为 近 似 阈 值 增 大 时 !寻 找合 适 分 割 线 的 时 间 将 增 大 !所 建 立 的 树 结 构 质 量 更高4综 合 各 方 面 情 况 !我 们 取4#作 为 近 似 阈 值4!点 包 容 性 判 定新 算 法 的 点 包 容 性 判 定 分 为 两 步 #&$根 据 二 叉 树 找 到 最 可 能 包 含 被 测 点 的 凸 多边 形4这 只 需 迭 代 地 考 察 被 测 点 位 于 一 条 分 割 直 线的 哪 一 边 并 检 测 其 相 应 的 子 节 点 !直 至 一 个 叶 节点4!$判 定 被 测 点 是 否 位 于 所 找 到 的 凸 多
13、 边 形 内+如 果 叶 子 节 点 中 包 含 多 个 凸 多 边 形 !则 要 逐 个 地 检测 这 些 凸 多 边 形+在 此 !我 们 用 空 间 需 求 最 少 的 分层 法&!+它 为 一 个 凸 多 边 形 的 边 生 成!个 单 调 层次 !如 图!所 示 的 两 条e值 单 调 边 链&7&!)!/!$8!;&7;&!;!;)!/!;%8!4&545$!;6&565%$为7的 顶 点 !e45e4(&!e;45e;4(&!且&;&!$&;%+设 被 测 点 为3!过3作 平 行 于Y轴 的 直 线A+我 们 先 用 二 分 查 找 法判 定e&位 于!;的 哪 两 个 顶 点
14、 的e值 区 段 内 !也 就 是 判 定 与7的 哪 两 条 边 相 交+若 无 交 则3必 定位 于7外+否 则 求 出 交 点7!7;!判 定Y3是 否位 于Y7与Y7;之 间+若 是 则3位 于7内 !否 则 位于7外+图!分 层 法 的 凸 多 边 形 点 包 容 性 判 定(!复 杂 度 分 析建 树 过 程 中 !不 同 的 多 边 形 被 剖 分 成 的 凸 多 边形 个 数 和 各 个 凸 多 边 形 的 边 数 会 有 很 大 差 异+但是 !不 失 一 般 性 !可 按 照 下 述 的 假 设 进 行 复 杂 度 分析 !即 #对 于 有%个 顶 点 的 原 多 边 形
15、!它 被 剖 分 成$个 凸 多 边 形 !且 这 些 凸 多 边 形 的 边 数 均 为I+由+/?:公 式 可 知 !_$I$&_%$+(!凸 多 边 形 个 数由 凸 剖 分 算 法 可 知 !剖 分 形 成 的 新 边 全 部 位 于多 边 形 内 !原 多 边 形 的 边 旧 边 $不 会 被 两 个 凸 多 边形 共 享 !且 大 多 数 凸 多 边 形 包 含 若 干 条 旧 边4由 于旧 边 不 会 被 分 割 且 不 增 加 新 点 !所 以 凸 多 边 形 的 数量 与 多 边 形 凹 点 个 数 呈 线 性 关 系 !且 小 于 旧 边 的 个33!第!卷!第期!#$年月
16、数4而 对 于 梯 形 法 来 说 !它 们 要 分 割 旧 边 增 加 新 点以 形 成 梯 形 !使 得 梯 形 的 数 目 通 常 会 大 于 旧 边 的 边数4因 此 新 算 法 需 要 处 理 的 凸 多 边 形 要 远 少 于 梯 形法 的 梯 形 !由 此 可 减 少 空 间 开 销 并 获 得 更 快 的 判 定速 度4(!空 间新 算 法 要 存 储 凸 多 边 形 的 顶 点 序 列 和 树 节 点 的信 息 !在 此 !树 的 中 间 节 点 存 储 分 割 直 线 的 方 程 !而 其 叶 节 点 存 储 指 向 对 应 凸 多 边 形 的 指 针+由)+&节 的 分 析 可 知 !凸 多 边 形 个 数 小 于 旧 边 个 数 !即$/%+根 据+/?:公
