Serial No. 512
现 ꢀ 代 ꢀ 矿 ꢀ 业
2011年总 第125月12第期 12 期
December. 2011
MODERN MINING
基 于 Delaunay 三 角 网 生 成 Voronoi 爆 破 图 的 研 究
卓 中 文 ꢀ 王 山 东 ꢀ 魏 生 文 ꢀ 杨 ꢀ 松
(
河 海 大 学 地 球 科 学 与 工 程 学 院 )
ꢀ
ꢀ 摘 ꢀ 要 ꢀ 阐 述 了 基 于 Delaunay 三 角 网 生 成 Voronoi 图 的 算 法 原 理 。 用 炮 孔 取 样 点 的 数 据 作 为
数 据 源 , 详 细 描 述 了 Voronoi 图 的 计 算 机 程 序 实 现 , 在 ObjectARX 2008 与 Visual Studio 2005 开 发 环
境 下 , 利 用 C#对 AutoCAD 2008 进 行 二 次 开 发 实 现 Voronoi 图 。
关 键 词 ꢀ Voronoi 图 ꢀ 炮 孔 取 样 ꢀ 品 位 分 布 图 ꢀ AutoCADꢀ 二 次 开 发
ꢀ
ꢀ Voronoi 图 又 称 Direchelct 网 格 、 WingerSeitz 区
较 少 , 所 以 采 用 逐 点 插 入 法 生 成 Delaunay 三 角 网 ,
具 体 步 骤 如 下 。
域 或 泰 森 多 边 形 , 是 计 算 几 何 的 重 要 研 究 内 容 之 一 。
Voronoi 图 的 计 算 机 自 动 生 成 方 法 研 究 源 于 20 世 纪
( 1) 遍 历 所 有 离 散 点 , 求 出 炮 孔 区 域 点 集 的 包
容 盒 , 得 到 作 为 点 集 凸 壳 的 初 始 三 角 形 并 放 入 三 角
形 链 表 。
7
0 年 代 , 广 泛 应 用 在 地 理 学 、 气 象 学 、 结 晶 学 、 航 天 、
[ 1]
, 是 解 决 距 离 计 算 、 碰 撞
核 物 理 学 、 机 器 人 等 领 域
检 测 、 路 径 规 划 、 骨 架 计 算 、 凸 包 计 算 以 及 最 小 树 生
成 等 计 算 几 何 问 题 的 有 效 工 具 。
( 2) 将 点 集 中 的 离 散 点 依 次 插 入 , 在 三 角 形 链
表 中 找 出 其 外 接 圆 包 含 插 入 点 的 三 角 形 ( 称 为 该 点
的 影 响 三 角 形 ) , 删 除 影 响 三 角 形 的 公 共 边 , 将 插 入
点 同 影 响 三 角 形 的 全 部 顶 点 连 接 起 来 , 从 而 完 成 一
个 点 在 Delaunay 三 角 形 链 表 中 的 插 入 。
( 3) 根 据 LOP 优 化 准 则 对 局 部 新 形 成 的 三 角 形
1
ꢀ Voronoi 图
1
. 1ꢀ 定 ꢀ 义
Voronoi 图 是 按 照 对 象 集 合 中 元 素 的 最 近 属 性
将 空 间 划 分 成 许 多 单 元 区 域 , 即 Voronoi 区 域 。
Voronoi 区 域 与 其 生 成
W
对 象
W
2]
。 其 数 学 定 义 : 给 定 平 面 上
一 一
W
对 应 ,
.
且 互
K
不 重 叠
Y
,
1
进 行
1
优 化
4
, 然 后
.
更 新
C
Delau
N
nay 三 角 形 链 表 。 LOP 原
[
构 成 空 间 的 一 个 划 分
理 就 是 根 据 Delaunay 三 角 网 的 性 质 对 具 有 公 共 边
的 三 角 形 组 成 的 四 边 形 进 行 判 别 , 如 果 其 中 的 某 三
角 形 的 外 接 圆 包 含 该 四 边 形 的 第 4 个 顶 点 , 则 将 该
四 边 形 的 对 角 线 交 换 , 生 成 以 另 一 条 对 角 线 为 公 共
边 的 两 个 三 角 形 。
的 点 集 P = { p1 , p2 , … p } , 由 V( p ) = n{ p | d( p, p )
n
i
i
<
d( p, p ) } ( i = 1, 2, … , n) ( 式 中 d 为 两 点 之 间 的 欧
j
式 距 离 ) 所 给 出 的 对 平 面 的 分 割 , 而 所 有 以 p ( i = 1,
i
2
, … , n) 为 生 成 元 ( 或 母 点 ) 的 多 边 形 的 集 合 V = { V
(
p ) , V ( p ) , V ( p ) , … , V ( p ) } 就 构 成 了 P 的
1 2 3 n
[ 3]
。
( 4) 循 环 执 行 上 述 ( 2) 、 ( 3) 步 , 直 到 所 有 离 散 点
插 入 完 毕 为 止 。 这 样 就 完 成 用 逐 点 插 入 法 对 Delau
nay 三 角 网 的 构 建 。
Voronoi 图
1
. 2ꢀ Delaunay 三 角 网 的 生 成 算 法
1934 年 , 俄 国 数 学 家 B. Delaunay 由 Voronoi 图
1. 3ꢀ 基 于 Delaunay 三 角 网 生 成 Voronoi 图
应 用 于 Voronoi 图 代 表 性 的 算 法 主 要 分 为 两
类 : 一 类 是 直 接 法 , 即 直 接 生 成 Voronoi 图 , 比 如 半
平 面 法 , 增 量 法 , 分 治 法 , 扫 描 线 法 等 ; 一 类 是 间 接
法 , 利 用 Voronoi 图 的 对 偶 性 , 先 生 成 Delaunay 三 角
网 , 然 后 构 造 Voronoi 图 , 这 类 方 法 有 换 边 法 , 升 维
演 化 出 了 更 易 于 分 析 应 用 的 Delaunay 三 角 网 。
Delaunay 三 角 网 具 有 良 好 的 形 态 , 在 表 达 地 表 形 态
方 面 较 为 出 色 , 是 数 字 地 面 模 型 ( 简 称 DTM) 的 一 种
[
4]
。
主 要 表 示 方 法
从 国 内 外 几 十 年 来 关 于 Delaunay 三 角 网 的 研
究 算 法 来 看 , 出 现 了 较 多 构 建 Delaunay 三 角 网 算
法 , 但 主 要 研 究 重 点 集 中 在 逐 点 插 入 法 、 三 角 网 生 长
法 、 分 治 算 法 、 凸 包 算 法 等 4 种 算 法 及 其 优 化 和 改
[
1]
。
法 等
采 用 基 于 Delaunay 三 角 网 构 造 Voronoi 图 , 具
体 算 法 如 下 。
[
5]
。 数 据 源 为 某 矿 山 炮 孔 取 样 点 , 由 于 离 散 点 比
进
(
1) 构 建 Delaunay 三 角 网 。 用 前 文 所 描 述 的 逐
点 插 入 法 构 建 Delaunay 三 角 网 。
(
2) 计 算 每 一 个 三 角 形 的 外 接 圆 圆 心 。 三 角 形
ꢀ
号ꢀ 。卓 中 文 ( 1986— ) 男 , 硕 士 研 究 生 , 210098 江 苏 省 南 京 市 西 康 路
外 接 圆 圆 心 为 三 角 形 三 边 垂 直 平 分 线 的 交 点 , 利 用
1
1
06
ꢀ
ꢀ 卓 中 文 ꢀ 王 山 东 等 : 基 于 Delaunay 三 角 网 生 成 Voronoi 爆 破 图 的 研 究 ꢀ ꢀ
ꢀ
ꢀ 2011 年 12 月 第 12 期
三 角 形 3 个 顶 点 的 平 面 坐 标 求 解 外 接 圆 圆 心 。
员 首 选 的 语 言 。 . NET Framework 主 要 包 含 一 个 非 常
大 的 代 码 库 , 可 以 在 客 户 语 言 ( 如 C#) 中 通 过 面 向
对 象 编 程 ( OOP) 技 术 来 使 用 这 些 代 码 。 这 个 库 分
为 不 同 的 模 块 , 这 样 就 可 以 根 据 希 望 得 到 的 结 果 来
选 择 使 用 其 中 的 各 个 部 分 。
(
3) 连 接 相 邻 三 角 形 的 外 接 圆 圆 心 。 根 据 是 否
有 公 共 边 判 断 2 个 三 角 形 是 否 相 邻 , 如 果 相 邻 则 连
接 它 们 的 外 接 圆 圆 心 。
(
4) 利 用 条 件 判 断 三 角 网 的 外 围 边 , 即 三 角 网
的 凸 壳 , 然 后 对 其 所 在 的 三 角 形 的 外 接 圆 圆 心 进 行
处 理 。 含 有 凸 壳 边 的 三 角 形 的 只 有 1 个 或 2 个 相 邻
的 三 角 形 , 在 处 理 此 问 题 的 时 候 , 过 去 多 采 用 的 是 三
角 形 的 外 接 圆 圆 心 在 凸 壳 边 内 作 垂 线 连 接 到 凸 壳
边 , 在 凸 壳 边 外 面 的 则 向 三 角 网 的 外 方 向 作 射 线 , 此
射 线 也 是 垂 直 于 凸 壳 的 。 离 散 点 数 据 被 已 有 的 境 界
线 所 包 围 , 所 以 构 建 Voronoi 图 的 时 候 必 须 得 考 虑
此 境 界 线 。 在 处 理 凸 壳 边 所 在 的 三 角 形 的 外 接 圆 圆
心 的 时 候 , 不 论 这 个 点 在 凸 壳 内 、 凸 壳 上 还 是 凸 壳
外 , 都 作 一 条 足 够 长 的 线 段 垂 直 于 对 应 的 凸 壳 边 , 此
线 段 至 少 应 伸 到 境 界 线 外 面 。
使 用 Visual Studio 2005 进 行 . NET 开 发 。 Visu
al Studio 2005 不 是 开 发 C#应 用 程 序 所 必 须 的 , 但 使
[
7]
。 通 过 安 装 ObjectARX
用 它 可 以 使 任 务 更 简 单
软 件 包 , Visual Studio 2005 可 以 直 接 对 AutoCAD 进
行 二 次 开 发 。
2. 2ꢀ 程 序 实 例
程 序 的 数 据 源 为 某 矿 山 的 炮 孔 取 样 点 数 据 。 炮
孔 取 样 是 露 天 矿 探 采 结 合 的 工 艺 手 段 之 一 , 炮 孔 提
取 矿 石 原 始 数 据 用 于 预 测 矿 体 模 型 走 向 、 矿 石 质 量
分 布 及 编 制 配 矿 计 划 等 方 面 。 矿 山 在 进 行 爆 破 之
前 , 在 钻 机 凿 岩 过 程 中 , 其 岩 粉 借 助 高 风 压 的 压 力 堆
积 在 孔 口 周 围 8] , 取 样 人 员 可 从 其 中 抓 取 部 分 岩 粉
到 取 样 袋 中 , 然 后 标 记 编 号 等 信 息 送 往 检 验 科 检 验 。
炮 孔 取 样 具 体 数 据 包 括 炮 孔 编 号 、 炮 孔 坐 标 、 炮 孔 样
品 品 位 , 以 TXT 文 件 存 储 。
[
(
5) 裁 剪 。 假 如 有 线 段 是 穿 过 外 围 境 界 线 的 ,
用 境 界 线 裁 剪 掉 。 有 的 线 段 是 完 全 在 境 界 线 外 面
的 , 则 根 据 条 件 找 到 这 些 线 段 , 然 后 删 除 掉 。 这 样 就
生 成 了 包 括 外 围 境 界 线 的 Voronoi 图 。
2
ꢀ 程 序 实 现
根 据 Voronoi 图 定 义 可 知 , 利 用 炮 孔 取 样 点 数
据 绘 制 Voronoi 图 , 可 以 直 观 而 有 效 地 显 示 每 个 点
的 爆 破 影 响 区 域 。 另 外 , 可 以 用 Voronoi 图 表 示 每
个 点 的 品 位 影 响 区 域 , 从 而 进 一 步 得 到 爆 破 区 域 的
品 位 分 布 图 。
2
. 1ꢀ 开 发 环 境
在 ObjectARX 2008 与 Visual Studio 2005 开 发
WWW. KY114. CN
环 境 下 , 利 用 C#对 AutoCAD 2008 进 行 二 次 开 发 实
现 Voronoi 图 。
2
. 1. 1ꢀ ObjectARX
得 到 炮 孔 取 样 点 数 据 后 , 程 序 分 3 步 完 成 具 体
功 能 。
ObjectARX 是 Autodesk 公 司 针 对 AutoCAD( 13. 0
或 以 上 版 本 ) 平 台 上 的 二 次 开 发 而 推 出 的 一 个 开 发 软
件 包 , 它 支 持 面 向 对 象 编 程 技 术 , 使 AutoCAD 开 发 从
形 式 到 内 容 发 生 了 根 本 变 化 。 ObjectARX 应 用 程 序
实 际 上 是 一 个 动 态 链 接 库 ( DLL) , 它 共 享 AutoCAD
的 地 址 空 间 并 直 接 调 用 AutoCAD 函 数 。 ObjectARX
编 程 环 境 提 供 了 一 个 面 向 对 象 的 编 程 接 口 , 用 户 可 以
通 过 这 个 接 口 来 使 用 、 优 化 和 扩 展 AutoCAD, 且 Ob
jectARX 库 包 含 了 各 种 工 具 , 用 户 可 以 利 用 这 些 工 具
来 使 用 AutoCAD 的 开 放 式 结 构 , 直 接 访 问 AutoCAD
2. 2. 1ꢀ 展 ꢀ 点
首 先 要 做 的 工 作 步 骤 是 将 以 TXT 文 件 存 储 的
点 数 据 展 绘 在 AutoCAD 中 。 文 件 中 每 一 行 为 1 个
炮 孔 点 的 相 关 数 据 , 根 据 炮 孔 数 据 存 储 的 格 式 以 空
格 或 逗 号 将 每 一 行 分 割 , 获 取 坐 标 、 高 程 、 品 位 等 信
息 。 通 过 坐 标 将 点 展 绘 到 AutoCAD 中 , 根 据 要 求 在
图 上 显 示 炮 孔 点 的 编 号 和 高 程 等 数 据 。
2. 2. 2ꢀ 绘 制 爆 破 区 域 境 界 线
根 据 爆 破 区 域 炮 孔 点 的 分 布 , 连 接 多 条 辅 助 线
生 成 外 围 轮 廓 线 , 将 外 围 轮 廓 线 按 照 一 定 的 距 离 向
外 围 平 移 , 将 轮 廓 线 中 有 尖 角 的 地 方 平 滑 。 然 后 结
合 展 点 时 候 得 到 的 坡 顶 线 , 绘 制 出 爆 破 区 域 境 界 线 。
将 以 上 两 步 得 到 的 图 存 储 起 来 , 作 为 生 成 Voronoi
图 的 源 图 。
[
6]
。
数 据 库 、 图 形 系 统 和 用 户 自 定 义 命 令
2
. 1. 2ꢀ 开 发 语 言
使 用 的 语 言 为 C#, C#是 可 用 于 创 建 要 运 行 在
NET CLR上 的 应 用 程 序 的 语 言 之 一 , 它 从 C / C + +
.
语 言 演 化 而 来 , 是 Microsoft 专 门 为 使 用 . NET 平 台
而 创 建 的 。 C#是 Microsoft 在 推 出 . NET Framework
第 一 版 时 提 供 的 语 言 , 自 从 问 世 以 来 , 得 到 了 广 泛 应
用 , 成 为 目 前 使 用 . NET 的 Windows 和 Web 开 发 人
2. 2. 3ꢀ 生 成 Voronoi 图
在 编 写 过 程 中 , 创 建 对 应 于 点 、 三 角 形 、 三 角 形
的 外 接 圆 圆 心 、 多 边 形 等 图 形 的 结 构 。 其 中 点 结 构
1
07
总 第 512 期 ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ 现 代 矿 业 ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ ꢀ 2011 年 12 月 第 12 期
中 定 义 了 坐 标 等 属 性 ; 三 角 形 结 构 中 定 义 了 3 个 整
数 型 变 量 用 于 存 放 3 个 顶 点 的 坐 标 索 引 , 三 角 形 的
坐 标 索 引 应 与 存 储 点 的 结 构 数 组 中 的 索 引 一 致 ; 外
接 圆 圆 心 结 构 定 义 了 坐 标 、 连 接 次 数 等 属 性 , 在 实 际
操 作 过 程 中 圆 心 的 数 组 索 引 应 和 其 对 应 的 三 角 形 数
组 的 索 引 一 致 ; 多 边 形 的 结 构 中 定 义 了 多 边 形 的 索
引 变 量 、 顶 点 数 组 等 , 其 中 索 引 变 量 的 值 为 此 多 边 形
所 包 含 的 离 散 点 的 索 引 , 顶 点 数 组 存 放 每 个 多 边 形
的 顶 点 与 外 接 圆 圆 心 相 吻 合 。 以 上 4 种 图 形 结 构 联
系 图 见 图 1。
图 2ꢀ Voronoi 效 果 图
影 响 区 域 , 并 得 到 爆 破 区 域 品 位 。 Voronoi 图 在 算 法
上 不 难 实 现 , 但 应 当 注 意 在 编 程 的 时 候 , 由 于 要 构 建
点 、 线 、 多 边 形 等 诸 多 图 形 结 构 , 应 当 遵 循 结 构 简 单 、
逻 辑 清 晰 等 原 则 。 另 外 应 当 注 意 , 使 用 Object
ARX2008 对 AutoCAD2008 进 行 二 次 开 发 时 有 时 会
出 现 错 误 , 希 望 以 后 的 版 本 中 能 有 所 改 进 。
参 ꢀ 考 ꢀ 文 ꢀ 献
[
1] ꢀ 宗 大 伟 . Voronoi 图 及 其 应 用 研 究 [ D] . 南 京 : 南 京 航 空 航 天 大
学 , 2006: 15.
图 1ꢀ 4 种 图 形 结 构 联 系
程 序 生 成 Voronoi 图 的 具 体 过 程 如 下 , 首 先 读
取 源 图 上 的 所 有 实 体 , 将 离 散 点 存 储 在 实 例 化 的 点
结 构 数 组 中 , 将 爆 破 区 域 境 界 线 以 多 段 线 要 素 存 储 ,
然 后 对 点 数 据 进 行 三 角 剖 分 , 求 出 每 个 三 角 形 的 外
接 圆 圆 心 。 对 于 凸 壳 内 的 点 , 通 过 一 系 列 的 条 件 判
断 后 , 依 次 连 接 围 绕 离 散 点 的 相 邻 三 角 形 的 圆 心 。
[ 2] ꢀ 李 淑 艳 , 曹 ꢀ 菡 , 刘 妮 玲 , 等 . Voronoi 图 的 并 行 生 成 算 法 研 究
[
J] . 郑 州 轻 工 业 学 院 学 报 : 2010, 25( 1) : 105109.
[
3] ꢀ 陈 ꢀ 军 . Voronoi 动 态 空 间 数 据 模 型 [ M] . 北 京 : 测 绘 出 版 社 ,
2
002.
[
4] ꢀ 汤 国 安 , 李 发 源 , 刘 学 军 , 等 . 数 字 高 程 模 型 教 程 [ M] . 北 京 :
科 学 出 版 社 , 2010.
WWW. KY1[ 5] ꢀ
1
茆 德 柱
4
. TIN
.
模 型 的
C
构 建 方
N
法 研 究 [ D] . 南 京 : 河 海 大 学 ,
对 于 含 三 角 网 边 界 的 三 角 形 的 外 接 圆 圆 心 , 进 行 特
2007.
殊 处 理 , 即 绘 制 一 个 垂 直 于 对 应 边 界 的 线 段 , 要 求 此
线 段 应 足 够 长 , 以 满 足 伸 出 爆 破 区 域 境 界 线 。 最 后
将 所 有 在 境 界 线 以 外 的 图 形 裁 剪 或 删 除 。 某 爆 区 的
Voronoi 效 果 图 见 图 2。
[ 6] ꢀ 刘 越 岩 , 岳 海 斌 , 林 爱 文 , 等 . 基 于 ObjectARX 的 土 地 整 理 规 划
属 性 数 据 库 系 统 设 计 与 实 现 [ J] . 测 绘 通 报 , 2006( 1) : 5557.
[
7] ꢀ Karli Watson, Christian Nagel, 等 . C#入 门 经 典 [ M] . 齐 立 波 ,
译 . 北 京 : 清 华 大 学 出 版 社 , 2006.
[
8] ꢀ 蒋 志 民 . 露 天 采 场 炮 孔 取 样 与 应 用 [ J] . 有 色 金 属 : 1979( 3) :
3
ꢀ 结 ꢀ 语
3
335.
Voronoi爆 破 图 可 以 直 观 地 显 示 各 个 点 的 爆 破
(
收 稿 日 期 20110923)
櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄櫄
·
记 者 在 线 ·
湘 西 — 鄂 西 成 矿 带 发 现 新 含 矿 地 层 铜 锌 矿 体
ꢀ
ꢀ 近 日 , 武 汉 地 调 中 心 《 湖 北 天 宝 — 陕 西 鱼 肚 河
大 于 2 000 m; 在 湖 北 省 十 堰 市 竹 溪 县 望 鱼 河 地 区 发
现 锌 铜 多 金 属 矿 化 体 3 个 、 银 矿 化 体 1 个 。 特 别 值
得 一 提 的 是 , 项 目 组 通 过 路 线 穿 越 、 剖 面 测 量 , 填 制
出 十 八 里 长 峡 — 刘 享 寨 铅 锌 银 成 矿 远 景 区 矿 产 地 质
图 300 km2 , 厘 清 了 测 区 地 层 分 布 范 围 、 分 布 特 征 以
及 构 造 发 育 情 况 。 通 过 剖 面 测 制 对 比 , 项 目 组 明 确
了 十 八 里 长 峡 锌 矿 体 赋 矿 层 位 为 寒 武 系 石 龙 洞 组 厚
层 灰 质 云 岩 , 为 该 地 区 新 的 含 矿 地 层 。
地 区 铅 锌 多 金 属 矿 远 景 评 价 》 项 目 组 发 现 新 的 含 矿
地 层 , 即 十 八 里 长 峡 锌 矿 体 赋 矿 层 位 ——— 寒 武 系 石
龙 洞 组 厚 层 灰 质 云 岩 。
据 了 解 , 该 项 目 隶 属 《 湘 西 — 鄂 西 成 矿 带 地 质
矿 产 调 查 》 计 划 项 目 , 工 作 年 限 2011 年 — 2013 年 。
2
011 年 项 目 开 展 以 来 , 在 陕 西 省 安 康 市 镇 坪 县 险 自
城 地 区 发 现 2 条 厚 1. 15 m、 0. 9 m 的 铜 锌 矿 体 , 延 长
1
08
/pdf/swf/201202/2012_0207_033659_760.swf