地图综合线目标的综合算法研究-毕业论文

中南大学本科生毕业论文 I 地图综合线目标的综合算法研究 目录 目录目录I 图表目录图表目录.III 摘要摘要 .1 ABSTRACT2 第一章第一章 绪论绪论 .3 1.1 引言.3 1.2 研究背景.4 1.3 论文的组织.5 第二章第二章 线目标综合的基本理论和评价方法线目标综合的基本理论和评价方法 .6 2.1 线目标综合的基本原理.6 2.2 线目标综合的基本方法.7 2.2.1 角度法.8 2.2.2 面积法.9 2.2.3 垂比弦算法.9 2.2.4 弧比弦算法.10 2.3 线目标综合基本方法的不足.11 2.4 算法评价的基本原理及指标介绍.12 2.5 本章小结.13 第三章第三章 弧比弦算法的设计及改进弧比弦算法的设计及改进 .14 3.1 弧比弦算法的基本原理.14 3.2 弧比弦算法的改进.18 3.2.1增强支撑域的自适应性改进18 中南大学本科生毕业论文 II 3.2.2 增强算法的迭代性更优化其性能.22 3.3 本章小结.26 第四章第四章 在在 VISUAL STUDIO 2008 平台上用平台上用 ARC ENGINE 9.3 二次开发实现算法二次开发实现算法27 4.1 开发平台介绍.27 4.1.1、Arc Engine 9.3介绍27 4.1.2、Visual Studio 2008 C#.NET介绍27 4.2 算法的实现.28 4.2.1、MainForm窗体.28 4.2.2、CArcDivideDistance类.31 4.2.3、CNewArcDDistance类.32 4.2.4、CNewDDis1类33 4.2.5、CEvalution类34 4.3 本章小结.35 第五章第五章 总结及展望总结及展望 .36 主要参考文献主要参考文献 .37 致谢致谢 .38 中南大学本科生毕业论文 III 图表目录 图图 1 曲线简化算法示例曲线简化算法示例 6 图图 2 线目标综合算法的分类线目标综合算法的分类 8 图图 3 角度法角度法 8 图图 4 面积法面积法 9 图图 5 垂比弦算法垂比弦算法 10 图图 6 弧比弦算法弧比弦算法 10 图图 7 曲线简化法生成自相交曲线简化法生成自相交 11 图图 8 连续剔除节点造成曲线大的失真连续剔除节点造成曲线大的失真 11 图图 9 曲线简化算法的性能评价曲线简化算法的性能评价矢量和面的位移矢量和面的位移 12 图图 10 NAKOSMITROPOULOS 算法算法14 图图 11 原始曲线图原始曲线图 15 图图 12 用弧比弦算法简化线目标用弧比弦算法简化线目标 16 图图 13 用弧比弦算法简化线目标用弧比弦算法简化线目标 17 图图 14 增强支撑域的自适应性改进增强支撑域的自适应性改进 18 图图 15 增强支撑域的自适应性改进结果图增强支撑域的自适应性改进结果图 1 .19 图图 16 增强支撑域的自适应性改进结果图增强支撑域的自适应性改进结果图 2 .20 图图 17 两种算法的每个点的弧比弦值两种算法的每个点的弧比弦值 22 图图 18 增强算法的迭代性改进算法增强算法的迭代性改进算法 2 结果图结果图 1 .23 图图 19 增强算法的迭代性改进算法增强算法的迭代性改进算法 2 结果图结果图 2 .24 图图 20 程序主界面程序主界面 28 表表 1 弧比弦算法保留点不同的评价指标弧比弦算法保留点不同的评价指标 16 表表 2 弧比弦算法保留点不同的评价指标弧比弦算法保留点不同的评价指标 17 表表 3 增强支撑域的自适应性改进评价结果表增强支撑域的自适应性改进评价结果表 1 .21 表表 4 增强支撑域的自适应性改进评价结果表增强支撑域的自适应性改进评价结果表 2 .21 表表 5 增强算法的迭代性改进算法增强算法的迭代性改进算法 2 评价结果表评价结果表 1 .25 中南大学本科生毕业论文 IV 表表 6 增强算法的迭代性改进算法增强算法的迭代性改进算法 2 评价结果表评价结果表 2 .25 中南大学本科生毕业论文 1 摘要 地图综合是地理信息科学界、地图制图科学界的重要研究课题之一。其中 线目标的综合算法研究是一个关键的问题。现有线目标综合算法大多是考虑线 目标的节点曲率，通过确定节点的重要性程度来进行节点剔除，以实现线目标 的简化。然而，现有算法在算法效率、简化错误率、表达效果等方面都存在不 足。为此，本文试图解决这些问题，提出一种迭代的自适应弧比弦算法。首先， 本文简要地回顾了国内外地图综合的发展现状，阐述了线目标综合的基本理论 和方法；然后，结合弧比弦算法的优缺点，提出了一种自适应弧比弦算法，降 低了曲线简化的错误率，优化了算法结果。在此基础上，使用迭代法对改进算 法进行了进一步优化，在不追求算法效率的前提下得到了更优的效果。进而， 通过在 Visual Studio 2008 平台中用 C#.NET + Arc Engine 9.3 二次开发实现原弧 比弦算法及其改进算法，进一步验证了本文改进算法的可行性、有效性和健壮 性。最后，总结了本文的研究成果，并展望了该方向进一步研究的若干问题。 关键字：关键字： 地图综合；线目标简化；弧比弦；算法改进 中南大学本科生毕业论文 2 ABSTRACT In the map generalization, generalization of the line feature was very important. For the generalization of the line feature, point-reduction is one of the most important issues. In the process of the curve simplification, a most basic issue is how to measure the importance of all vertices in the curve. This article briefly retrospect the development status of the map generalization both abroad and at home, elaborates the basic principle and method on the local length ratio algorithm, compares its advantages and disadvantages, makes a suggestion on the improvement of the generalization of the line feature algorithm in theory, proposes an improved algorithm through a series of experiments, and gives its assessment method. And than on the Visual Studio 2008 platform using C#.NET + Arc Engine 9.3 the second-development is carried on to achieve the original local length ratio algorithm and its improved algorithm; evaluations of the two algorithms are also given. Finally, according to the results of the evaluation test of curve simplification, the relative local length ratio algorithm is concluded. The improved algorithm has a better effect on the curve simplification, the selected nodes can retain the shape of the curve better and noise can be effectively avoided. KeyKey wordswords：map generalization; measure of the importance of vertices in the curve; local length ratio algorithm; improvement of the algorithm 中南大学本科生毕业论文 3 第一章 绪论 1.1 引言 随着地理信息系统应用领域和需求层次的不断扩展和多样化,地图综合问题 成了当前地理信息科学研究的热点问题1。地图综合中的一个重要内容是单个 线目标的综合，其核心问题是曲线的简化。这一问题作为地图综合的重要组成 部分被许多学者所研究,并广泛应用于地理信息科学、计算机视觉、计算机图形 学、模式识别等诸多领域2。例如，在地理信息科学领域，曲线简化应用于地 图综合、数据压缩等方面；在模式识别与计算机图形学领域，曲线简化则用于 目标提取，节点的压缩编码等方面。 在曲线简化的过程中，一个最基本的问题是如何确定曲线上节点的重要性 程度。Attneave 发现在曲线上，一部分节点比另一部分节点有着更丰富的信息， 保留那些有着丰富信息的节点可以在曲线简化后尽可能保持曲线的形状不变和 曲线的信息不丢失3。即在曲线简化中剔除部分含信息较少的节点不会导致曲 线大的变形和信息的丢失，从而很好的实现曲线的简化。于是，怎样找出这些 含有较多信息的节点就是曲线简化的一个重要问题。而本文的主题就是讨论如 何找出曲线上那些含有丰富信息的节点，即曲线简化方法优化的问题。 目前，许多学者都在研究如何度量曲线上节点的重要性程度并简化曲线， 他们提出的方法大致有以下两个方向：无支撑域的曲线简化方法和有支撑域的 曲线简化方法。其中无支撑域的曲线简化方法主要包括角度法4-6、面积法7等； 有支撑域的曲线简化方法则主要包括弧比弦算法8、垂比弦算法9等。现在又有 许多综合性算法，比如弧比弦算法与角度法的结合、垂比弦算法与角度法的结 合等1。地图综合中著名的道格拉斯普克算法就是无支撑域的曲线简化方 法的一种10。这些算法都在地图综合中广泛使用，其中角度法、面积法在地图 综合中使用较早，但效果没有后几种方法好，所以现在普遍使用后几种算法实 现地图综合。 本文从弧比弦算法入手，先介绍该算法的工作原理，对其进行分析，总结 出它的优点和不足，并对其不足进行自适应的改进。在此基础上，使用迭代法 对自适应改进算法进行进一步优化，在不追求算法效率的前提下得到了更优的 中南大学本科生毕业论文 4 效果。继而采用当下流行的 Visual Studio 2008 平台用 C#.NET + Arc Engine 9.3 二次开发实现弧比弦算法及其改进算法，并用给出的曲线简化评价指标对其进 行评价，最后得出结论。 1.2 研究背景 地图综合是传统制图学和自然地理学的课题，和所有其他地理学课题一样， 现在它也成为地理信息科学界的重要课题之一。从表现形式上看，地图综合是 指地图信息随显示范围的变化而具有不同详细程度。这种变化主要是由于地图 的缩放操作而引起的。在实际中，地图的综合包含两层含义：一是显示具有单 一比例尺数据的某一地图时，在不同的缩放比率下地图呈现出具有不同详细程 度的外观;二是当地图有多级比例尺时，当地图的缩放比率达到一定程度时，可 以自动调阅该图上一级或下一级比例尺的地图11。最理想的综合应是地图自动 逐级抽象，这也是自动综合的研究目标，但目前实现起来仍较为困难。 在以往地图综合的研究中，4 个人先后出现提出了线目标的综合，他们分 别是：Tobler (1966)、Tpfer(1966)、Pillewizer (1966) 和 Perkal (1966)。在 20 世纪 70 年代，线目标综合算法得到了飞速发展，到 20 世纪 80 年代，学者们对 这些线目标综合算法进行了评价，并展开了面目标的综合算法研究。 20 世纪 90 年代以来，地图综合一直是热门的研究课题。国际制图协会 （ICA）于 1991 年成立自动制图综合小组。国际摄影测量与遥感（ISPRS）协 会于 2000 年专门设立了一个地图综合工作组。目前关于这一主题的特别会议已 经举办了多次，并且都取得了巨大的成果。 线目标的综合从地图综合的研究出现至今，一直经历着快速的发展。从 Attneave 发现线目标上的一些点比另一些点包含更加丰富的信息，学者们就相 继发现了曲线简化的一系列方法，例如角度法，面积法，垂比弦算法，弧比弦 算法等。后来又提出了一系列曲线简化算法的评价标准，实现了算法效能的评 价。现在学者们又开始了算法的融合和该进12，想进一步优化算法的性能，这 就是当前线目标综合的研究方向。 40 多年过去了，随着地理信息科学的发展，地图综合和曲线简化经过 40 年余年的发展已经相对比较成熟。一门学科经过 40 多年的发展而确立，学科越 中南大学本科生毕业论文 5 来越完善，这标志着它的逐渐成熟。 1.3 论文的组织 本文共分为五章，分别从论文背景及问题的提出；线目标综合的基本理论、 方法和弧比弦算法的分析和评价；弧比弦算法的不足及其改进以及改进算法的 评价；在 Visual Studio 2008 平台上用 Arc Engine 9.3 二次开发实现弧比弦算法 及其改进算法这五个方面进行阐述，下面对其分别进行介绍： 第一章为概论，首先阐述了论文的基本情况，介绍了地图综合的研究背景， 以及论文研究问题的提出，说明了章节的安排情况。 第二章为线目标综合的基本理论和方法，介绍了线目标综合的基本原理和 方法，阐述了线目标综合算法的一些不足及改进方向，并对线目标综合算法的 评价给出了基本的原理及指标。 第三章为弧比弦算法的设计及改进，首先介绍了弧比弦算法的基本原理， 然后指出弧比弦算法的一些不足，并结合曲线综合的改进方向就两个方面对其 进行改进，逐步得出最终的改进算法，最后给出算法的评价，得出自己的结论。 第四章为在 Visual Studio 2008 平台上用 Arc Engine 9.3 二次开发实现算法， 首先介绍了开发的基本平台，然后分别讲述了原弧比弦算法及其改进算法的实 现方法。 第五章为总结及展望，主要总结了我在论文完成中遇到的一些问题及以后 对该课题的后续研究方向。 最后为主要参考文献及致谢。 中南大学本科生毕业论文 6 第二章 线目标综合的基本理论和评价方法 2.1 线目标综合的基本原理 线目标综合算法，顾名思义，是减少曲线上不必要的点的数量，用较少的 含有丰富信息的点来表达这条曲线的算法，我们也称这种算法为曲线简化算法。 在早期，减少曲线上的点的数量是一个十分重要的课题，因为在当时而言，存 储曲线的大量数据是一个很大的开销。于是就有许多学者开始研究如何用较少 的含有丰富信息的点来代替原始曲线以达到曲线简化的目的。图 1 说明了曲线 简化算法的基本思想。图 1a 是一条曲线，它有许多点组成，但其中只有少数被 选择用来代表原来的线目标。图 1b 则显示了许多曲线简化的可能结果之一，它 用五个点来代表原始曲线。 （a）一条许多点组成的曲线 （b）用五个点代表原曲线 图 1 曲线简化算法示例 我们利用曲线简化算法进行线目标综合的原理如下：通常情况下，通过删 除一些点，线的形状可以简化。所以许多学者用这种算法实现线目标的综合。 曲线简化算法的目标是尽量用最少的点去拟合原始曲线。必须强调的是，在这 些算法中应该尽量避免尺度的变化。这样就可以实现线目标的综合了。 曲线简化算法的最初思想，是由 Attneave 在 1954 年发现的，他发现线目 标上的一些点比其他一些点有着更丰富的信息，这些有着丰富信息的较少的点 足以表达线目标的形状。换言之，大量的信息较少的点，可以被除去而不会造 成线目标大的变形。在这种思想中，那些有着丰富信息的点，在计算机图形学 和模式识别学我们称之为支配点；而在空间信息科学中则被我们称作关键点。 关键点在许多学科中都是一个重要的概念，如计算机视觉、图像处理、模 中南大学本科生毕业论文 7 式识别、计算机图形学和地理空间科学等。例如，在地理空间科学中，关键点 的概念可应用于数据压缩，线的夸张表达，以及线的综合等；在计算机视觉和 模式识别中，则可应用于特征提取，形状识别，基于点的运动的评价和编码的 算法等。 而我们知道，在经典的几何学中，曲线的关键点通常是： 1、 极大值点 2、 极小值点 3、 曲率极小值点 4、 曲率极大值点 而 Freeman1978 年在上述列表中增加了以下新的内容1： 1、 曲率不连续点 2、 终点 3、 交点 4、 切点 由于这些点都拥有明确的定义，他们的特征不会受到曲线缩放（扩大或减 少） ，旋转或平移的影响，所以它们十分适合被当作曲线的关键点。 而怎样找出这些关键点并用它来表示原始曲线，就成为线目标综合算法研 究的主要问题。 2.2 线目标综合的基本方法 线目标综合主要有两种基本方法：无支撑域的综合方法和有支撑域的综合 方法。无支撑域的综合方法主要包括角度法、面积法等；而有支撑域的综合方 法主要包括弧比弦算法和垂比弦算法等。而现在又产生了许多综合性算法，比 如弧比弦算法与角度法的结合、垂比弦算法与角度法的结合等。图 2 显示了这 样的分类。 通过分析可以发现，用作无支撑域的曲线综合算法的标准通常主要是原始 的几何参数（如距离，角度，面积等） ，而用作有支撑域的曲线综合的标准则主 要是几何参数的运算结果（如垂比弦值和弧比弦值等） 。下面将分别介绍这几种 算法，见图 2。 中南大学本科生毕业论文 8 线目标综合的方法 无支撑域 有支撑域 综合性算法 角度法 面积法 弧比弦算法 垂比弦算法 弧比弦算法与角度法 垂比弦算法与角度法 图 2 线目标综合算法的分类 2.2.1 角度法 一条曲线如果删除其中某个点,将会引起一个角度的变化。因此，可以根据 这一角度变化的大小来度量这个点的重要性，当然端点应该除外。我们不妨设 曲线上的点依次为P0，P1，P2，Pn(P0和Pn为曲线的两个端点) ,那么删除任 一点Pi所引起的角度变化可以表达为： （1）1)-ni(1PPP i 1i1-ii 图3的曲线有5个节点,分别记为P0、P1、P2、P3和P4。根据式(1)可依次计算 得到P1、P2和P3的角度度量值。我们可以知道，角度变化越大,点的重要性程度 越高，其值也就越大。 图 3 角度法 中南大学本科生毕业论文 9 2.2.2 面积法 一条曲线如果删除其中某个点将会产生一个局部变形。因此，可以利用新 曲线与原始曲线围成的变形的面积来度量这个点的重要性(图 4)。这一方法称 为面积法。删除每个点(端点除外)所引起的面积变化可以表达为： (2)1)-ni(1S iA PPP 1i1- ii 图 4 的曲线有 5 个节点,分别记为 P0、P1、P2、P3和 P4。根据式(2) ,可以 得到图中每个节点的面积变形值。面积变形值越大,节点重要性程度越高。相反， 面积变形值越小,节点重要性程度则越低。 图 4 面积法 2.2.3 垂比弦算法 曲线上的节点 Pi ,其重要性可以根据该点到其邻近点 Pi-k、Pi+k连接弦长的 垂直距离 Di,k,与弦长 Ci,k的比值来度量,该种度量方法称之为垂比弦算法,其表 达式可以表达为： (3)1)-ni(1/CD iDC k ik i ， 式中 k 的取值从 1 开始,直到满足如下条件结束: (4) 1ki 1ki k i k i C D C D ， ， ， ， 如图 5 ,对于点 P4,k 取值为 2。不难发现，该方法是一种自适应度量方法, 它没有固定的支撑域。而这里支撑域可以理解为一种约束,即式(4)。 中南大学本科生毕业论文 10 图 5 垂比弦算法 2.2.4 弧比弦算法 弧比弦算法是曲线简化算法中较为成熟高效的一种算法，见图 6，Teh 和 Chin 用两点之间的弧长和相应的弦长的比值来度量节点的重要性，不同于用垂 直距离 Di,k,与相应弦长 Ci,k的比值来度量节点的重要性的垂比弦算法，弧比弦 算法的表达式可以表达为： (5)1)-ni(1/CL iLC i i 一种特殊的情况是支撑域的圆与曲线只有一个交点,这种情况下,我们把圆 心到这一交点的直线距离作为弦长 Ci,k,即弦长 Ci,k等于半径 R。 图 6 弧比弦算法 2.3 线目标综合基本方法的不足 大多数曲线简化算法可能有以下几个不足： 中南大学本科生毕业论文 11 1、算法得到的解可能不是最优的。 这一问题正是我算法改进所参考的主要因素，提高算法的效率及性能，达 到算法的优化是所有算法改进工作的最终目标，我此次改进也是从这方面入手 的。 2、不能保证生成曲线之间的自相交。 自相交的问题见图 7，产生曲线的自相交将严重破坏曲线的拓扑关系，极 端的时候可能会产生致命的缺陷，所以优秀的综合算法必须尽可能的避免产生 曲线的自相交问题。 （a）原始曲线 （b）简化后曲线 图 7 曲线简化法生成自相交 3、可能连续剔除节点而造成新生成曲线大的失真。 算法可能造成节点的连续剔除而导致曲线产生较大的变形，如图，曲线简 化时由于节点的连续剔除而出现曲线的严重变形。 （a）原始曲线 （b）简化后曲线 图 8 连续剔除节点造成曲线大的失真 4、保留的节点并不一定对曲线的表达是必须的。 这一问题是现在综合算法的前沿研究方向，怎样确定曲线上点的重要性程 度成为许多学者研究的方向，即曲线上节点的信息量的度量方法，我在今后的 中南大学本科生毕业论文 12 研究中将进一步的研究这个方向。 以上所说的这些问题往往会造成算法的效果不尽如人意，所以许多学者提 出了许多针对以上问题的算法改进方法，在下一章中我也将针对这些问题对弧 比弦算法进行一些改进，并提出一种新的改进弧比弦算法。 2.4 算法评价的基本原理及指标介绍 White(1985)和 McMaster(1986)提出了一些指标来评价曲线简化算法的性能： 即矢量位移和面位移13。这两个参数是见图 9，图 9a 是由原始曲线和保留点组 成的新曲线所形成的矢量位移，图 9b 则是由原始曲线和保留点组成的新曲线所 形成的面位移。显然，矢量位移和面位移越小，算法的性能就越好。在矢量位 移上，最大误差、中位数、平均误差均可作为其指标。 （a）矢量位移 （b）面位移 图 9 曲线简化算法的性能评价矢量和面的位移 而我在后文中将采用偏移平均值，偏移中值和面积变形值作为评价指标， 这三种指标主要是通过对删除曲线上一些重要性程度较低的节点进行评价,在很 大程度上可以视为对破坏原始曲线的稳定性的评价。对于向量偏移,我计算其中 值和平均值，即偏移平均值和偏移中值;对于面积变形,我通过简化后的曲线与 原始曲线进行叠加,然后计算产生的一系列区域单元的面积总和即可。 2.5 本章小结 本章开始阐述了线目标综合的基本方法，重点介绍了角度法、面积法、垂 中南大学本科生毕业论文 13 比弦算法以及弧比弦算法，并且指出了这些算法的一些共同不足，例如算法得 到的解可能不是最优的；可能不能保证生成曲线之间的自相交问题；可能连续 剔除节点而造成新生成曲线大的失真；曲线保留的节点可能并不一定对曲线的 表达是必须的。最后指出了评价这些算法的一个标准，即矢量位移和面位移， 给出了本文评价这些算法的标准，即采用偏移平均值，偏移中值和面积变形值 作为评价指标。 中南大学本科生毕业论文 14 第三章 弧比弦算法的设计及改进 3.1 弧比弦算法的基本原理 弧比弦算法是曲线简化算法中性能较好算法，它用两点之间的弧长和相应 的弦长的比值为标准来度量曲线上节点的重要性。弧比弦算法的这个比值可以 表示为： （6）1)-ni(1/CL iLC i i 对每一个节点，都有它自身的一个支撑域，节点的支撑域可以理解为一种 范围，即在不同的范围内节点有不同的重要性。例如在中国全图上，长沙很重 要，但在全球地图上，长沙的重要性也许就有所下降了，这个范围即可以理解 为支撑域。根据文献8,支撑域半径 R 的取值由曲线的总长度(L0) 和曲线的节 点数 V (其中端点除外)计算得到，其表达式为: （7）1) (V / L R 0 由式（6），称为曲线上节点的弧比弦值（也译为局部长度比） ，图iLC 10 以第 6 点为例来说明，其弧的长度是两部分的和，即 A6和第 6 点的距离加 上 B6和第 6 点的距离。这里 A6是的圆 6（即点 6 的支撑域）和点 5、点 6 连线 段的交叉点。B6是的圆 6 和点 6、点 7 连线段的交叉点。这种算法最初被 Nakos 和 Mitropoulos 发现，所以也称为 NakosMitropoulos 算法8。 图 10 NakosMitropoulos 算法 中南大学本科生毕业论文 15 NakoMitropoulos 算法流程如下： 1、确定了支撑域的半径值。1) (V / L R 0 2、计算每个点的。iLC 3、构建函数，并找到函数的极大值，以此最大1)-ni(1/CL iLC i i 值为关键点。 4、循环以上步骤 2、3，直到选中的关键点个数满足给定的阈值。 本文采用 Visual Studio 2008 C#.NET + Arc Engine 9.3 二次开发来实现该算 法的程序（具体见后面章节） 。为了更好地对比算法，我采用两条曲线作为实验 曲线，其一为 91 个点的一条点分布密度较大的曲线，其二为一条 40 个点分布 密度较小的曲线，它们的坐标系均为 WGS-84 坐标系，如下图： （a）原始曲线 1（点分布密度较大） （b）原始曲线 2（点分布密度较小） 图 11 原始曲线图 中南大学本科生毕业论文 16 对实验曲线 1，用弧比弦算法进行曲线简化，分别保留 60、50、40、30 个 点，所得简化结果见下图： （a）保留 70 个点 （b）保留 60 个点 （c）保留 50 个点 （d）保留 40 个点 图 12 用弧比弦算法简化线目标 所得评价指标见下表： 表 1 弧比弦算法保留点不同的评价指标 评价指标留 70 个点留 60 个点留 50 个点留 40 个点 偏移平均值(mm) 1.261.331.793.06 偏移中值(mm) 0.350.801.372.17 面积变形值(mm2) 272.56405.23760.441591.03 对实验曲线 2，用弧比弦算法进行曲线简化，分别保留 35、30、25、20 个 点，所得简化结果见下图： 中南大学本科生毕业论文 17 （a）保留 35 个点 （b）保留 30 个点 （c）保留 25 个点 （d）保留 20 个点 图 13 用弧比弦算法简化线目标 所得评价指标如下表： 表 2 弧比弦算法保留点不同的评价指标 评价指标留 35 个点留 30 个点留 25 个点留 20 个点 偏移平均值(mm) 0.932.987.8728.11 偏移中值(mm) 0.352.828.3015.31 面积变形值(mm2) 99.3814.913521.8613767.92 由上述两个实验，我们可以看出弧比弦算法随着保留点的逐渐减少而变形 逐渐变大。在曲线节点密集的情况下效果较好，而在曲线节点稀疏的情况下效 果有所下降，并产生了明显的自相交，如图 13（d） 。由此，结合上文中曲线综 合算法的可能不足，发现弧比弦算法有以下三个不足： 1、算法精度有待提高； 中南大学本科生毕业论文 18 2、可能产生连续的减点而使曲线有较大的变形； 3、生成的曲线可能产生自相交； 不难看出弧比弦算法有自己的一些独特的缺点。结合这些不足，下文中我 将分两步提出一种弧比弦算法的改进算法，对弧比弦算法进行一些改进，改善 上述不足。 3.2 弧比弦算法的改进 3.2.1 增强支撑域的自适应性改进 原弧比弦算法的支撑域 R 是整条曲线为相同的一个数值，这样如果曲线的 密度不均匀或者曲线太稀疏，很可能产生连续的节点剔除而使曲线产生大的形 变，因此曲线简化效果不是很好。我们可以总结为算法的自适应性不强，所以 下文中我将提出一种增加自适应性的改进。如图 14： 图 14 增强支撑域的自适应性改进 计算 P3点的弧比弦度量值，用 P3到 P2的距离 L3加上 P3到 P4的距离 L4之 和（即弧的长度之和）与 P2与 P4的距离 L24（即弦的长度）之比，这样就相当 于其支撑域为过 P2、P4并且包含 P3的一个圆，这样就使得算法更具有自适应性， 提高了其效能。具体算法如下： 1、从第二点到倒数第二点，计算每个点的改进弧比弦值，即一点的弧比弦 值等于这点到相邻两点的弧长之和比上相邻两点间的弦长（端点除外） 。 2、找出其中的最大值点 3、直到找到的点的数量满足阈值为止 这样就实现了算法的自适应性改进，对节点密度不均匀或节点较为稀疏的 曲线有很好的效果，实验依然采用上一章中的实验曲线 1 和 2，实验结果图如 中南大学本科生毕业论文 19 下，对于实验曲线 1： 弧比弦算法 自适应改进 （a）保留 70 个点 弧比弦算法 自适应改进 （b）保留 60 个点 弧比弦算法 自适应改进 （c）保留 50 个点 弧比弦算法 自适应改进 （d）保留 40 个点 图 15 增强支撑域的自适应性改进结果图 1 对于实验曲线 2： 中南大学本科生毕业论文 20 弧比弦算法 自适应改进 （a）保留 35 个点 弧比弦算法 自适应改进 （b）保留 30 个点 弧比弦算法 自适应改进 （c）保留 25 个点 弧比弦算法 自适应改进 （d）保留 20 个点 图 16 增强支撑域的自适应性改进结果图 2 对于实验曲线 1，其评价指标见下表： 中南大学本科生毕业论文 21 表 3 增强支撑域的自适应性改进评价结果表 1 评价指标偏移平均值偏移量中值面积变形值 原弧比弦算法 1.260.35272.56 保留 70 点自适应改进 0.260.2338.58 原弧比弦算法 1.330.80405.23 保留 60 点自适应改进 0.530.34163.62 原弧比弦算法 1.791.37760.44 保留 50 点自适应改进 1.230.60504.25 原弧比弦算法 3.062.171591.03 保留 40 点自适应改进 2.351.631266.29 对于实验曲线 2，其评价指标见下表： 表 4 增强支撑域的自适应性改进评价结果表 2 评价指标偏移平均值偏移量中值面积变形值 原弧比弦算法 0.930.3599.30 保留 35 点自适应改进 0.210.1921.51 原弧比弦算法 2.982.82814.91 保留 30 点自适应改进 3.011.38870.08 原弧比弦算法 7.878.303521.86 保留 25 点自适应改进 5.322.792186.67 原弧比弦算法 8.349.074044.51 保留 20 点自适应改进 28.1115.3113767.92 由上述实验结果可得到结论，改进算法相比原弧比弦算法，无论从直观的 曲线简化视觉效果，还是从算法的评价指标对比，效果都有明显的提高。尤其 是在曲线节点稀疏的情况下，效果较原始算法更好，并且可以有效避免产生曲 中南大学本科生毕业论文 22 线的自相交。 下面以第二条实验曲线为例，对比两种算法中每个节点的弧比弦值，如图： （a）弧比弦算法 （b）自适应改进 图 17 两种算法的每个点的弧比弦值 对比发现，改进后的算法对一些较小的值进行了放大，例如 3 点、25 点、 35 点等，所以优化了算法的效果，提升了算法的性能。 3.2.2 增强算法的迭代性更优化其性能 线要素化简的基本要求是：保持弯曲形状或轮廓图形的基本特征，即总的 图形的相似性；保持弯曲的特征转折点的精确性；保持不同地段弯曲程度的对 比。对4.2.1中弧比弦算法的改进，虽然优化了其性能，但在计算机硬件快速发 展的今天,这算法的运算量和速度已不是主要问题。现在所关心的关键是化简前 后线要素的形状逼近程度以及是否存在错误(如自相交问题等)。所以我们可以 采用迭代算法进一步提高算法的效率，因此我在这一节中我将提出最终的弧比 弦改进算法如下： 1、从第二点到倒数第二点，计算每个点的改进弧比弦值（计算方法同 4.2.1 中的改进算法 1） ，即：一点的弧比弦值等于这点到相邻两点的弧长之和比上相 邻两点间的弦长（端点除外） 。 2、找出其中值最小的点，将其从曲线中剔除并生成新曲线 3、对新的曲线再进行此算法。 4、直到曲线还有规定数量阈值的点为止。 这样就实现了算法的迭代性，它可以有效的避免连续的节点剔除，使得曲 线简化的效果更好。实验效果见下图，对于曲线 1： 中南大学本科生毕业论文 23 自适应改进 迭代自适应改进 （a）保留 70 个点 自适应改进 迭代自适应改进 （b）保留 60 个点 自适应改进 迭代自适应改进 （c）保留 50 个点 自适应改进 迭代自适应改进 （d）保留 40 个点 图 18 增强算法的迭代性改进算法 2 结果图 1 中南大学本科生毕业论文 24 对于曲线 2： 图 19 增强算法的迭代性改进算法 2 结果图 2 自适应改进 迭代自适应改进 （a）保留 35 个点 自适应改进 迭代自适应改进 （b）保留 30 个点 自适应改进 迭代自适应改进 （c）保留 25 个点 自适应改进 迭代自适应改进 （d）保留 20 个点 中南大学本科生毕业论文 25 实验的评价指标见下表，对于曲线 1： 表 5 增强算法的迭代性改进算法 2 评价结果表 1 评价指标偏移平均值偏移量中值面积变形值 原弧比弦算法 1.260.35272.56 自适应改进 0.260.2338.58 保留 70 点 迭代自适应改进 0.240.2338.58 原弧比弦算法 1.330.80405.23 自适应改进 0.530.34163.62 保留 60 点 迭代自适应改进 0.440.34120.18 原弧比弦算法 1.791.37760.44 自适应改进 1.230.60504.25 保留 50 点 迭代自适应改进 0.870.67375.15 原弧比弦算法 3.062.171591.03 自适应改进 2.351.631266.29 保留 40 点 迭代自适应改进 1.110.80502.52 对于曲线 2： 表 6 增强算法的迭代性改进算法 2 评价结果表 2 评价指标偏移平均值偏移量中值面积变形值 原弧比弦算法 0.930.3599.30 自适应改进 0.210.1921.51 保留 35 点 迭代自适应改进 0.210.1921.51 原弧比弦算法 2.982.82814.91 自适应改进 3.011.38870.08 保留 30 点 迭代自适应改进 1.301.15310.8 原弧比弦算法 7.878.303521.86 自适应改进 5.322.792186.67 保留 25 点 迭代自适应改进 3.362.731249.84 中南大学本科生毕业论文 26 原弧比弦算法 28.1115.3113767.92 自适应改进 8.349.074044.51 保留 20 点 迭代自适应改进 5.823.013118.64 由以上实验图示及评价指标表可见，改进算法经过迭代后效果明显改善， 得到的曲线更加吻合原始曲线，并且有效的改善了可能连续剔除节点带来的曲 线大的变形，尤其在剔除节点较多的情况下，这种改善更为明显。 3.3 本章小结 本章首先介绍了弧比弦算法的基本原理，然后指出它的一些不足，并针对 这些不足对弧比弦算法进行了两次改进，得到了一种新的具有自适应性的迭代 弧比弦算法。得到的改进算法可以有效的提高算法的性能，并且很好的解决了 弧比弦算法的三个不足：即改善了算法的性能；有效的减少了生成曲线的自相 交可能性；并且最大程度的抑制了可能的连续节点剔除，使得生成的曲线更加 吻合原始曲线，算法的效果得到了明显改善。 但是算法改进的不足之处是尚未能解决弧比弦算法的最后一个缺点，即保 留的节点并不一定对曲线的表达是必须的。这个问题涉及到曲线上节点的信息 量的问题，我会在以后的研究中继续就这个问题进一步优化我的算法，达到更 好的曲线简化效果。 中南大学本科生毕业论文 27 第四章 在 Visual Studio 2008 平台上用 Arc Engine 9.3 二次开发实现算法 4.1 开发平台介绍 我的整个算法程序开发采用 Visual Studio 2008 C#.NET 平台，在其之上使 用 ESRI 公司的 Arc Engine 9.3 开发包进行二次开发，下面分别介绍之： 4.1.1、Arc Engine 9.3 介绍14 Arc Engine 是基于核心组件库 Arc Objects 搭建的。Arc Objects 组件库有 3000 多个对象可供开发人员调用，为开发人员集成了大量的 GIS 功能，可以快 速的帮助开发人员进行 GIS 项目的开发。ArcGIS 可以在多种编程环境中进行开 发，其中包括：C+、支持 COM 的编程语言、.NET、Java 等。 2004 年，美国 ESRI 发布 Arc Engine 9.3，Arc Engine 9.3 具有简洁、灵活、 易用、可移植性强等特点。Arc Engine 开发包提供了一系列可以在 ArcGIS Desktop 框架之外使用的 GIS 组件，Arc Engine 9.3 的出现对于需要使用 Arc Objects 的开发人员来说是个福音，因为 Arc Engine 9.3 发布之前，基于 Arc Objects 的开发只能在庞大的 ArcGIS Desktop 框架下进行。 4.1.2、Visual Studio 2008 C#.NET 介绍15 C#是一种程序开发语言，它在.NET 平台上开发，.NET 平台上支持用 C#或 者 VB 进行开发。另外，C#不但可以开发基于.NET 的应用程序，也可以开发基 于 WinForm 的程序，而用 Arc Engine9.3 进行的二次开发就是基于 WinForm 的 程序开发。 C#（读做 C-sharp）编程语言是由微软公司的 Anders Hejlsberg 和 Scott Willamette 领导的开发小组专门为.NET 平台设计的语言。C#是事件驱动的、完 全面向对象的可视化编程语言，我们可以使用集成开发环境 IDE 来编写 C#程序。 使用 IDE 后，程序员可以方便的建立，运行，测试和调试 C#程序。 中南大学本科生毕业论文 28 4.2 算法的实现 我的程序的主界面如图 20，它继承了 ArcGIS 的简洁易用的特点： 图 20 程序主界面 我的整个程序有一个主窗体 MainForm 以及四个类，四个类分别是实现弧比 弦算法的 CArcDivideDistance 类，实现自适应改进算法的 CNewArcDDistance 类，实现迭代的自适应改进算法的 CNewDDis1 类，以及实现算法评价的 CEvalution 类，它们分别实现三种算法以及对其评价的工作。 4.2.1、MainForm 窗体 MainForm 窗体采用 Arc Engine 9.3 插件式开发，保留了 ArcGIS 的基本界面 风格，在其中主要实现了图层的读取以、进行算法以及图形的现实等功能。 图层的读取分为点图层、线图层和面图层，代码的框架如下（示例为读取 线图层）： /读取线图层并保存线元素 IPolyline polyline = new PolylineClass(); IFeatureLayer lyr = this.getLayer(“polyline1“); IFeatureClass featureClass = lyr.FeatureClass; ESRI.ArcGIS.Geodatabase.IFeature Feature; object o = Type.Missing; Feature = featureClass.GetFeature(0); polyline = (IPolyline)Feature.Shape; return polyline; 中南大学本科生毕业论文 29 图层的显示也分为点图层、线图层和面图层，代码的框架如下（示例为读 取线图层）： /线元素的显示 IFeatureLayer pFlayer = this.getLayer(“ArcDDis“); IFeatureClass pFClass = pFlayer.FeatureClass; IFeature pFeat = pFClass.CreateFeature(); pFeat.Shape = geometry; pFeat.Store(); axMapControl1.Refresh(); 实现一个曲线简化算法并评价有三个类似的函数，分别实现三种算法。下 面以改进算法 2 为例展示，即迭代自适应弧比弦改进算法，程序实现点线的读 取，循环减点，显示新的线并评价其算法，代码示例如下： /迭代自适应弧比弦改进算法程序 private void btnNewRun_Click(object sender, EventArgs e) /获取点图层 List lpoint = new List(); lpoint = readPointLayer(); /获取线图层 IPolyline lpolyline = new PolylineClass(); lpolyline = readLineLayer(); object o = Type.Missing; /循环减点 int rNumber = Convert.ToInt32(txtNumber.Text); /保留点数 int d