平面扫描算法的动态容差确定方法

《平面扫描算法的动态容差确定方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、平面扫描算法的动态容差确定方法朱效民，赵红超，方金云中国科学院计算技术研究所北京市海淀区科学院南路6号中科院计算所，100190摘要:本文采用高斯误差传递公式来分析平面扫描算法中浮点数的计算误差。通过这个方法，可以提前计算得到一个浮点数并将其设定为动态容差，用来判断两个浮点数是否相等。动态容差保证了浮点计算存在误差的前提下扫描线算法的正确性。基于扫描线算法的应用程序证明了此方法的正确性与有效性。关键词:误差分析，高斯误差传递，容差，浮点计算1.引言平面扫描算法是计算几何中的基础算法，它用来计算平面上若干线段的交点。这个算法首先由Shamos和Hoey提

2、出[1]，并且由Bentely和Ottmann[2]作了改进，然后许多以此为基础的变种出现。所有这些算法都有相同的核心思想―通过扫描的方法计算交点而非通过N×N的循环计算，更多的实现细节请参考相关的参考文献[1][2]。这些算法的核心需要这样一个过程－得到过当前事件点的所有线段。如果我们仅仅从理论上实现这个算法，也就是假设浮点计算是精确计算，那么一个线段可能不会过某个事件点哪怕这个事件点是一个由此线段产生的交点。事实上，在算法实现过程中，我们首先计算交点，然后通过一个点和线段的关系判断得到过当前事件点的所有线段。也就是说，计算过某点的线段是算法的一个必

3、需步骤。这个过程大致如下：如果一个点足够靠近一个线段，那么我们认为这个点在线段上。因此，我们需要确定靠近的程度，也就是多近是足够的并且合适的。实际计算中，点与多边形关系的判断首先判断点是否位于线段的最小包含矩形中。若在矩形内部，再通过判断点与线段的两个端点所围成的三角形的面积得到。这个判断的具体实现请参考在第四节中的代码实现。理论上，我们可以计算三角形的面积是否为0.0。然后，在具体实现时，应该设定一个合适的容差值。如果计算得到的三角形面积的绝对值小于此容差值，那么我们认为此值为0.0，也就是线段过当前事件点。这个容差值必需合理设置－如果这个值太小的话

4、，可能会遗漏一些过当前点的线段；而如果这个值过大的话，可能会得到额外的一些线段经过当前点而实际上它们并不经过当前事件点。如果这个值设置不合理，整个依赖于此求交算法的应用程序将无法正确实现。目前，一些涉及平面扫描算法的论文或者仅仅给出了理论上的实现[2]，或者仅仅设定一个静态值（[6]中的epsilon）作为容差，或者通过高精度的计算[7]，或者采用有理数计算[8]。高精度计算或者有理数计算都需要耗费更多的时间，而静态容差可能仅仅适用于某些类型的数据－比如说对于采用经纬度为单位的数据与采用KM为单位的数据，因为其数值大小的范围不相同，因此其容差值也不相同

5、。也就是对不同数量级的数据，有不同的容差值。如果根据当前数据动态地设置容差正是本文的动机。本文的高斯误差分析方法解决了这454个问题。本文组织如下：第二节中介绍了一些关于浮点数以及VC++对浮点数的支持。第三节中介绍了一些误差传递的公式。在第四节中，提出了动态容差计算方法，并且以代码的形式从误差的产生到容差的使用详细分析了动态容差的计算过程。然后在第五节中给出了真实数据的测试并且在第六节中作了小结。2.浮点数以及VC++的实现大部分的编程语言和编程环境采用IEEE－754标准[3][4]，也就是二进制浮点运算的标准。这个标准定义了四种不同精度的浮点数：

6、single,single-extended,double以及double-extended.它们都有相似的编码格式，不同的是它们的位数。下面将以double为例简单介绍一下它们的格式。标准定义的double类型有64位，从高位到低位包括1位符号位（signbit）、11位指数位（exponent）以及52位底数位（mantissa），每一位的值为0或者1。BitNumber6362～5251～0MeaningSignExponentMantissa一般而言，由SEΛEMΛM636252510代表的实际值是由三个值决定的：符号值S、指数值E和底数值M。

7、这三个值的计算公式如下：S=1S63=0S=−1S=16301910E=Λ2×E+2×E++2×E+2×E52536162−1−2−51−52M=M×2+M×2+Λ+M×2+M×2515010E−1023S×(1+M)×2对于一个NormalNumbers[3][4]，其值为：。此外，标准还定义了以下浮点类型的数：Subnormals，Infinites,SNaNs和QNaNs。关于这些类型的具体编码格式，请参考相关的文献[3][4]。一般而言，浮点计算主要涉及NormalNumbers。VC++编程采用了IEEE－754标准，并且支持三种浮点类

8、型：float、double以及longdouble，分别对应于标准中的single，doub