多边形合并的算法研究

《多边形合并的算法研究》由会员分享，可在线阅读，更多相关《多边形合并的算法研究（3页珍藏版）》请在金锄头文库上搜索。

1、多 边 形 合 并 的 算 法 研 究叶 琳 邱 龙 辉青 岛 化 工 学 院 机 械 系 青 岛 双 欢 抖摘 要 本 文 介 绍 了 多 边 形 合 并 算 法 的 发 展 现 状 和 应 用 前 景 , 提 出 一 种 新 的 基 于 扫 描 线 技 术 的 多 边 形 合 并 算 法 , 重 点 讨 论 了 算法 的 技 术 支 持 , 病 态 多 边 形 的 修 复 等 , 采 用 本 文 提 出 的 新 算 法 , 在 雷 鸟 式 , 内 存 的 机 上 对 组 复 杂 的 多 边 形 进 行了 合 并 计 算 , 结 果 表 明 , 本 算 法 可 行 。关 键 词 合 并 多

2、边 形 计 算 几 何 扫 描 线 技 术心玩构 粥 从 对 四 咬 才 五 掩 冲 把 的 武 罗 , 认 嗯 山 口 加 众 以 了 凸 翻 血 心 几 肠 诫 盯 , 伍 吧 由 。 肠 浏习 戚 门 妞 四 绳 丽 加 屺 卿 试 卯 卿 朋 用 口抽 叩 而 , 叨 山 司 免 山 氏 沈 脚 脚 垃 坦 拌 肠 到 哭 曰 祀, 切 让 旧 邵 沉 翻 , 脚 阎 户 男 田 飞 鸣 山 刘 比 润 即 】卿 拓 艾 而取 粉 呱 找 如 施 心 网 兴 护 诩 七 。 目 鱿 盯 犯 匀 , 反 田前 言多 边 形 是 使 用 最 多 的 几 何 形 状 , 在 维 图 形 中

3、, 多边 形 用 于 表 达 边 界 面 。 我 们 可 以 对 多 边 形 进 行 各 种 运算 一 。 较 复 杂 的 任 务 是 用 多 条 线 划 分 一 个 多 边 形 ,确 定 其 外 形 , 将 其 分 成 几 个 简 单 的 多 边 形 等 。 完 成 较复 杂 的 任 务 必 须 仔 细 研 究 算 法 , 才 能 有 效 运 算 。 布 尔运 算 是 极 为 重 要 的 , 但 现 有 的 算 法 中 只 有 为 数 不 多 的靠 其 支 持 。 例 如 对 凸 面 多 边 形 , 建 立 了 运 算 时间 复 杂 度 为 的 一 种 有 效 算 法 , , 。 均 为 多

4、边 形 的 顶 点 数 川 。 本 文 讨 论 合 并 一 组 多 边 形 的 算 法 描述 和 算 法 执 行 问 题 。 介 绍 了 多 边 形 合 并 算 法 的 发 展 现状 和 应 用 前 景 , 引 人 了 输 人 多 边 形 二 尸 。 , , , ,凡 、 合 并 的 多 边 形 组 日 。 , 口 , , , 一 、 非 简单 多 边 形 、 可 修 复 的 病 态 多 边 形 等 概 念 , 以 此 为 基 础 ,本 文 将 给 出 一 种 新 算 法 。多 边 形 , 如 果 满 足 以 下 二 个 条 件 相 邻 线 段 只 在 一个 共 同 点 相 连 非 相 邻 线

5、 段 不 在 任 何 共 同 点 相 连 ,则 为 简 单 多 边 形 。 当 线 段 与 多 边 形 顶 点 相 连 时 , 这 些线 段 为 多 边 形 的 边 。如 多 边 形 不 能 满 足 这 个 条 件 , 则 为 非 简 单 多 边形 , 或 称 之 为 病 态 多 边 形 , 如 图 中 的 多 边 形 即为 病 态 多 边 形 , 在 计 算 几 何 和 计 算 机 图 学 中 , 目 前 的 主要 算 法 只 能 对 简 单 多 边 形 进 行 运 算 。 如 果 多 边 形 不 包含 孔 , 它 严 格 的 将 平 面 分 成 二 部 分 边 界 内 与 边 界 外 。如

6、 果 多 边 形 包 含 有 限 的 孔 , 它 将 平 面 分 成 多 于 二 个 的区 域 , 但 只 有 一 个 是 不 封 闭 的 , 如 图 所 示 。办 鱼 画非 简 单 多 边 形 简 单 多 边 形图 多 边 形算 法 的 技 术 支 持多 边 形由 平 面 上 几 个 点 。 , , , , 。 一 , 和 连 接 这 些 点 的条 线 段 , 。 。 尸 , , , 夕 、 夕 , 。 一 , 。 一 , 尹 。 , 组 成 一 个回 路 和 环回 路 由 一 系 列 将 平 面 划 分 成 有 限 或 无 限 个 区 域的 边 构 成 , 每 个 多 边 形 有 一 个

7、确 切 的 回 路 , 回 路 按 顺收 稿 日 期 一 一 。 叶 琳 , 副 教 授 主 研 领 域 计 算 机 图 形 学 ,虚 拟 现 实 技 术 。时 针 方 向 旋 转 。环 由 一 系 列 多 边 形 的 内 边 界 组 成 , 在 一 个 多 边 形内 有 乓 个 环 岌 , 其 中 有 些 环 可 以 互 相 嵌 套 。奇 数 个 数 的 环 按 反 时 针 方 向 旋 转 , 偶 数 个 数 的 环 按 顺时 针 方 向 旋 转 。合 法 多 边 形 及 非 法 多 边 形根 据 多 边 形 的 性 质 , 可 以 分 为 种 情 况简 单 多 边 形 , 这 是 最 常

8、见 和 所 希 望 的 情 况环 接 触 回 路 或 多 边 形 中 其 他 的 环 。 在 一 些 实 际 应用 中 这 是 可 以 接 受 的 。 如 图 所 示 , 环 , 分 别 在不 同 的 点 上 接 触 到 。 和 回 路 , 这 种 情 况 在 本 算 法 中可 以 认 为 多 边 形 合 法 回 路 与 环 的 边 接 触 或 相 交 。这 样 的 多 边 形 不 能 满 足 完 整 图 形 的 条 件 , 为 了 防 止 算法 出 现 错 误 , 必 须 能 检 测 出 这 种 错 误 的 多 边 形 即 非 法多 边 形 或 称 病 态 多 边 形 , 如 果 可 能 的

9、 话 , 将 其 转 化 成 合法 的 多 边 形 否 则 就 必 须 从 输 人 数 据 中 剔 除 。多 边 形 组 与 合 并 多 边 形 组 曰令 个 合 法 多 边 形 组 成 的 多 边 形 组 二 , 尸 , , , 尺 一 , , 将 多 边 形 只 的 回 路 记 为 , , 其 环为 尺 , , 式 中 代 表 环 所 属 的 多 边 形 , 表 示 环 的 连 续非 负 指 数 。 函 数 几 定 义 为 合 并 一 组 多 边 形 , 多边 形 凡 的 边 界 几 份 , 定 义 为 , 它 的内 部 边 界 定 义 为 沪 , 尸 沪 。 如 果 下 列 条 件满 足

10、 则 多 边 形 组 可 以 被 合 并多 边 形 内 部 边 界 不 重 叠 , 讯 门 功 尸 沼 二 ,撼 , , 并 多 边 形 边 界 部 分 重 叠 , 动 尸 几 门 ,二 , 撼 , , 尹 , 是 一 组 重 叠 的 边 界 点 ,也 可 以 是 空 集 。函 数 几 定 义 为 介 二 沪 一 , 一 组合 并 的 多 边 形 组日 二 口 。 , , , , 。 蕊 、 毛日 有 下 列 性 质如 果 输 人 多 边 形 组 且 只 包 含 合 法 多 边 形 , 则 输 出的 也 是 合 法 的 对 日 中 多 边 形 边 或 顶 点 的 总 数来 说 , 吻 撼 合

11、并 后 多 边 形 个 数 幕 输 人 的 多 边 形 个数 。 输 出 多 边 形 组 日 中 的 环 可 以 大 于 、 等 于 或 小 于 输人 多 边 形 组 中 的 环 。合 并 回 路图 中 有 个 多 边 形 , 相 互 之 间 可 能 有 接 触 , 顶点 用 多 边 形 的 号 数 标 记 , 从 开 始 编 号 。 虚 线 为 扫 描线 , 用 表 示 。 合 并 算 法 首 先 要 确 定 普 通 的 边 和 顶点 。 按 。 、 时 间 复 杂 度 进 行 运 算 较 困 难 , 在 这 里可 以 用 扫 描 线 方 法 。 在 计 算 机 图 形 学 和 计 算 机

12、几 何 学中 , 用 这 种 方 法 解 决 了 大 量 不 同 的 任 务 , 如 填 充 多 边形 、 构 造 图 、 多 边 形 中 梯 形 、 三 角 形 运 算 等 。合 并 算 法本 算 法 用 于 合 并 合 法 的 多 边 形 , 包 括 以 下 主 要 步骤分 别 生 成 带 有 方 向 的 多 边 形 回 路 和 环 的 列表 合 并 回 路 处 理 孔 将 孔 插 入 合 并 后的 回 路 中 。 首 先 分 别 生 成 带 有 方 向 的 多 边 形 回 路 和 环的 列 表 , 然 后 再 进 行 合 并 回 路 和 合 并 多 边 形 。图 回 路 组 实 例扫 描

13、 回 路 和 剔 除 内 部 多 边 形本 文 对 确 定 个 多 边 形 相 交 点 的 算 法 闭 作 了 改进 改 进 后 的 算 法 可 以 用 多 于 个 的 多 边 形 来 复 制 , 而且 使 算 法 大 大 加 速 。 在 扫 描 中 , 本 算 法 确 定 多 边 形 的相 对 位 置 , 这 可 使 算 法 加 速 。扫 描 线 加 速 技 术 的 概 念 是 扫 描 线 将 平 面 分 成 一条 条 的 带 状 区 域 , 在 带 中 所 要 求 的 任 务 可 以 很 迅 速 的完 成 。 扫 描 线 从 一 到 十 扫 过 平 面 , 只 在 有 任 务 的位 置 停

14、 下 来 , 进 行 计 算 或 更 新 数 据 结 构 。 在 搜 索 多 边形 的 相 交 点 时 , 所 关 注 的 是 正 被 扫 描 线 掠 过 的 多 边 形的 边 。 只 有 这 些 边 是 可 能 的 相 交 边 , 它 们 被 储 存 在 数据 结 构 数 组 一 , 称 之 为 扫 描 线 状 态 数 组玲 。 为 使 扫 描 平 滑 的 进 行 , 要 将 顶 点 按 扫 描 线 的 运动 方 向 排 序 。以 图 中 的 多 边 形 来 说 明 本 算 法 。 对 多 边 形 组中 的 每 一 个 多 边 形 只 , 其 扫 描 线 状 态 轰均 初 始 化 为 空 ,

15、 当 扫 描 线 在 位 置 。 。 时 , 比 即 被 赋值 。 以 下 考 察 几 根 扫 描 线扫 描 线 。 第 一 根 扫 描 线 。 。 通 过 顶 点 几 , 算 法 将几 , 和 氏 。 置 人 】岛 。 因 为 所 有 其 它 的 巧 均 为 空 ,所 以 算 法 将 扫 描 线 移 到 一 个 新 位 置 。 扫 描 线 。 , 顶 点。 不 属 于 任 意 一 个 已 经 扫 描 过 的 多 边 形 , 所 以 可 以 检查 是 否 被 其 他 多 边 形 封 闭 。 由 于 使 用 了 扫 描 线 , 因 此不 用 进 行 其 它 的 封 闭 性 检 查 。在 处 应

16、用 所 引 人 的 封 闭 规 则 , 可 以 对 储 存 在巩 中 的 线 段 及 多 边 形 的 边 几 。 , 、 几 。 进 行 相 交 性检 查 , 只 有 在 边 氏 , 给 出 奇 数 交 点 , 表 明 多 边 形 , 位于 多 边 形 内 时 , 相 交 才 存 在 。 将 多 边 形 尸 , 从 回 路表 伽 田 中 剔 除 , 放 人 内 部 表 中 。扫 描 线 , 将 扫 描 线 移 到 下 一 个 位 置 , 即 , , 当 扫描 线 离 开 时 , 只 有 巩 储 存 这 个 多 边 形 的 边 , 所 以实 际 上 不 进 行 相 交 性 检 查 。 通 过 顶 点 , 、 的 扫 描 线不 用 考 虑 , 因 为 它 们 与 内 部 多 边 形 尸 一 起 剔 除 了 。 在 二 处 , 所 有 的 顶 点 已 扫 描 完 , 即 扫 描 结 束 。合 并 多 边 形下 面 以 图 为 例 说 明 本 算 法 。 从 边 鸟 开 始 , 因为 这 个 边 不 与 其 他 任