3.2.1　误差定义

第1章给出了空间近似查询的定义,同时给出了空间近似查询作为查询条件的两个约束项,一是误差约束,二是数据量约束。无论以哪类约束进行空间近似查询,都需要使用顶点的误差值进行查询处理。在误差约束下,通过设置误差阈值进行顶点采样;在数据量约束下,通过设置数据量阈值给出查询结果,同时返回顶点的最大误差值。

误差是衡量查询精准度的重要指标,是近似查询的核心概念。误差的度量方法根据应用需求的不同而不同。常用的根据几何特征度量误差的方法包括曲线长度比、曲折度、位置误差等。其中,曲线长度比是指简化前后线对象在长度上的比值,曲折度是指曲线上每相邻直线段组成的夹角之和,位置误差是指简化前后曲线围成的面积与原始线长度的比值。然而,对于基于屏幕的交互式可视化而言,误差是定义在像素空间的,原始几何对象与近似后的几何对象可视化时的误差在图形设备上表现为两条线的像素差异。例如,即使近似的线对象与原始线对象具有较大的差别,但在可视化界面上可能只表现出很小甚至没有像素差异。因此,像素差异会使得原本存在的几何误差度量方法得出的结论具有一定的差异。

由于数据可视化结果最终表现为屏幕像素,这种像素差别可采用豪斯多夫距离进行精确度量。因此选择原始线对象可视化形成的像素集合与近似后的线对象可视化形成的像素集合的豪斯多夫距离作为面向数据可视化的误差。

豪斯多夫距离是一种可以应用在边缘匹配算法的距离,其计算公式如下:

(https://www.daowen.com)