空间定位技术(第七讲).pptVIP

第四章 射线跟踪定位理论与方法 4.1 射线跟踪方法简介 4.1.1 射线跟踪机理 4.1.2 正向射线跟踪 4.1.3 反向射线跟踪 4.1.4 两种跟踪方法比较 4.1.5 射线跟踪加速技术 4.2 适应于射线跟踪定位的数据库 4.2.1 几何模型 4.2.2 形态模型 4.2.3 多面体面模型 4.2.4 GIS数据库转换 4.1.5 射线跟踪加速技术 正向算法和反向算法这两种射线跟踪方法的分析中可以看出它们有一些共同的射线跟踪过程：射线与多面体面和劈的相交测试，以确定一条射线是否被某一个障碍物所遮挡。因城市微小区中建筑物的数量多，在射线和多面体面和劈的相交测试上所花费的时间可能占总的射线跟踪时间的90%以上，只有不到10%的时间用在多面体面的反射点和劈上的绕射点等的计算中。因此，射线跟踪加速技术主要是研究减少射线与多面体面和劈的相交测试。这可以从两个方面来考虑这个问题：一方面利用空间分区技术，直接减少多面体面和劈的相交测试的次数；另一方面，利用镜像法等方法提高射线反射和绕射路径的跟踪求迹速度，间接减少射线与多面体面的相交测试。 空间分区技术是将整个考察区域分为很多的小区域，这些小区域里的面和劈的数量就会比较少，当射线进入某一小区域的时候，只需要用这个小区域内的面和劈来进行遮挡检验，这就大大减少了遮挡检验的次数。在建筑密集的城区，一个微小区内面和劈的数目相当多。如果不采用一些技巧，每根射线都同小区内每个面、每个劈进行相交判断，这个计算量是很大的。层次越深计算量越大，以致计算量难以承受。所以需要采用有效的技术来减少计算量。这就是分区技术的产生的主要原因。 最简单的分区方法就是直接空间分区，图4-5显示了直接空间分区方法的2D情况。 图4-5 直接空间分区图图 角分区是以源点为中心，如图4-6所示，按照一定的角素将考察区域分为若干小区域进行标注，对区域内的面按照其与源点距离的远近进行排序，如区域(6)，它所含的面就标记为(1，2，5，4，3)。从源点出发到区域的射线按顺序同其所含的面、劈进行求交计算，一旦有相交情况发生，就不需要同相交面后面的面进行求交计算了。这种分区方法的计算量比直接空间分区更少。但这种分区法同源点的位置有关，当有反射或绕射发生时，需要重新进行分区。当计算的层次较多时，分区的工作量也是比较大的。一种折衷的方法是将两种分区法结合起来用，对于头两个层次的计算用角分区法，高层次的计算用直接空间分区法。 图4-6 角分区图 直接空间分区是用正方形（在2D情况下）或正方体（在3D情况下）划分小区。还有另外两种分区方法，就是三角分区和八叉树分区。三角分区方法主要在2D情况应用，八叉树分区适用于真3D环境，是比前三种方法性能都要好的分区方法。用它进行计算只需要进行一次分区。由于其自身特殊的层次数据结构关系，在进行区域的自动划分及射线跟踪时，它比前三种分区方法都有较大的优势。 提高射线反射和绕射路径的跟踪求迹速度，主要是对提高反射射线的求迹速度而言，有镜像方法和枕形（Pincushion）方法两种。镜像法和枕形法也合称为弹跳射线法SBR（Shooting and Bouncing Ray），是用来寻找从源（或次级源）到接收点的多次反射射线的两种方法。图4-7，图4-8分别表明了镜像方法和枕形法对反射射线的求迹过程。 2011.03.17 镜像法是从对所有看得见的建筑物表面建立源的镜像开始的。镜像本身也在对它可见的所有建筑物表面成镜像。从图4-7中可以看到这种镜像，并且重复上述的成像过程一直达到需要考虑的多次反射数目，这时就可以在每一个镜像和接收机之间建立连线。到了这一步，有必要确定这种连线是否和在建筑物墙位置的镜像平面相交，而不仅仅是它的解析延拓，例如在图4-7中，从第二级镜像到Rx1的射线同在RB1点的镜像平面相交于RB1点，在那里存在有一个建筑物表面，因此就可以起到一个反射点的作用。然而，从第二级镜像到Rx2的射线同镜像平面相交于RB2点，那里不存在墙，因此也就不是一个有效的反射点。 图4-8中描述的枕形法，从离开源(或次级源)且角距为δ的射线开始。计算射线和数据库中所有墙壁的交点，因其它的交叉点被第一个墙壁所遮挡，只选择最接近源的交叉点作为反射墙。然后检验最终所得的射线部分，看它是否照射了任何的接收位置。下一步，计算在反射墙壁上的入射角以得出反射射线方向，之后就可以求得它同下一个墙壁的交点，因此也就确定了反射射线部分的线段。对每一条从源发出的射线，重复执行这个过程直到到达所期望的反射次数。求找射线和墙壁的交叉点是枕形法程序中最耗时的过程。 4.2 适应于射线跟踪定位