基于射线跟踪算法数字地图自动提取与预处理

冯永胜，郭立新，刘忠玉

(西安电子科技大学理学院，陕西 西安 710071)

随着移动通信业务的发展、个人通信需求的迅猛增长，通信技术应用越来越广，微蜂窝技术由于采用频谱复用技术而得到广泛应用。在这种环境下，基站天线的高度一般低于周围建筑物的高度［1］。另一方面，随着无线通信形式和容量的增加，发射源也越来越多，使得城市电磁污染进一步加重，对人体及通信环境都有不利影响。因此有必要对微小区中某辐射源的电波传播特性进行确定性分析，对于在微小区情形下的电波传播预测模型的研究也尤为重要。射线跟踪方法因具有预测精度较高、计算工作量较小、易于程序化等优点而获得广泛应用［2－4］。然而，为满足不同传播环境下信号预测的实时性，射线跟踪算法的效率仍有待于提高。尤其是在建筑物密集的城市微小区环境下，射线跟踪加速算法是一项共同研究的课题。在所有的射线跟踪技术中，遮挡判断必须被反复执行。当城市微小区环境包含大量的建筑物时，射线跟踪算法程序需要大量的计算时间。

数字地图是整个射线跟踪算法的基础，准确高效的数字地图是射线跟踪算法结果是否理想的重要保障。在已有地图的基础上，如何对地图进行二次开发，结合射线跟踪算法的需求，设计出合理高效的环境地物信息数据库即地图的存储格式，是提高算法效率的关键技术。

文中用C++结合针对AutoCAD平台上的二次开发而推出的一个开发软件包ObjectARX，开发了一段高效的可批量提取AutoCAD画出格式的数字地图点坐标的程序，可批量一次性地提取建筑物的点坐标，使其转化成标准的数字地图格式，把点坐标写入数字地图数据库文件，攻克了如何能快速的获取地图中符合射线跟踪算法所需要的地图坐标格式的难题。实现了自动化提取技术，从而能够建立实用的、快速的、高精度的室外微蜂窝环境电波预测模型。

1 地图自动提取及预处理

1.1 应用软件说明

文中采用的开发环境是电子地图软件AutoCAD2008，开发软件ObjectARX2008，Visual Stdio2005作为开发工具。ObjectARX是AutoDesk公司针对AutoCAD平台上的二次开发而推出的一个开发软件包，它提供了以C++为基础的面向对象的开发环境及应用程序接口，能真正快速的访问AutoCAD图形数据库。与以往的AutoCAD二次开发工具 AutoLISP和 ADS不同，ObjectARX应用程序是一个DLL，共享AutoCAD的地址空间，对 AutoCAD进行直接函数调用。所以，使用ARX编程的函数的执行速度得以提高。AutoCAD在批量提取点位坐标时没有相应功能，需要二次开发才能满足需要。AutoCAD的开发手段多种，如C++、ObjectARX、Java、VisualBasic、AutoLisp 等，采用C++ 结合针对AutoCAD平台上的二次开发而推出的一个开发软件包ObjectARX，开发了一段可一次性批量提取点坐标的技术，且把点坐标写入文本文件。

1.2 提取数字地图

AutoCAD文件的图元对象属性有多种形式，文中采用的电子地图有多线段、线段和圆弧3种，需要根据射线跟踪模型和图元的不同情况，通过AutoCAD的二次开发功能ObjectARX编程提取所有的图元信息分别转化为边的形式，并存入数据库。

在AutoCAD定义的图元中，线段(Line)与边的模型完全符合。搜索当前地图内所有的“Line”对象，将其两个端点坐标和对象属性提取出来，载入数据库中文件即可。

为符合射线跟踪算法地形数据库模型需要，程序需要对数字地图中的3种特殊图形进行处理，即:多线段处理、圆弧处理和子块划分的处理。以多线段为例，循环搜索电子地图图元信息，载入数据库表格。

多线段(Polyline)由一些线段首尾连接而成，分成闭合和不闭合两种。

AutoCAD定义的多线段属性中没有图元的线段数，即程序无法知道Polyline由多少条Line组成。本文处理Polyline时预定义了90次的循环依次搜索多线段的各顶点，当遍历到最后一个顶点即跳出循环。在循环的过程中，提取当前线段的顶点坐标，载入数据库。当循环至最后一个顶点时，对多线段的闭合属性作判断，如果该多线段是闭合的，则将终点和起点作为一条线段的信息载入数据库，如果多线段为非闭合的，则忽略起点和终点的连线。

分解方法如图2所示，图1中建筑物由封闭多边形ABCDEFA构成，在AutoCAD地图信息中构成一个完整的图元。当程序搜索到这个多边形后将其分解，如图2所示变成6条线段，分别以边的形式存入数据库。获取步骤为:(1)打开Autocad地图。(2)在命令行键入appload命令。(3)在弹出的对话框中装载之前已经写好的arx应用程序。(4)运行ObjectARX程序，键入命令Gp。(5)结果输出到数据库，结束。

Autocad中dwg格式的二维数字地图的提取结果如，图3为原AutoCAD中富兰克林部分街道的微小区地图;图4是根据数字地图提取出来的线段的坐标;图5是经过信息提取后用Matlab画出的图形100%吻合原来的数字地图。

图5 用Matlab画出的图形

1.3 数字地图预处理

作为一种特定地形的电波预测模型，射线跟踪算法需要准确的地形环境信息，地形数据的准确性将会影响预测结果的精度。城市微小区的环境几何描述相当复杂，包含大量的不同物体，如建筑物、路灯杆、电话亭等，另外还有一些移动的物体，如汽车和人群等。它们都会对无线传播产生影响，在这样的环境中，若不作一定的简化，即使利用了近似的电磁技术，也无法得到确定性解。另一方面，小物体的几何信息通常不可能包括在内，因此不可能得到足够的和移动障碍物有关的信息。

1.3.1 前期

在数字地图的自动提取过程中就可以先把嵌套在建筑物里面的建筑物剔除，如图6存放的是建筑物投影到地面上轮廓的描述，该投影形成的轮廓为多边形。有不少多边形套在其他多边形的内部，其实两个多边形本来就是一个建筑物，只是由于一部分高，另一部分低所以把它分成了两个多边形处理。其实内部的多边形在准三维射线跟踪中是用不到的。假如在读取的时候就将这些建筑物去掉，会减少一部分存储量，同时也会降低搜索时间。

图6 两个互相嵌套的多边形关系

1.3.2 后期

相邻建筑物间的合并。室外微小区传播场景下，建筑物的分布密集。对于这种密集建筑物群，可以视为一个大的建筑物，从而减少了射线跟踪算法在遮挡判断时要处理的墙面数和墙角数。这种合理的做法，其准确性在文献［5～6］中得到了证明。文中的建筑物合并技术比文献［6］中的更全面，可用于任何复杂情况。

图7 可以合并的相邻建筑物平面图

2 仿真结果分析

为验证预处理技术的效果，对曼哈顿市微小区数字地图中的部分区域进行处理。图8为没有进行预处理的微小区地图，图中含有315个建筑物，共2956的垂直地面的墙角。该城市地图中建筑物的高度相对较高，适合2.5D射线跟踪算法，是一个典型的室外微小区场景。

图8 预处理前城市微小区地图

利用上文提到的预处理技术对数字地图进行自动处理，处理结果表明，建筑物套嵌测试所删除的建筑物共有21个，这21个建筑物包含的总建筑物面数或墙角数为122个，这些几何信息的删除对准三维射线跟踪算法的预测精度并无影响;对建筑物进行剔除处理操作舍弃了73个墙角，套嵌和墙角剔除处理所删除的面占所有面的6.6%，依据文献［7］可知，建筑物几何信息对射线跟踪预测结果影响较大的是建筑物的空间方位，而不是墙角的微小偏移。

表1 不同合并间距下的预处理对比

表1给出了不同合并间距下的预处理结果的对比，可以看出随着合并间距的增大，其合并掉的面在增加。当合并间距为1 m时，建筑物的套嵌、轮廓的修正和建筑物合并的3种操作，使环境中的面数减少了近14%，其对应的处理效果如图9所示。因此，随着射线跟踪算法考虑的反、绕射阶数越来越大，其预处理效果越明显。

图9 预处理后城市微小区地图

3 结束语

以C++结合，针对AutoCAD平台上的二次开发而推出的一个开发软件包ObjectARX，开发了一段高效的可批量提取AutoCAD画出格式的数字地图点坐标的程序，自动提取建筑物的顶点坐标，使其转化成标准的数字地图格式。相比较以往射线跟踪利用手动提取点坐标方面效率大大提高。后文的预处理技术能实现对数字地图的预处理，改进了射线跟踪算法的运行效率，并提高了射线跟踪算法的通用性。

［1］SON H W，MYUNG N H.A deterministic ray tube method for microcellular wave propagation prediction model［J］.IEEE Trans on Antennas Propagat，1999，47(8):1344 －1350.

［2］FUSCHINI F，EL － SALLABI H，DEGLI ESPOSTI V，et al.Analysis of multipath propagation in urban environment through multidimensional measurements and advanced ray tracing simulation［J］.IEEE Trans on Antennas and Propagation，2008，56(3):848 －857.

［3］张文，杨锦辉.基于固定区域的SBR改进算法［J］.电波科学学报，2010，25(4):728 －731.

［4］李超峰，焦培南，聂文强.射线追踪技术在城市环境场强预测计算中的应用［J］.电波科学学报，2005，20(5):660 －665.

［5］TAN S Y，TAN H S.A microcellular communications propagation model based on the uniform theory of diffraction and multiple image theory ［J］.IEEE Trans on Antennas and Propag，1996，44(10):1317 －1326.

［6］DEGLI E V，FUSCHINI F，VITUCCI E，et al.Speed － up techniques for ray tracing field prediction models［J］.IEEE Trans on Antennas and Propag，2009，57(5):1469 －1480.

［7］RIZK K，WAGEN J F，GARDIOL F.Influence of database accuracy on two－dimensional ray－tracing－based predictions in urban microcells［J］.IEEE Trans on Antennas and Propag，2000，49(2):631－642.