首页 > 论文范文 > 工程工业论文 > 军事技术论文 > 军事地形学论文 > 利用一次性构建Delaunay三角网模型实现视域分析

利用一次性构建Delaunay三角网模型实现视域分析

2020-01-08 608 上传者：管理员

摘要：任何军事行动都离不开对地形的分析和判断，视域分析作为地形分析的重要组成部分，被广泛应用，尤其是在军事行动的许多方面都具有极其重要的作用。基于此，本文在一次性构建约束Delaunay三角网DEM模型的基础上，结合模型的数据结构特点，分析、研究了两点可视、范围可视以及区域可视的3种视域分析算法。

关键词：
Delaunay三角网
数据结构
算法
视域分析
加入收藏

1、概述

任何军事行动都是在一定的地理环境下进行的,都要受到地形的制约。在现代化战争条件下,基于地理信息系统（GIS）的地形显示、地形分析等是对地形环境认识的一种重要手段。其中,直瞄武器的视界、最少观察点的设定、隐蔽路线的选择等都离不开地形分析中的视域分析,是地形分析的主要组成部分,是GIS空间分析中的关键技术。视域分析是指从某一特定位置所能看到的地形范围或与其他地形点的可见程度,其应用可归结为以下3种情况：（1）两点可视,即两点间的通视判断；（2）范围可视,即观察点对两个方向射线间的区域进行可视分析；（3）区域可视,即观察点对一定半径内的区域进行可视分析。

在GIS中,视域分析主要是通过分析数字高程模型（DEM）中的每个单元数据的高程值来确定特定位置的可见性。数字地形模型(DTM)是地形表面形态属性信息的数字表达,是带有空间位置特征和地形属性特征的数字描述,当数字地形模型中地形属性为高程时称为数字高程模型(DEM)。DEM有多种表达方式,包括网格、等高线、三角网等。在一次性构建约束Delaunay三角网DEM模型的基础上,利用模型数据结构的特点和优势,分析、研究了两点可视、范围可视以及区域可视的3种视域分析算法。

2、一次性构建Delaunay三角网模型算法

算法的总体步骤^[1][2]

(1) 将所有离散点和约束线段端点数据信息存储到点链表中,将约束线段数据信息存储到线段链表中。设置标志位,记录存储完所有约束线段后线段链表的表尾位置。

(2) 根据点数据链表,对点数据进行预处理,创建点数据的格网索引。

(3) 依次将线段链表中的每一条约束线段作为基边,应用夹角最大准则分别在该线段的左右两侧找到第三点,生成左右三角形(若某条约束线段是边界线段则只能生成一个三角形),形成初始三角网。将新生成的三角形、非约束线段信息分别记录到三角形链表和线段链表,且记录不重复。更新基边信息。

(4) 从标志位的下一条线段（即构建三角网时生成的第一条非约束线段）开始,依次判断该条线段是否已存在左三角形,如果存在,则判断下一条线段；否则,将该条线段作为基边,按照一步生长法向左生成新的三角形。记录新生成的三角形信息和非约束线段信息,更新基边信息。直到遍历完线段链表。

(5) 基于非约束线段对剖分结果进行优化处理。从标志位的下一条线段开始,依次判断其左右三角形是否同时存在,如果不同时存在,判断下一条线段；否则,判断该条线段是否与其左右第三点的连线相交,如果不相交,则进行下一条线段的优化处理,否则,对其左右三角形进行优化处理。

2.2算法的数据结构

一次性构建Delaunay三角网算法中的线段和三角形的嵌套数据类结构及三角形链表的数据结构如下：

2.2.1 线段和三角形的嵌套数据类结构

c|assCLine

{pub|ic:

Int Index;

CDot*startdot;CDot*|astdot;//线段的起始//点和终止点

c|assCTriang|e

{pub|ic:

Int index;

CDot*firstdot;CDot*seconddot;CDot*thirddot;//三角形三点

CLine*first|ine;CLine*second|ine;CLine*third|ine;//三角形三边

CTriang|e*next;};CTriang|e*|efttin;CTriang|e*righttin;//线段的//左右三角形

CLine*next;};

c|assCTriang|eLink

{pub|ic:

Int tricount;CTriang|e*headtri;CTriang|e*peartri;}

2.2.2 线段和三角形数据形成的拓扑结构

线段与三角形数据形成的拓扑结构如图1所示。

图1 约束边和三角形数据形成的拓扑结构

3、视域分析算法原理与实现

3.1 视域分析算法原理

视域分析算法中最基本的是对视线（LOS）的计算和基于LOS的可视域计算。其中,视线（LOS）是指从观察点G起到目标点M的一条射线。如果在射线方向上,无遮蔽点P,则两点通视。根据三角形定理可得：PD=GC×MP/GM。因此,当PD>GC×MP/GM,G、M不能通视；当PD<GC×MP/GM,G、M能通视。该算法关键：遮蔽点的确定以及其高程的计算。如图2所示。

图2 两点通视算法原理图

可视域是指观察点对观察区域能看见的具体范围。其大小根据观察区域内的遮蔽点及其遮蔽区域判断。当P为遮蔽点时,对观察点C的遮蔽边界M位置的确定公式为：GM=GP×GC/（GC-PD）,如图3所示。

图3 可视域算法原理图

3.2 两点可视算法步骤

算法的总体步骤描述如下^[3]：

（1）根据观察点G、目标点M的坐标,分别判断出G、M所在的三角形TinG、TinM,以及G、M两点的高程值。

（2）以观察点G所在的三角形TinG为起始三角形TinP,判断视线GM与三角形TinP相交的边线L,并记录边线L的另一侧三角形TinN。

（3）计算视线GM与边线L的交点I,并根据边线L的两个端点LA、LB的高程值,计算出交点I的高程值G1。

（4）根据交点I所在视线GM的位置及G、M两点的高程值计算出交点I的高程值G2。

（5）当G1>G2时,两点间不能通视；否者用三角形TinN替换三角形TinP。

（6）重复步骤2-5,直到起始三角形TinP即为目标点M所在的三角形TinM为止。

3.3 区域可视算法步骤

算法的总体步骤描述如下：

（1）根据观察点G、目标点M1、M2的坐标,判断出GM1、GM2的位置关系,将位于视线方向左侧的目标点记为Ml,位于视线方向右侧的目标点记为Mr。

（2）根据观察点G、目标点Ml、Mr的坐标,分别判断出G、Ml、Mr所在的三角形TinG、TinMl、TinMr,以及3个点的高程值。

（3）根据数据结构,找出GMlMr范围内的所有三角形,记入三角形链表TinlinkRange。

（4）将TinlinkRange中的第一个三角形作为起始三角形TinP,TinP的3个顶点记为T1、T2、T3。

（5）计算视线GT1与MlMr的交点I1,并根据GT1的高程值,计算出交点I1的高程值G1。

（6）根据交点I1所在视线MlMr的位置及Ml、Mr两点的高程值计算出交点I的高程值G2。

（7）当G1>G2时,T1为不可通视顶点。

（8）计算视线GT2与MlMr的交点I2,并根据GT2的高程值,计算出交点I2的高程值G1。

（9）根据交点I2所在视线MlMr的位置及Ml、Mr两点的高程值计算出交点I2的高程值G2。

（10）当G1>G2时,T2为不可通视顶点。

（11）计算视线GT3与MlMr的交点I3,并根据GT3的高程值,计算出交点I3的高程值G1。

（12）根据交点I3所在视线MlMr的位置及Ml、Mr两点的高程值计算出交点I3的高程值G2。

（13）当G1>G2时,T3为不可通视顶点。

（14）当T1、T2、T3均为不可通视顶点时,TinP三角形为不可通视三角形；当T1、T2、T3均为可通视顶点时,TinP三角形为可通视三角形；否则,进入（15）。

（15）分别将T1T2的中点记为M1,T2T3的中点记为M2,T3T1的中点记为M3。将三角形TinP分解成4个三角形T1M1M3、M1T2M2、M2T3M3以及M3M1M2,并记录到TinlinkRange链表。

（16）用TinlinkRange中的下一个三角形替换三角形TinP。

（17）重复步骤4-16,直到完全遍历三角形链表TinlinkRange。

3.4 范围可视算法步骤

算法的总体步骤描述如下：

（1）根据观察点G和观察半径R,找出所有范围内的三角形,并记录到三角形链表TinlinkRange。

（2）将TinlinkRange中的第一个三角形作为起始三角形TinP,TinP的3个顶点记为T1、T2、T3。

（3）计算视线GT1与圆GR的交点I1,并根据GT1的高程值,计算出交点I1的高程值G1；

（4）判断I1所在的三角形TinI1,并计算出I1在TinI1中的高程值G2。

（5）当G1>G2时,T1为不可通视顶点。

（6）计算视线GT2与MlMr的交点I2,并根据GT2的高程值,计算出交点I2的高程值G1；

（7）判断I2所在的三角形TinI2,并计算出I2在TinI2中的高程值G2。

（8）当G1>G2时,T2为不可通视顶点。

（9）计算视线GT3与MlMr的交点I3,并根据GT3的高程值,计算出交点I3的高程值G1；

（10）判断I3所在的三角形TinI3,并计算出I3在TinI3中的高程值G2。

（11）当G1>G2时,T3为不可通视顶点。

（12）当T1、T2、T3均为不可通视顶点时,TinP三角形为不可通视三角形；当T1、T2、T3均为可通视顶点时,TinP三角形为可通视三角形；否则,进入（13）。

（13）分别将T1T2的中点记为M1,T2T3的中点记为M2,T3T1的中点记为M3。将三角形TinP分解成4个三角形T1M1M3、M1T2M2、M2T3M3以及M3M1M2,并记录到TinlinkRange链表。

（14）用TinlinkRange中的下一个三角形替换三角形TinP。

（15）重复步骤2-14,直到完全遍历三角形链表TinlinkRange。

4、结语

从上述3种情况的视域分析算法步骤描述中可以看出,视域分析算法的时间消耗主要集中在以下两个方面：（1）找出可能的遮蔽点或遮蔽三角形；（2）判断是否是遮蔽点或遮蔽三角形。由于一次性构建Delaunay三角网数据结构的优越性,大大减小了查找可能的遮蔽三角形所耗费的时间；另外,当可能的遮蔽三角形的3个顶点有的是遮蔽点有的不是遮蔽点时,算法采取了中点切割三角形的方法,既解决了区域视域分析结果不精确的问题又没有额外增大算法的时间复杂度。

参考文献：

[1]任振娜,李斌兵.一次性生成约束Delaunay三角网算法的编程与实现[J].测绘工程,2006,1:54-58.

[2]任振娜,杨颖.一次性生成约束Delaunay三角网的算法研究[J].几何设计与计算的新进展,2005:151-154.

[3]陈龙,王永君,李大军.R3视域算法与参考面算法的对比研究[J].测绘与空间地理信息,2014,5:36-38.

[4]吴超辉,张涵斐,公茂玉.一种改进的地形上一点可视区域近似值算法[J].信息工程大学学报,2014,4:198-204.

任振娜.刍议基于一次性构建Delaunay三角网模型实现视域分析[J].电脑编程技巧与维护,2019,(8):24-26.

网友评论

加载更多

我要评论

期刊名称：地理研究

期刊人气：2651

期刊详情

主管单位：中国科学院

主办单位：中国科学院地理科学与资源研究所,中国地理学会

出版地方：北京

专业分类：地质

国际刊号：1000-0585

国内刊号：11-1848/P

邮发代号：2-110

创刊时间：1982年

发行周期：月刊

期刊开本：16开

见刊时间：一年半以上

论文导航

利用一次性构建Delaunay三角网模型实现视域分析

相关论文

军事堡寨型的传统村落空间形态研究分析

关键词

四川云顶城防御空间的形态探究

关键词

基于战争防御的中原传统乡村防御聚落特性研究

关键词

以老牛湾堡为例分析晋北明长城沿线军事堡寨的景观特色及其保护利用策略

关键词

BOPPPS模式基础上的军事地形学课程教学方法研究

关键词

以拆除明清城墙为考察对象分析民国时期郑州城市的变迁

关键词

兰彻斯特方程基础上分析战场地形因素对战争的影响

关键词

解析野外综合训练中军事地形学的实际应用

关键词

国外军事地质学热点问题分析

关键词