采空区体积三角网模型剖面的微积分算法

第36卷第9期 北京科技大学学报 Vol.36 No.9 2014年9月 Journal of University of Science and Technology Beijing Sep.2014 采空区体积三角网模型剖面的微积分算法 罗周全)8，张文芬”，鹿浩”，许士民2) 1)中南大学资源与安全工程学院，长沙4100832)中国矿业大学（北京）资源与安全工程学院，北京100083 ☒通信作者，E-mail:zg505@csu.ed.com 摘要为了准确获取采空区空间体积，以采空区三维激光扫描系统探测到的原始数据为依据，提出采空区体积的三角网模 型微积分算法.算法首先确定模型剖切的主轴方向，用一组等间距平行面对模型进行相切并获得剖面的无序点集，运用所提 出的凸包压人法生成采空区剖面的初始边缘轮廓线：再将初始边缘轮廓线内的其他交点添加到剖面中，形成完整的采空区剖 面形态：最后利用平面三角形有向面积叠加计算剖面面积，将剖面面积与微小间距进行积分获取采空区的体积.工程应用表 明，所研究的采空区体积算法稳定性好，精度高，可实现对复杂采空区体积的有效计算 关键词采空区：体积；算法；三维模型：网格生成：三角形 分类号TD76 Calculus algorithm of triangular mesh model profiles for cavity volume LUO Zhou-quan,ZHANG Wen-fen,LU Hao),XU Shi-min2) 1)School of Resources and Safety Engineering,Central South University,Changsha 410083,China 2)School of Resources&Safety Engineering,China University of Mining&Technology (Beijing),Beijing 100083,China Corresponding author,E-mail:zq505@csu.edu.com ABSTRACT To obtain the cavity volume accurately,a calculus algorithm of cavity volume was researched according to data surveyed with a three-dimensional laser scanning system.In the algorithm,the main sectioning axis is fixed first,the model is cut by a group of equally interval parallel planes,and the intersection points are got,so the initial edge contour line is generated by using a convex hull impressed method.Then other intersections within the initial edge contour line are added to the cross-section to form a complete cross- section shape.Finally the volume of the model is got by superposition of the triangular directed area.Experimental results show that the algorithm program is stable and has a higher accuracy,and can be used as an effective algorithm of cavity volume. KEY WORDS cavity;volume;algorithms;three-dimensional models;mesh generation;triangle 金属和非金属地下矿山开采形成的采空区是矿 而导致计算的体积偏大.文献[5]提出了用正二十 山重要灾源之一，如何准确获取采空区的体积是矿 面体对模型形状进行描述，提取出剖面图求得模型 山空区充填及其灾变监控的重要基础性工作，也是 体积；该方法速度较慢而且模型数据处理量大.文 矿山实施空区周边资源以及残矿安全回采的重要基 献[6]通过指定三角形的投影平面，计算每个三角 础性依据之一「1-3) 面片及其在投影平面上的投影三角形所构成的凸五 目前，关于三角网模型体积的求取国内外学者 面体的有向体积，求出所有凸五面体有向体积的代 做了相关研究.文献[4]提出了在三角网模型内找 数和即为模型的体积；这类方法以每个三角形法向 一点与所有的三角形进行连线构成四面体，所有四 量指向都完全正确为前提，而实际由于采空区形态 面体有向面积的代数和即为三角网模型的体积；该 复杂，构建的三角网模型的三角形法向量方向并不 算法虽然简单方便，但由于空间四面体存在重叠从 一定完全准确，所以利用该算法对采空区进行体积 收稿日期：2014-01-14 基金项目：“十二五"国家科技支撑计划专题资助项目(2012BAk09B02-05);中央高校基本科研业务费专项资金资助项目(2013zs061) DOI:10.13374/j.issn1001-053x.2014.09.003;http://joumals.ustb.edu.cn

第 卷 第 期 北 京 科 技 大 学 学 报 年 月 采 空 区 体 积 三 角 网 模型 剖 面 的 微积 分算 法 罗 周 全 ， 张文芬 ， 鹿 浩“ ， 许士 民 中 南 大学资源 与安 全工程学 院 ， 长沙 中 国 矿业大学 （ 北京 ） 资 源与 安全工程学 院 ， 北京 通信作 者 ， 摘 要 为 了 准确 获取采空 区 空 间 体积 ， 以 采 空 区 三维激光扫 描 系 统探测 到 的 原始数据 为 依据 提 出 采 空 区体积 的 三 角 网 模 型微积分算法 算法首先确定模型剖切 的 主轴方 向 用一 组等 间 距平行面对模型进行相切 并获得剖 面 的 无序点 集 运 用 所 提 出 的 凸 包压人法生成采空 区剖 面 的初始边缘轮廓线 ； 再将初始边缘轮廓线 内 的 其他交点 添加 到 剖 面 中 ， 形 成完 整 的 采 空 区 剖 面形 态 ； 最后利用平面三角 形有 向 面积叠加计算剖 面 面积 ， 将剖 面 面积与微小 间 距进行积分获 取采 空 区 的 体积 工程应用 表 明 ， 所研究 的 采空 区体积算法稳定性好 精度高 ， 可实现对复杂采空 区体积的 有效计算 关键词 采空 区 ； 体积 ； 算法 ； 三维模型 ； 网 格生成 ； 三角 形 分类 号 ， ， ， ， ： ， ； ； ； ； ； 金属 和非金属 地下矿 山 开采形成的 采空 区是矿 而导致计算 的体积偏 大 文献 提 出 了 用 正 二十 山 重要灾源之一 如 何 准确 获取采空 区 的 体积是矿 面体对模型形状进行描述 提取 出 剖 面 图 求 得模型 山 空 区充填及其灾 变监控 的 重要基础性工作 ， 也是 体积 该方法速 度 较慢 而 且模型 数据处理量大 文 矿 山 实施空 区周边资源 以 及残矿安全 回 采 的重要基 献 通过指 定 三 角 形 的 投影平 面 ， 计算 每 个 三 角 础性依据之一 面片及其在投影平面上 的 投影三角 形所构成的 凸 五 目 前 ， 关于三角 网 模 型 体积 的 求 取 国 内 外学者 面体 的有 向 体积 ， 求 出 所有 凸 五 面体有 向 体积 的 代 做了 相关研究 文献 提 出 了 在三 角 网 模 型 内 找 数和 即 为模型 的 体积 这类方法 以 每个三 角 形 法 向 一 点与所有 的 三角 形 进行连线 构 成 四 面体 所有 四 量指 向 都完全正确 为前提 而实 际 由 于采空 区 形 态 面体有 向 面积的代 数和 即 为 三 角 网 模型 的 体积 ； 该 复杂 构建的三角 网模 型 的 三角 形 法 向 量方 向 并不 算法虽然简单方便 但 由 于空 间 四 面体存在重叠从 一 定完全准确 所 以 利 用 该算法对采空 区 进行体积 收稿 日 期 ： 基金项 目 ： “ 十二五 ” 国 家科技 支撑计划 专 题资助项 目 （ ； 中 央 高 校基本科研业务费 专项 资金 资助项 目 （ ； ：

·1144· 北京科技大学学报 第36卷 运算存在误差 确定剖切主轴方向 为实现采空区体积准确计算，本文研究了基于 采空区三角网模型剖面微积分的体积算法.采空区 确定割切平行面之间的间距 三角网模型是利用自主研发的采空区激光探测三维 建模可视化集成系统生成的，如图1所示 遍历所有的三角形 ↓ 销中安大学区大三建可见化安喜候一回区。 判断三角形与 否 剖切平面是否相交？ 日图2國可？ ∠灯次zc-田围☑☑g回M/ 是 求取剖切平面与三角形的交点 将所有的交点进行排序 求三维模型的体积 图2算法基本流程图 62空区 Fig.2 Basic flowchart of the algorithm 图1采空区三角网模型 首先对激光探测到的采空区边界数据进行比 Fig.1 Triangular mesh model of a cavity 较，求出所有数据中z坐标的最大值和最小值.根 据工程的精度要求确定剖切平面之间的间距，确定 1算法设计 每个剖切面的位置.以z=:(i为1,2，…，n的任意 1.1思路 一个剖面)的剖切面说明其交点获取的方法.三角 采空区体积三角网模型剖面微积分算法思路如 形△P,P2P,与剖切面存在交点的位置关系总共有三 下：(1)利用等间距的垂直于任意坐标轴的平面集 种情况，如图3所示：(1)三角形的一条边位于剖切 与三角网模型相切，获得平面与三角形的交点，构成 面上，有两个交点，见图3(a);(2)三角形与剖切面 剖面轮廓线无序点集：(2)对构成剖面轮廓线的无 相交，有两个交点，见图3(b):(3)三角形的一个顶 序点集运用凸包压人法生成闭合的剖面轮廓线； 点位于剖切面上，有一个交点，见图3(c). (3)利用三角形有向面积的叠加计算剖面的面积； (4)参照微积分的思想，将剖面面积和剖面间距进 剖面线 行微积分从而计算出模型的体积 算法的基本流程如图2所示，算法需要解决的 (a 关键问题如下：(1)判断三角网模型中三角形与剖 切平面的相切关系，并获得交点；(2)如何将剖面轮 图3剖面与三角形的位置关系 廓线无序点集运用凸包压人法生成闭合的剖面轮廓 Fig.3 Positional relationships between the triangle and profile 线；(3)如何求剖面的面积，并利用微积分思想求出 图中对于图3(a)和(c)两种情况求交点时，只 采空区体积 需要判断三角形顶点坐标的z值是否与z,相等，如 1.2剖面线散乱点集提取 果相等则说明顶点为交点；对于图3(b)情况，线段 大量的三角形用来对三维模型进行离散逼近， P1P2与平面交点为a1,a,相对于p1和p2的位置比例 这类模型的网格面在三维空间中围成了一个体积有 关系t为 限的区域[68].本文所剖切的三角网模型就是指这 类网格模型，并且满足以下两个条件：网格上的每个 =之名 (1) m-,’ 面片都是三角形：网格上的每条边有且仅有两个三 则a,的坐标值为 角形所共有. [xa1=xp1+t(xp2-x）, 对三角网模型剖切时，借用微分单元法求和的 ya1=ym+t(y2-yn）, (2) 思想，将生成的三角网模型划分为多个子域（单 元)，并用微分求和原理进行分析求解.现以垂直于 2a,=21+t(zp2-zpn）. z轴方向的剖切平面集进行说明. 同理可求出线段pP3与剖切面交点a2的坐标

北 京 科 技 大 学 学 报 第 卷 运算存在误差 确 定剖切 主轴方 向 为 实 现采 空 区 体 积准 确 计算 本 文研究 了 基 于 采空 区三角 网 模型剖 面微积分的 体积算法 采 空 区 确 定剖切平 面之 间 的 间距 三 角 网 模 型 是利用 自 主研发 的采空 区激光探测 三维 一 建模可视化集成系 统生成 的 如 图 所示 遍 历 所 的三 角 形 — □ 田 □ 圍 求 取剖 切平；与 三 角 形 的交点 将所有 的交点进行排序 求 三维 型 的体积 图 算法基本 流 程 图 始 — 土 首 先 对 激 光探测 到 的 采 空 区 边 界 数据 进 行 比 ‘ 较 ， 求 出 所有 数据 中 坐 标 的 最 大 值 和 最 小 值 根 据工程 的 精度要 求 确 定 剖 切 平 面 之 间 的 间 距 ， 确 定 算 ；去 又 计 每个剖切面 的 位 置 以 、 （ 纟 为 ， … … 的 任 意 思 路 一 个剖 面 ） 的 剖 切 面 说 明 其交点 获 取 的 方法 三 角 采 空 区 体积三角 网 模 型剖 面微积分算法思路如 形 与 剖切 面存 在 交点 的 位 置关 系 总 共有 三 下 ： （ 利 用 等 间 距 的 垂 直 于 任 意 坐 标 轴 的 平 面 集 种情况 如 图 所示 ： （ 三 角 形 的 一 条边 位 于 剖 切 与 三角 网 模 型 相 切 ， 获得平面 与 三角 形 的 交点 ， 构 成 面上 有 两 个交点 ， 见 图 ； 三 角 形 与 剖 切 面 剖 面 轮廓线 无序 点 集 ； （ 对 构 成 剖 面 轮 廓 线 的 无 相交 有 两个交点 ， 见 图 ； 三 角 形 的 一 个顶 序 点 集 运 用 凸 包 压 人 法 生 成 闭 合 的 剖 面 轮 廓 线 ； 点 位 于剖切 面上 有一 个交点 见 图 利 用 三 角 形 有 向 面 积 的 叠 加 计算 剖 面 的 面 积 ； 参照 微 积 分 的 思 想 ， 将 剖 面面 积 和 剖 面 间 距 进 … 剖 面线 行微积分从而计算 出 模 型 的 体积 算 法 的 基本 流程 如 图 所示 算 法需要 解 决 的 关键问 题如 下 ： （ 判 断 三 角 网 模 型 中 三 角 形 与 剖 切平面 的 相切关系 ， 并获得交点 ； （ 如 何将剖 面 轮 廓线无序点集运 用 凸 包压入法生成闭 合的 剖 面轮廓 ‘ ° § ° 线 ； （ 如 何求剖 面 的 面 积 并 利 用 微 积分思 想求 出 图 中 对于图 和 （ 两 种 情 况求 交点 时 ， 只 采空 区 体积 需要判 断三 角 形 顶 点 坐标 的 值 是 否 与 相 等 ， 如 剖 面线 散乱点 集提 取 果相 等则 说 明 顶点 为 交 点 ； 对 于 图 情 况 ， 线 段 大量 的 三角 形 用 来 对三维模 型 进行离 散 逼 近 ， 与 平 面交点 为 … ， … 相 对 于 仏 和 卩 的 位 置 比 例 这类模 型 的 网 格 面在三维空 间 中 围 成 了 一 个体积有 关系 为 限 的 区 域 — 本文所剖 切 的 三 角 网 模 型 就 是 指 这 么 、 类 网 格模 型 并且 满 足 以 下 两个条件 ： 网 格上 的 每个 面 片 都是二 角 形 ； 网 格 上 的 每 条边 有 且仅有 两 个 二 则 … 的 坐标值为 角 形所共有 （ 、 ） ， 对三 角 网 模 型 剖 切 时 ’ 借用 微分单元法求 和 的 思想 ， 将 生 成 的 三 角 网 模 型 划 分 为 多 个 子 域 （ 单 ‘ ‘ 元 ） ， 并用 微分求 和 原理进行分析求解 现 以 垂 直 于 轴 方 向 的 剖切平 面集进行说明 同 理可求 出 线段 与 剖 切 面交点 的 坐标

第9期 罗周全等：采空区体积三角网模型剖面的微积分算法 .1145· 求出剖切面与三角网模型的所有交点依次标记为 初始边缘轮廓线的第三个点b3; {a1,a2,…,a}并将该点集记为A,作为生成剖面轮 (4)b代替b,b3代替b2,在其余m-3个点中， 廓线的点集 重复(3)，寻找下一个生成初始边缘轮廓线的点； 用上述方法求剖切面与三角网模型的交点是以 (5)当b与b,重合时，停止，即生成边缘轮廓 三角形为判断单元，而生成三角网模型的每个相邻 线，如图5中红线为将所有的交点包络在内的初始 的三角形都会共用一条边，从而导致求剖切面与三 边缘轮廓线. 角形三条边的交点时，除最开始相交和最后相交的 几个三角形与平面的交点只需要求一次外，其他的 交点都要求两次，使得求得的交点中存在大量重复 点.虽然重复点对于求三角网模型的体积没有影 响，但是对于算法的运行速度影响较大.因此需要 通过判断两点之间的坐标是否相等来删除重复点， 图5z=1剖面外的初始边缘轮廓线 并将去除重复点后的交点重新保存到点集A={a, Fig.5 Contour line of the outer boundary at the point of z=z a2,…,am}中.以某采空区为例，在z:=-759.390m 处的剖切面上，删除重复点之前的交点个数为254， 在初始边缘轮廓线的基础上，要想将所有的交 删除重复点之后的交点个数为130. 点都添加到轮廓线中，有两个不确定性：一是交点是 随机分布的具有不确定性；二是完整剖面轮廓线形 1.3 剖面轮廓线生成 点集A={a1,a2,…,an}中的交点是按照剖切 状具有不确定性，包括交点和轮廓线的位置关系 针对以上两个不确定性，运用最大张角准则的原理， 面与三角网模型的相交顺序进行排序的.图4为按 将初始边缘轮廓线内的其他交点依次加入到相应的 照交点的相交颠序依次连线形成的剖面图（以？=z1 边界轮廓线中，其原理如下（见图6）. 处的剖面为例).因此需要将交点进行排序后再连 成剖面轮廓线. 图4无序点集连成的剖面图 Fig.4 Profile of a set of unorganized points 图6最大张角准则的原理 Fig.6 Principle of the maximum angle 对于剖面轮廓线上交点的排序方法有紧邻排序 法[]和扇形区域法[o],这两种排序方法对于表面变 (1)找出与b和b,1形成的夹角最大的点，在 化比较平缓的模型较实用：但是应用于边界复杂的 图6中为a1点，并将b,和b1两点连成的线段记 采空区时，得到的剖面轮廓线会失真.基于传统方 为L. 法的缺陷，运用凸包算法13-6]的思想提出：凸包压 (2)判断∠b,a+1b+1是否为钝角，这是因为当 人法生成初始边缘轮廓线，再运用最大张角准则将 点添加到正确的初始边缘轮廓线段时，交点与b,和 包络于初始边缘轮廓线内的其他交点添加到剖面线 b,+:两点形成的夹角为钝角，否则应将交点添加到 中.具体步骤如下： 其他的初始边缘轮廓线段中；用夹角的余弦值进行 (1)找出点集A={a1,a2,…,an}中m个数据 判断交点是否满足条件，这是因为余弦值在[0°， 的横坐标最小的点记为6，并作为生成边缘轮廓线 180°]为单调递减函数，余弦值取得最小值的点即为 的第一个点； 夹角最大的点，并且当余弦值为负值时，该夹角为钝 (2)对于其余的m-1个点，计算与b,连线与 角.这样就可以判断点a+:是否满足条件，是否应 水平方向夹角的余弦值，取出余弦值最小的点，作为 该加入到线段L中. 生成初始边缘轮廓线的第二个点，记为b2: (3)若a+1点满足第二个条件则将点a+1加人 (3)对于点集A中其余的m-2个点a,可构 到b,和b+1两点之间，再判断b和a+1两点之间是否 成三角形b,b2a,找出∠b,b2a,最大的点a,作为生成 有满足条件的其他交点，并按照(1)和(2)进行

第 期 罗 周 全等 ： 采 空 区 体 积 三 角 网 模 型 剖 面 的 微积 分 算 法 求 出 剖切 面 与 三 角 网 模 型 的 所有 交点 依 次 标 记 为 初始边缘 轮廓线 的 第三个点 ； ， … ， 并将该点集记为 ， 作 为生 成剖 面 轮 （ 代替 代替 ， 在其余 个点 中 ， 廓线 的 点集 重复 ， 寻找下一 个生成初始边缘轮廓线 的 点 ； 用 上述方法求剖切 面 与 三角 网 模型 的 交点 是 以 （ 当 、 与 重 合 时 停 止 ， 即 生 成边 缘 轮廓 三角 形 为判 断单元 ， 而 生 成 三 角 网 模 型 的 每 个相 邻 线 如 图 中 红线 为 将 所 有 的 交 点 包络 在 内 的 初 始 的 三角 形都会共用 一 条边 ， 从而 导 致求 剖 切 面 与 三 边缘轮廓 线 角 形 三条边 的 交点 时 除 最 开 始 相 交 和 最后 相 交 的 几个三角 形 与 平 面 的 交 点 只 需要求 次外 ， 其他 交点都要賴次 ， 使 得求 動奴巾 存 找 点 虽然重 复 点 对 于 求 三 角 随型 的 体 积 没 有 影 响 ， 但是对于算 法 的 运 行速 度 影 响 较 大 因 此需 要 嘱 通过判 断两点 之 间 的 坐 标 是 否 相 等 来 删 除 重 复 点 ， 图 剖 面外 的初 始边缘轮 廓 线 并将去 除重 复 点 后 的 父点 重新保存 到 点集 ， … ， 丨 中 以 某采空 区 为例 ， 在 处 的 剖切 面上 ， 删 除重复 点 之前 的 交点 个数 为 ’ 土 的 ， 础 上 土想 将 白 應 丨 论舌 有 占 的 六 占 点 都添加 到 轮廓线 中 ， 有 两 个不确 定性 ： 一 是父点 是 线 生 随机分細具有 不 确 定 性 ； 二 是 完 整 剖 面 轮 廓 线 形 占 集 丨 中 的 交 占 是 按 昭 剖 切 状具有 不 确 疋 性 ， 包 括 父 点 和 轮 线 的 位 置 关 系 … 二 二二： 卄 、 、 、 针对 以 上两个不确 定性 ， 运用 最大 张 角 准 则 的 原理 ， 将初 始边缘轮廓线 内 的其他交点依次加 人 到 相 应 的 …、 父 ‘ 、 的 相 序 依 线形 邮 酣丨 （ 、 边 界轮廓线 中 其原應卩 下 （ 见 图 处 的 剖 面 为 例 ） 因 此需 要 将交 点 进 行 排 序 后 再 连 應 图 无序 点 集连 成 的剖 面 图 图 最 大张 角 准 则 的 原理 对于剖 面轮 廓线 上 交点 的排序方法有 紧 邻排序 法 和 扇 形 区 域法 ， 这 两种 排序方法对 于表 面 变 （ 丨 ） 找 出 与 和 形 成 的 夹 角 最 大 的 点 ， 在 化 比 较平缓 的 模 型 较 实 用 ； 但是 应用 于边 界 复 杂 的 图 中 为 力 点 ， 并 将 和 两 点 连 成 的 线 段 记 采空 区 时 ， 得到 的 剖 面 轮 廓 线 会 失 真 基 于 传 统 方 力 法 的 缺 陷 ， 运 用 凸 包 算 法 的 思 想 提 出 ： 凸 包 压 （ 判 断 乙 是否 为 钝 角 ， 这是 因 为 当 人法生成初 始边 缘 轮 廓 线 ， 再运 用 最 大 张 角 准 则 将 点 添加 到 正 确 的 初 始 边 缘 轮廓 线 段 时 ， 交点 与 和 包络 于初 始边缘轮廓线 内 的 其他交点 添加 到 剖 面线 两点 形 成 的 夹 角 为 钝 角 ， 否 则 应 将 交点 添 加 到 中 具体步骤 如 下 ： 其他 的 初 始边缘 轮廓 线 段 中 ； 用 夹 角 的 余弦 值进行 找 出 点 集 ， … ， 中 个 数 据 判 断交 点 是 否 满 足 条 件 ， 这 是 因 为 余 弦 值 在 ° 的 横坐标最小 的 点 记 为 、 ， 并 作 为 生 成边 缘 轮 廓 线 ° 为单调 递减 函 数 ， 余弦值取得最小值的 点 即 为 的 第一 个点 ； 夹 角 最大 的 点 并且 当 余弦值为负 值时 该夹角 为钝 对于 其余 的 个点 ， 计算 与 … 连 线 与 角 这 样就可 以 判 断 点 是 否 满 足 条 件 ， 是 否 应 水平方 向 夹角 的余弦值 取 出 余弦值最小 的 点 作 为 该加 入到 线段 中 生 成初 始边缘轮廓线 的第 二个点 ， 记为 若 点 满 足第 二个 条件 则 将 点 加 人 对 于 点 集 中 其余 的 个 点 ， 可 构 到 和 两点之间 再判 断 和 两点 之 间 是否 成三角 形 仏 ， 找 出 … 最 大 的 点 作 为 生 成 有满 足 条 件 的 其 他 交 点 ， 并 按 照 （ 和 （ 进 行

·1146· 北京科技大学学报 第36卷 判断. 面中的一点，与剖面轮廓线中的紧邻两点进行连线 依次判断，将所有的交点都添加到轮廓线中，将 构成三角形，所有三角形面积的叠加即为剖面的面 连线生成剖面图运用CAD输出.图7为z=乙，剖面 积1.该方法虽然简单快捷，但是由于采空区边界 处将所有的交点添加到图6的初始边缘轮廓线后， 复杂使得该方法求出的面积与实际相差较大.本文 生成的完整剖面轮廓线. 从剖面轮廓线外找一点，并与剖面线上排好顺序的 紧邻两点进行连线构成三角形.按照向量叉乘，求 出三角形的有向面积，将所有三角形的有向面积进 行叠加即可得到该剖面的面积. 三角形有向面积的原理0)：对于任意的一个剖 面，把生成剖面轮廓线的紧邻两点b和b+1,以及剖 图7：=名处的完整腳面线 面外任意一点b构成三角形.按照b、b和b1顺 Fig.7 Complete profile at the point of 序，若三点满足右手法则，三角形的法向量指向平面 需要注意的是，采空区的形状不规则并且边界 外则三角形的面积为正值：反之，求出的三角形的面 具有较大的凸起，对三角网模型进行剖切时会出现 积为负值 图8所示的情况：存在两个凸起在同一个剖切面上， 如图9，设z=:剖面的上2个紧邻的交点， 从而造成剖面连接在一起 b,(,y）、b+（x+4y+)以及剖面外一点b(x,y）. 图9三角形的有向面积 的削面 Fig.9 Directed area of a triangle 求出品、品，两边的向量N,和V,: (N1=bb=(x-x）,(（y-y), N2=成，1=(x-x1),（y-y) (3) 按照两向量的叉乘求出三角形的法向量N,的z坐 图8三角网模型的两个凸起在同一个剖切面上 Fig.8 Two humps of the border region on the same profiles of the tri- 标zN angular mesh model EN=NI X N2 =%NYNa +yNNa= 因此需要将两个区域分开形成独立的剖面区 (x-x)(y-y1)+(x-x)(y-y).(4) 域以便减少体积误差.需要将剖面划分为两个独立 则三角形的面积S,为： 区域的剖面交点满足以下条件： S,=0.5zy (5) (1)散乱点集A={a1,a2,…,am}中存在a、 当计算到剖面交点的最后一点时，应按照最后一点 a4、a+1、ag1四个点，使得a,与a+1,a与a+1连线的 b。、三角形外部一点b、第一个点b,的顺序求出三角 距离要远大于其他相邻两交点之间距离，即L1,L,的 形的面积.所有三角形有向面积的叠加就是该剖面 要远大于其他相邻两交点之间距离； 的面积.因此z=z剖面的面积S为 (2)a与ak,a+1与ak+1连线的距离远小于a,与 a+1,a与ag+1连线的距离，即L,L,要远小于L1,L2; S,= (6) (3)a与a4,a+1与ak+1之间都存在其他的交 用该剖面的面积乘以平行平面的间距得到的是 点，且交点数大于3； 两个平行平面之间的三角模型的体积.将所有的体 满足以上三个条件的剖面交，点需要将该剖面上 积进行加和就可得到三角网模型的体积.由于采空 的点划分到两个点集中，分别对各个封闭剖面区域 区的整体形状是不规则的，因此紧邻两个剖面的面 求面积 积会有差别.为了进一步减小误差需要求取上下两 1.4三角网模型体积微积分计算 剖面面积的平均值，用紧邻两剖面的均值面积乘以 基于四面体求取三角网模型体积是按照求出剖 两平行平面之间的间距求取体积，则三角网模型的

北 京 科 技 大 学 学 报 第 卷 判 断 面 中 的 一 点 ， 与 剖 面 轮廓 线 中 的 紧 邻 两点 进 行连 线 依次判 断 ， 将所有 的 交点都添加 到 轮廓线 中 ， 将 构 成三角 形 ， 所有 三 角 形 面 积 的 叠 加 即 为 剖 面 的 面 连线生成剖 面 图 运 用 输 出 图 为 剖 面 积 ° 该方法虽然 简 单快捷 但 是 由 于 采 空 区 边 界 处将所有 的 交点 添加 到 图 的 初 始 边 缘 轮 廓 线 后 ， 复杂使得该方法求 出 的 面积 与 实 际相 差较 大 本 文 生成 的 完 整 剖 面轮廓线 从剖 面轮廓 线外 找 一 点 并 与 剖 面线 上 排 好顺序 的 紧 邻 两点 进行 连 线 构 成 三 角 形 按 照 向 量 叉 乘 ， 求 出 三 角 形 的有 向 面 积 ， 将 所 有 三 角 形 的 有 向 面 积进 行叠 加 即 可得 到该剖 面 的 面积 三角 形有 向 面积 的 原理 … 对 于任 意 的 一 个剖 面 把生成剖 面轮廓线 的 紧 邻 两 点 和 … 以 及 剖 图 、 处 的 完 整 剖 面线 面外 任 意 一 点 构 成 三 角 形 按 照 … 和 页 序 若三点 满 足 右手法 则 ， 三角 形 的 法 向 量指 向 平 面 需 要 注 意 的 是 ， 采 空 区 的 形 状不 规则 并且边 界 外 则 三角 形 的 面 积为 正值 ； 反 之 ， 求 出 的 三角 形 的 面 具有较大 的 凸 起 对 三 角 网 模 型 进 行剖 切 时会 出 现 积 为 负 值 图 所示 的情况 存在两 个 凸 起在 同 一 个剖 切 面上 ， 如 图 ， 设 七 剖 面 的 上 个 紧 邻 的 交 点 ， 从而造成剖 面连接在一 起 、 … ） “ 以 及剖 面外一 点 、 图 三 觸贿向 面积 的剖 面 求 出 两边 的 向 量 和 一 广 丨 广 ’ ⑶ 广 、 “ 图 三角 随型 的 两 个 凸 起在 同 个剖侧 ： 照两 向 量 的 叉 乘求 出 二角 形 的 法 向 里 乂 的 坐 丰不 ’ 二 因 此需要将 两 个 区 域 分开 形成 独 立 的 剖 面 区 一 （ ， “ 域 以 便减少体积误差 需要将剖 面划 分为 两个独 立 则 三 角 形 的 面积 为 ： 区 域 的剖 面交点 满 足 以 下 条件 ： 散 乱 占 集 丨 … 丨 中 存 在 当 计算 到 剖 面父点 的 最 后 一 点 时 ， 应 按 照 最 后 一 点 、 二 二 ， 使得 ： 与 ：二 连 勺 、 三角 形外部一 点 、 第 一 个点 、 的 顺 序 求 出 三 角 距离要远大 于其他相邻两 交点 之 间 距离 ， 即 ， 的 形 的 面 积 所有 三角 形 有 向 面 积 的 叠 加 就是该剖 面 要远大 于其他相邻两交点 之 间 距离 ； 的 面 积 因 此 剖 面 的 面积 为 与 ， 与 连 线 的 距离远 小 于 与 今 与 连线 的 距离 ， 即 ， 要远小于 ‘ 与 、 与 七 之 间 都 存 在 其 他 的 交 用该剖 面 的 面 积乘 以 平行平面 的 间 距得到 的 是 点 ， 且交点 数大于 两个平行平 面之 间 的 三 角 模 型 的 体 积 将 所有 的 体 满 足 以 上三个条件 的 剖 面 交点需要将该剖 面上 积进行加 和 就可得 到 三角 网 模 型 的 体积 由 于 采 空 的 点 划 分到 两个点 集 中 ， 分 别 对各 个封 闭 剖 面 区 域 区 的 整 体形状是不 规 则 的 ， 因 此 紧 邻 两 个 剖 面 的 面 求 面积 积会有 差别 为 了 进一 步减小误差需 要 求 取上 下 两 三 角 网 模型体 积微积 分计 算 剖 面面积的 平均 值 用 紧 邻 两 剖 面 的 均 值 面 积乘 以 基于 四 面体求取三 角 网 模 型 体积是按照求 出 剖 两平行平 面 之 间 的 间 距求取 体 积 则 三 角 网 模 型 的

第9期 罗周全等：采空区体积三角网模型剖面的微积分算法 .1147, 体积V为 但运算速度相对较低.实际应用中宜取剖面间距为 V= 立0.5(s+5)d 0.10~0.25m.当剖面间距为0.1m时，分析表明， (7) i=I 单个采空区体积的绝对误差小于35m3,采空区体积 式中，d为剖切面之间的间距；S,和S:1分别为z=a 相对误差小于0.004%.因此该算法计算的体积是 和z=,1两剖面的面积 准确且可靠的. 2算法实现及应用 为了进一步验证该算法的准确性，取多个不同 采空区的参考体积，与利用本算法、四面体法、正二 运用Visual C++程序语言编程实现了采空区 十面体的方法和凸五面体法求得的体积相对误差进 体积计算的三角网格模型剖面微积分算法.图10 行对比分析，如图11. 为采空区体积计算界面. ·一剖面微积分算法一正二十面体方法 0中大学果安区对大衡三迪建可现化速威氧年 凸五面体法 口日风题题国百？ 么x发2a一田田☑☑@周☑ 0.007 0.006 0.005 562#立又29行4525.32a 0.0D4 0003 16 采空区数 图11不同方法求得采空区体积与参考值的偏差 图10剖面微积分算法体积计算界面 Fig.11 Deviations between the volume values obtained by different Fig.10 Volume computation interface of the calculus algorithm methods and the reference value 依据剖面微积分算法求取采空区的体积，通过 运用采空区三角网模型剖面微积分算法求取采 设定不同的剖面间距值分析算法的准确性和算法效 空区的体积是建立在精确建模的基础上.因此，精 率，并运用目前较为成熟的某三维软件计算获得的 确建立采空区三角网格模型是运用微积分算法求取 某采空区体积值为45329m3,将其作为参考值.实 采空区体积的关键.虽然空区三角网模型体积的剖 验统计结果如表1所示. 面微积分算法求得的采空区体积较为精确，但是对 表1采空区体积计算结果和算法效率 于存在图8所示的情形时，求得的体积误差较大 Table 1 Volume and operation time of the cavity 因此，对于存在较多、较大凸起和凹陷的采空区求取 剖面 采空区 体积绝对 算法 体积时要进行误差分析. 间距/m 体积/m3 误差值/m3 效率/s 3结论 0.01 45325 4 30 0.05 45315 g 21 (1)提出了采空区三角网模型体积的剖面微积 0.09 45308 21 15 分算法.以生成的三角网模型为基础，确定剖切方 0.10 45296 33 > 向后对模型进行剖切，按照三角形与剖切平面的关 0.25 45292 37 系，求取三角形与剖切面的交点；按照凸包压人法生 0.50 45285 44 4 成剖面图；运用三角形的有向面积的叠加求出剖面 0.75 45270 西 3 的面积，进而求得模型的体积工程应用表明，算法 1.00 45242 87 2 具有良好的稳定性和精度，实现了复杂采空区体积 2.00 45225 104 的精确求取 (2)运用提出的剖面轮廓线的凸包压入法生成 根据实验结果可见：当剖面间距为0.10~ 完整剖面边缘轮廓线，能很好地反映采空区边界的 0.25m时，求的体积较为接近参考值，且运算速度较 细节，有效地实现了复杂采空区剖面的生成，具有实 快；当剖面间距小于0.10m时，求的体积准确度高， 际工程应用价值，从而为矿山实施采空区灾害防治

第 期 罗 周 全等 ： 采 空 区 体 积 三 角 网 模 型 剖 面 的 微积分算 法 体积 为 但运算速度相 对较低 实 际应用 中 宜取剖 面 间 距为 当 剖 面 间 距 为 时 分析表 明 ， ‘ ‘ 单个采空 区体积 的 绝对误差小于 ， 采空 区 体积 式 中 为 剖 切 面之间 的 间 距 和 分别 为 相对误差小于 因 此 该算 法计算 的 体 积是 和 两剖 面 的 面积 准确 且可靠 的 为 了 进一 步验证该算法 的 准 确 性 ， 取 多 个不 同 采空 区 的 参考体积 与 利 用 本算 法 、 四 面 体 法 、 正 二 运 用 程序 语言 编 程 实 现 了 采 空 区 十 面体的方法 和 凸 五 面体法求得 的 体积相对误差进 体积计算 的 三 角 网 格 模 型 剖 面 微 积分算 法 图 行对 比分析 如 图 为采空 区体积计算界 面 一 剖句丨 面微积分膽算 吐法 丄正丁— 十 紐面体方十法吐 一 人 ■ 软件 凸 五面体法 中南大学一 菜空区激先探激三 建曳可视化集成系统 口 回 泛 圔 園 ： 匕 七 田 — 、 一 — 采 空 区 数 图 不 同方法求 得采 空 区 体 积 与 参 考值 的 偏 差 图 口 丨 面 微 积 分 算 法 体 先 、 丨 卜 算 各 面 依据 剖 面微积分算 法求 取 采 空 区 的 体积 ， 通 过 运用 采 空 区三角 网 模 型 剖 面微积分算法求取采 设定不 同 的 剖 面 间 距值分析算法 的 准确性和算法效 空 区 的 体积是 建立 在 精 确 建 模 的 基础 上 因 此 ， 精 率 二 并运 用 目 前较为 成熟 的 某 三 维 软 件 计 算 获 得 的 确 建立采空 区 三角 网 格模 型 是运 用 微积分算法求取 某采空 区 体积值 为 ， 将 其作 为 参 考 值 实 采空 区 体积的 关键 虽 然空 区 三 角 网 模 型 体积 的 剖 验统计结果 如 表 所示 面微积分算 法求 得 的 采 空 区 体 积较 为 精 确 ， 但是 对 表 采 空 区体 积计算结果 和 算法效率 于存在 图 所 示 的 情 形 时 ， 求 得 的 体 积 误 差 较 大 因 此 ， 对于存在较多 、 较大 凸 起和 凹 陷 的采空 区求取 剖 面 采空 区 体 积绝 对 算 法 体积 时要进行误差分析 间 距 体积 误差 值 效率 结论 提 出 了 采空 区 三角 网 模 型体积 的剖 面微积 分算法 以 生 成 的 三 角 网 模 型 为 基础 ， 确 定 剖 切 方 向 后对模 型进行剖 切 ， 按 照 三 角 形 与 剖 切 平 面 的 关 系 ， 求取三角 形 与 剖切 面 的 交点 ； 按 照 凸 包压入法生 成剖面 图 ； 运用 三 角 形 的 有 向 面 积 的 叠 加 求 出 剖 面 的 面积 ， 进 而求得模 型 的体积 工 程应用 表 明 ， 算 法 具有 良 好的 稳定性 和 精 度 ， 实 现 了 复 杂 米 空 区 体 积 的 精确 求取 （ 运用 提 出 的 剖 面轮廓线 的 凸 包压入法生成 根 据 实 验 结 果 可 见 ： 当 剖 面 间 距 为 完整 剖 面边缘轮廓 线 ， 能 很 好地 反 映采空 区 边 界 的 时 ， 求 的 体积较为 接近参考 值 且运 算速度 较 细节 ， 有效地实现 了 复杂采空 区 剖 面 的 生成 具有 实 快 ； 当 剖 面 间 距小 于 时 ， 求 的 体积准确 度 高 ， 际工程应用 价值 从 而 为 矿 山 实施 采 空 区 灾 害 防 治

·1148· 北京科技大学学报 第36卷 及空区周边资源安全开采提供重要的技术支持 Detection Dissertation ]Changsha:Central South University, 2010 参考文献 (罗贞焱.基于CMS探测的采空区三维可视化系统研究[学位 [1]Li X B,Li D Y,Zhao G Y,et al.Deteeting,disposal and safety 论文】.长沙：中南大学，2010) evaluation of the underground goaf in metal mines.J Min Saf Eng, [9]Zhang X Y,Zhou M Q,Geng G H,et al.A method of detecting 2006,23(1):24 the edge of triangular mesh surface.J Image Graphics,2003,8 (李夕兵，李地元，赵国彦，等.金属矿地下采空区探测、处理 (10):1223 与安全评判.采矿与安全工程学报，2006,23(1)：24) (张献颗，周明全，耿国华，等.空间三角网格曲面的边界提 [2]Xiong L X,Luo Z Q.Research on management system of goaf 取方法.中国图象图形学报，2003,8(10)：1223) information based on VRML.Sci Technol Rev,2012,30(1):48 [10]Qiao PC,Wu ZG.Li H,et al.Power quality synthetic evalua- (熊立新，罗周全.基于VRML的采空区信息管理系统的开 tion based on improved radar chart.Electr Power Autom Equip, 发.科技导报，2012,30(1)：48) 2011,31(6):88 [3]Luo Z Q,Liu X M,Zhang M Y,et al.Stope 3D monitoring and (乔鹏程，吴正国，李辉，等.基于改进雷达图法的电能质量 its mining index visible calculation.J Cent South Univ Sci Techn- 综合评估方法.电力自动化设备，2011,31(6)：88) ol,2009,40(6):1732 [11]Dai W J,Pang M Y,Wu G S,et al.Extracting volume distribu- (罗周全，刘晓明，张木毅，等.大规模采场三维探测及回采指标 tion feature from 3D models.J Huazhong Univ Sci Technol Nat 可视化计算.中南大学学报：自然科学版，2009,40(6)：1732) Sci Ed,2005,33(Suppl):326 [4]Zhang X Q,Zhu G,Hou M L,et al.Volume calculation of (戴文俊，庞明勇，武港山，等。三维模型轴向体积分布特征 surface irregular cultural relic based on tetrahedron.Bull Surv 提取及比较算法.华中科技大学学报：自然科学版，2005， Map,2011(10):50 33(增刊)：326) (张小青，朱光，侯妙乐，等.基于四面体的不规则表面文物 [12]Dai W J,Pang M Y,Wu GS,et al.Extracting volumetric fea- 体积计算.测绘通报，2011(10)：50) tures from arbitrary geometric models.Comput Si,2006,33 [5)Chen D,Tian X,Shen Y,et al.On visual similarity based 3D (4):198 model retrieval.Comput Graphics Forum,2003,22(3):223 (戴文俊，庞明勇，武港山，等.一种任意三维实体网格模型 [6]Liu K W.Study of3D Laser Scanning,Visualization and Analysis 的体积特征提取算法.计算机科学，2006,33(4)：198) of the Stability of Hazardous Cavity Under Open-pit Mine Disserta- [13]Rezaei H.On the convex hull generated by orbit of operators. tion ]Changsha:Central South University,2012 Linear Algebra Its Appl,2013,438(11):4190 (刘科伟.露天开采隐患空区激光三雏探测可视化研究及其 [14]Ping Y,Tian Y J,Zhou Y J,et al.Convex decomposition based 稳定性分析[学位论文].长沙：中南大学，2012) cluster labeling method for support vector clustering.Comput [7]Xiao C X.Studies on Digital Geometry Processing of 3D Point- Sci Technol,2012,27(2):428 sampled Models Dissertation ]Hangzhou:Zhejiang University, [15]Liu G H,Chen C B.A new algorithm for computing the convex 2006 hull of a planar point set.J Zhejiang Univ Sci A,2007,8(8): (肖春薇.三维点采样模型的数字几何处理技术研究[学位论 1210 文】.杭州：浙江大学，2006) [16]Zhang X Q,Tang Z J,Yu J H,et al.Convex hull properties and [8]Luo Z Y.The Research of Goaf's 3D Visual System Based on MS algorithms.Appl Math Comput,2010,216(11):3209

北 京 科 技 大 学 学 报 第 卷 及空 区周边资源安全开采提供重要 的技术支持 ； 参 考 文 献 （ 罗 贞 焱 基于 探测 的 采空 区三维可 视化系统研究 学位 论文 长 沙 ： 中 南大学 ， ， ， ： ， ， 李夕 兵 ， 李地元 ， 赵 国彦 ， 等 金属 矿地下采空 区探测 、 处理 （ 与安全评判 采 矿与安 全工程学报 ， ： 张献颖 ， 周 明 全 ， 耿 国 华 ， 等 空 间 三 角 网 格 曲 面 的 边 界提 取方法 中 国 图 象 图形学报 ， ， ： ： 熊立新 ， 罗 周 全 基 于 的 采 空 区 信 息 管 理 系 统 的 开 发 科技 导报 ， ： ： 乔鹏 程 ， 吴正 国 ， 李辉 ， 等 基于改进雷达图法 的 电 能质量 综合评估方法 电力 自 动化设备 ， ； ， ： ， ， ， 罗周全 ， 刘晓明 ， 张木毅 ’ 等 大规模采场三维探测及 回采指标 可视化 算 中南大学学报 ： 自 然科学版 ， ； ： ， 戴文 俊 ， 庞 明 勇 ， 武港 山 ， 等 二维模 型 轴 向 体积分布特征 提取及 比较算 法 华 中 科技 大 学 学报 ： 自 然 科 学 版 ， ， ： 增 刊 ） ： 张小青 ， 朱光 ， 侯妙乐 ， 等 基于 四 面 体 的 不 规 则 表 面 文 物 丨 ， 体积计算 测 绘通 报 ， ： ， ， ： ， ； 戴文俊 ， 庞 明 勇 ， 武港 山 ， 等 一■ 种任 意 二维实体网格模型 的 体积特征 提取算 法 计算 机科学 ， ： ： ： 刘科伟 露 天开 采 隐 患 空 区 激 光 三维 探测 可 视 化研究 及 其 丨 稳定性分析 学位论文 长沙 ： 中 南大学 ， ： ， ， ： 肖 春霞 三维点 采样模 型 的数字几何处 理技术研究 学位论 文 杭州 ： 浙江大学 ， ， ， ：