关于离散点集的三维凸包的研究

在对凸壳算法进行研究的基础上,对现有的凸壳算法进行改进,并将其应运于凸壳地质体建模中,实现了凸壳地质体模型的建立和储量的计算,通过实验证明该算法能准确、有效地进行凸壳地质体的精细建模和储量计算。

信f f f息科学

关于离散点集的三维凸包的研究吕志强司明

(西安科技大学计算机科学与技术学院，陕西西安 70 5 ) 10 4摘要：在对凸壳算法进行研究的基础上，对现有的凸壳算法进行改进，并将其应运于凸壳地质体建模中，实现了凸壳地质体模型的建立和储量的计算，实验证明该算法能准确、通过有效地进行凸壳地质体的精细建模和储量计算。 关键词：凸壳：地质体建模；算法引言凸壳 t .e u) ovxH l。 1

也称最小凸包，是包含集合s中所有对象的最小凸集。凸包的构造涉及两个问题 B凸包上的点的选取 P和这些点的连接关系的建立。由给定的点集求取凸 包是计算几何学中基本、 常见的问题姻常可以分为二维凸包和三缩二

豳l执雠墼 I井点中

整个凸壳的顶点，并能汁算出凸壳的最小体积。算法的流程图如图 1所示。 1法的具锌 2算涉骤步骤 I读取空间离散点集的数据，:对空间点按x坐标的升序进行排鼠如果x坐标相等， Y按坐标的升序进删 E如果Y序，坐标也相等，则再按 z 图 2凸包的二维显示图 3凸包的三雄显示坐标的升序进行排序。步骤 2生成初始四面体。:选取x坐标最小坐标最大、坐标最大冉L z Y芑点和坐 1. 32四面体的面

I _■P bi T p. r a e u l y eT l c t c f

标最大的四个点，由这四个点构成初始的四面体 (如果此四点共面或者有重复点，那么对这些点进

识别、图像处理和设计自动化等书， 相对于三维而言杖觯，, 成熟已经有很多研究成果；三维凸

f女一 I 础 【..... J ... ... .. . . __ . .}一●…——

广— _ —上]I 蓐☆辕 &自垂 豉f l出争再 l氇每遵疆l

包被广泛应用于计算：机仿真、建筑体建摸、地质建模，卫星通信和无线电广播等领域。 到目前为止已有众，多构造凸包的算法。计算平面点集凸壳的算法主要有卷包裹法、格雷厄姆方法、分治算法、增量算法和周培德提出的 z一 3 l和 z—算法等。卷包裹法、 32 分治算法、增量算法.3 2 Z-算法都能推广到三维，其

‘

f西l l与卞 蘑拜忙 直

行棍应的调整)舀奇是为了使点集中更多的点界面，其

9包含在初始四面体中，然后将此四面体力人四面体 I 1 f0 s og n A n L’面的编号 E dT p n ye列表T t hdo e aern中， r四个面设为凸壳的边界面，并 13四面体 3将在此四面体中的点和此四面体的四个顶点从点 u h y eT t e rn P h cT p erh do a集中删除。步骤 3生成外部点：集合。判断点集中的 v,, s e e四面体的四个顶点坐标 12 4A rx’ vv Vt点与初始四面体的关系，将不在初始四面体内部的 f,,￣ s ra t四面的四个表面 l t 34A i c’ 2 ' t T fe点加入外部点集合。点在四面体中的判断方法：点 do m s ob ’ vl nA u l u D e四面体的体积 En pe d Ty 在四面体内的判断方法很多，可以通过体积进行判 2应用实例断，由点和四面体的每个面构成四面体，如果这四原四面体的体积，那么这本文的算法已用 V 6语言实现， Bo并将其应取得了很好的效果并计算点在四面体内，否则在四面体外。也可通过判断点用于凸壳地质体建摸中，为了在面的同异侧来判断，分别取出此四面体的每个面出了地质体的准确储量。验证算法的实际运行

po 0 s ee’ a k￣A r x四面体面的三个顶点 V tⅡ A ol n s o a’ B e判断面是否为凸壳的边

和该面所对的顶点，判断这两个点是否在此面的同效果，选取了23个三位离散数据进行凸壳求取， 06 3, 4 O生成 8个边界三角形'并且能够异侧，如果点和四面体每个面所对的顶点都在此面运行时问为 1s的I倾，该点就在四面体内。这两种方法的计计算出凸壳的精确体积图 2 0 i那么】为其二维显示图， 3图r—— 1

中去。随着计算机软件和硬件技术的发展，三维凸 包算法具有更多的实用性，本文着重对三维凸包 I瓢乜l 糟凸觚嚣蔺I算法进行深入的研究，并在现有二维和三维凸包算法的基础 E出—种改进提的三维点集凸包求取算法，并将其应运到三维地质体精细建模中。 1求解算法图 I算法的流程图 1算法思想 . 1求取三维点集的凸包一般要求求出凸包的 顶点棱边集、集以及面集。当然，在三个集合中， 顶点集和画集是必需的棱边集可以由面集直接推出。, 算法的总体思路是：对给定的点集

进行四面体剖分，由四面体剖分得到点集的虽小凸壳的边界面和凸壳的顶点。首先由已知点得到初始的四面体，将其四个面都作为边界面，然后从点集中依次取出点进行四面体的扩展，将能扩展的面置为非边界面， 将扩展得到的其余三个面都设为边界面，依次类推，将点集中的所有点都扩展完毕后就得到了最小志凸壳的边界面，由组成凸壳边界面的顶点就可得到

◇

为三维下显示效果。 在四面体内。依次考察点集中的点从该点出发引 3结论条平行于 X轴的射线，如果该射线与初步凸包的该算法与传统算法比较起来计算更简便，在格生成过程中采用了基于面扩展技术，构面不相交或有 2个交点测该点在初步凸包的外部.四面体网 如果只有 1个交点测该点在初步凸包的内部。如造四面体依据的三角形或者是边界三角形，或者是果与初步凸包的棱边、蔚或顶点相交改平行于 y生成的四 0 面体的新三角形，因此中保证这些轴或 Z轴的射线然后再按照前面的方法判定。如果三角形最多只参与—次四面体的构造，同时在为每 3个方向的射线均与初步凸包的顶点或棱边相交，个三角形寻找对应顶点时保证生成的每个新四面 则该点在初始凸包的内部步骤 4从外部点集中体不会与已经存在的四面体和边界三角形交叉，:有取出一点，从四面体链表中依次取出四面体，判断效避免四面重叠，导使，魄贯体的储量体积更此点是否与四面体中的边界面所对的顶点是否在加准确。 此面的异侧，如果为 T U,此面置为非边界面， R E将 参考文献然后由此面的三个顶点和选取的 .生成新的四面 f周培德. 1]计算几何——法分析与设计，版北埠 2脚体。依次和四面体链表中的各个四面体扩展以后，京： 清华大学出版社0 o: o 15 05 O _3. l 将增加的面设为边界面并加人到边界面链表，将新[RO R EOJo p tt nleme yn1]n 2 U K m uai a o t . d] E o g r i￣1 2增加的四面口到 Tt hdo入 e aern链表，从外部点 e .a rd e mb i g Un vPr s 9 87 -& r dC mb i g:Ca r d e i e￣1 9:3 7 集中删除此点。步骤 5:重复步骤 4直到外部点集 l nlyJL as G Peaa .p mxm—, 3 t F ut M, prt

FP p i a e e r a A为空，这样就得到点集的凸包的边界面和顶点集， t n a o tmsfrC￣e ul[C m AC i l rh o Ol Xh l J o m札 o gi V s] .并能由四面体列表求出凸包的体积。 1 8,5 4 6 . 22 . - 8 9 6 1 3数据结构及算法实现情况 f】 4余翔宇，’余志雄改进的二雏点集凸包快速求孑洪， J本算法所采用的是 VB高级程序语言实现，主取方法Ⅱ武汉理工大学学报0 o2 ( 8-置 l O 5 71 18 徘要采用以下数据结构： 翻蒋红斐.平面点集凸包快速构建算法的研究口计 l 1 .三维离散点数据 .1 3算机工程与应用1 0 3【 b _ . 2 z 8 O&4 o 24 9 P b i T p e tx u l y eV r c e作者简介：吕志￣(9 03 )男，、西扶 18,一，汉陕—

算量很大，比菠低。效率

v o sI ee’ n t r数据点的点号 A ng风县，西安科技大学计算机科学与技术学院 0级 7 x￣A D u l, s obe y z离散点坐标值￣r - l s o a fgA ol n判断点是否已进行过扩展的标在￣o究生。 a B eEn y e dT p

司明(9 4 1-,汉， 1 8,1)男，宁夏中卫人，西安科技大学计算机科学与技术学院助理工程师。

一

7— 0

本文来源：https://www.bwwdw.com/article/zu2q.html