1、中南大学本科生毕业论文I地图综合线目标的综合算法研究目录目录 .I图表目录 .III摘要 .1ABSTRACT.2第一章 绪论 .31.1 引言 .31.2 研究背景 .41.3 论文的组织 .5第二章 线目标综合的基本理论和评价方法 .62.1 线目标综合的基本原理 .62.2 线目标综合的基本方法 .72.2.1 角度法 .82.2.2 面积法 .92.2.3 垂比弦算法 .92.2.4 弧比弦算法 .102.3 线目标综合基本方法的不足 .112.4 算法评价的基本原理及指标介绍 .122.5 本章小结 .13第三章 弧比弦算法的设计及改进 .143.1 弧比弦算法的基本原理 .143.
2、2 弧比弦算法的改进 .183.2.1 增强支撑域的自适应性改进 .18中南大学本科生毕业论文II3.2.2 增强算法的迭代性更优化其性能 .223.3 本章小结 .26第四章 在 VISUAL STUDIO 2008 平台上用 ARC ENGINE 9.3 二次开发实现算法 .274.1 开发平台介绍 .274.1.1、 Arc Engine 9.3 介绍 .274.1.2、 Visual Studio 2008 C#.NET 介绍 .274.2 算法的实现 .284.2.1、 MainForm 窗体 .284.2.2、 CArcDivideDistance 类 .314.2.3、 CNew
3、ArcDDistance 类 .324.2.4、 CNewDDis1 类 .334.2.5、 CEvalution 类 .344.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
4、原始曲线图 .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 增强支撑域的自
5、适应性改进评价结果表 2 .21表 5 增强算法的迭代性改进算法 2 评价结果表 1 .25中南大学本科生毕业论文IV表 6 增强算法的迭代性改进算法 2 评价结果表 2 .25中南大学本科生毕业论文1摘要地图综合是地理信息科学界、地图制图科学界的重要研究课题之一。其中线目标的综合算法研究是一个关键的问题。现有线目标综合算法大多是考虑线目标的节点曲率，通过确定节点的重要性程度来进行节点剔除，以实现线目标的简化。然而，现有算法在算法效率、简化错误率、表达效果等方面都存在不足。为此，本文试图解决这些问题，提出一种迭代的自适应弧比弦算法。首先，本文简要地回顾了国内外地图综合的发展现状，阐述了线目标综
6、合的基本理论和方法；然后，结合弧比弦算法的优缺点，提出了一种自适应弧比弦算法，降低了曲线简化的错误率，优化了算法结果。在此基础上，使用迭代法对改进算法进行了进一步优化，在不追求算法效率的前提下得到了更优的效果。进而，通过在 Visual Studio 2008 平台中用 C#.NET + Arc Engine 9.3 二次开发实现原弧比弦算法及其改进算法，进一步验证了本文改进算法的可行性、有效性和健壮性。最后，总结了本文的研究成果，并展望了该方向进一步研究的若干问题。关键字： 地图综合；线目标简化；弧比弦；算法改进中南大学本科生毕业论文2ABSTRACTIn the map generaliz
7、ation, 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 br
8、iefly 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 algorit
9、hm 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 algorith
10、m; 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 sha
11、pe of the curve better and noise can be effectively avoided.Key words：map generalization; measure of the importance of vertices in the curve; local length ratio algorithm; improvement of the algorithm中南大学本科生毕业论文3第一章 绪论1.1 引言随着地理信息系统应用领域和需求层次的不断扩展和多样化,地图综合问题成了当前地理信息科学研究的热点问题 1。地图综合中的一个重要内容是单个线目标的综合，其
12、核心问题是曲线的简化。这一问题作为地图综合的重要组成部分被许多学者所研究,并广泛应用于地理信息科学、计算机视觉、计算机图形学、模式识别等诸多领域 2。例如，在地理信息科学领域，曲线简化应用于地图综合、数据压缩等方面；在模式识别与计算机图形学领域，曲线简化则用于目标提取，节点的压缩编码等方面。在曲线简化的过程中，一个最基本的问题是如何确定曲线上节点的重要性程度。Attneave 发现在曲线上，一部分节点比另一部分节点有着更丰富的信息，保留那些有着丰富信息的节点可以在曲线简化后尽可能保持曲线的形状不变和曲线的信息不丢失 3。即在曲线简化中剔除部分含信息较少的节点不会导致曲线大的变形和信息的丢失，从
13、而很好的实现曲线的简化。于是，怎样找出这些含有较多信息的节点就是曲线简化的一个重要问题。而本文的主题就是讨论如何找出曲线上那些含有丰富信息的节点，即曲线简化方法优化的问题。目前，许多学者都在研究如何度量曲线上节点的重要性程度并简化曲线，他们提出的方法大致有以下两个方向：无支撑域的曲线简化方法和有支撑域的曲线简化方法。其中无支撑域的曲线简化方法主要包括角度法 4-6、面积法 7等；有支撑域的曲线简化方法则主要包括弧比弦算法 8、垂比弦算法 9等。现在又有许多综合性算法，比如弧比弦算法与角度法的结合、垂比弦算法与角度法的结合等 1。地图综合中著名的道格拉斯普克算法就是无支撑域的曲线简化方法的一种
14、10。这些算法都在地图综合中广泛使用，其中角度法、面积法在地图综合中使用较早，但效果没有后几种方法好，所以现在普遍使用后几种算法实现地图综合。本文从弧比弦算法入手，先介绍该算法的工作原理，对其进行分析，总结出它的优点和不足，并对其不足进行自适应的改进。在此基础上，使用迭代法对自适应改进算法进行进一步优化，在不追求算法效率的前提下得到了更优的中南大学本科生毕业论文4效果。继而采用当下流行的 Visual Studio 2008 平台用 C#.NET + Arc Engine 9.3二次开发实现弧比弦算法及其改进算法，并用给出的曲线简化评价指标对其进行评价，最后得出结论。1.2 研究背景地图综合是
15、传统制图学和自然地理学的课题，和所有其他地理学课题一样，现在它也成为地理信息科学界的重要课题之一。从表现形式上看，地图综合是指地图信息随显示范围的变化而具有不同详细程度。这种变化主要是由于地图的缩放操作而引起的。在实际中，地图的综合包含两层含义：一是显示具有单一比例尺数据的某一地图时，在不同的缩放比率下地图呈现出具有不同详细程度的外观;二是当地图有多级比例尺时，当地图的缩放比率达到一定程度时，可以自动调阅该图上一级或下一级比例尺的地图 11。最理想的综合应是地图自动逐级抽象，这也是自动综合的研究目标，但目前实现起来仍较为困难。在以往地图综合的研究中，4 个人先后出现提出了线目标的综合，他们分别
16、是：Tobler (1966)、Tpfer(1966)、Pillewizer (1966) 和 Perkal (1966)。在 20世纪 70 年代，线目标综合算法得到了飞速发展，到 20 世纪 80 年代，学者们对这些线目标综合算法进行了评价，并展开了面目标的综合算法研究。20 世纪 90 年代以来，地图综合一直是热门的研究课题。国际制图协会（ICA）于 1991 年成立自动制图综合小组。国际摄影测量与遥感（ ISPRS）协会于 2000 年专门设立了一个地图综合工作组。目前关于这一主题的特别会议已经举办了多次，并且都取得了巨大的成果。线目标的综合从地图综合的研究出现至今，一直经历着快速的发
17、展。从Attneave 发现线目标上的一些点比另一些点包含更加丰富的信息，学者们就相继发现了曲线简化的一系列方法，例如角度法，面积法，垂比弦算法，弧比弦算法等。后来又提出了一系列曲线简化算法的评价标准，实现了算法效能的评价。现在学者们又开始了算法的融合和该进 12，想进一步优化算法的性能，这就是当前线目标综合的研究方向。40 多年过去了，随着地理信息科学的发展，地图综合和曲线简化经过 40年余年的发展已经相对比较成熟。一门学科经过 40 多年的发展而确立，学科越中南大学本科生毕业论文5来越完善，这标志着它的逐渐成熟。1.3 论文的组织本文共分为五章，分别从论文背景及问题的提出；线目标综合的基本
18、理论、方法和弧比弦算法的分析和评价；弧比弦算法的不足及其改进以及改进算法的评价；在 Visual Studio 2008 平台上用 Arc Engine 9.3 二次开发实现弧比弦算法及其改进算法这五个方面进行阐述，下面对其分别进行介绍：第一章为概论，首先阐述了论文的基本情况，介绍了地图综合的研究背景，以及论文研究问题的提出，说明了章节的安排情况。第二章为线目标综合的基本理论和方法，介绍了线目标综合的基本原理和方法，阐述了线目标综合算法的一些不足及改进方向，并对线目标综合算法的评价给出了基本的原理及指标。第三章为弧比弦算法的设计及改进，首先介绍了弧比弦算法的基本原理，然后指出弧比弦算法的一些不
19、足，并结合曲线综合的改进方向就两个方面对其进行改进，逐步得出最终的改进算法，最后给出算法的评价，得出自己的结论。第四章为在 Visual Studio 2008 平台上用 Arc Engine 9.3 二次开发实现算法，首先介绍了开发的基本平台，然后分别讲述了原弧比弦算法及其改进算法的实现方法。第五章为总结及展望，主要总结了我在论文完成中遇到的一些问题及以后对该课题的后续研究方向。最后为主要参考文献及致谢。中南大学本科生毕业论文6第二章 线目标综合的基本理论和评价方法2.1 线目标综合的基本原理线目标综合算法，顾名思义，是减少曲线上不必要的点的数量，用较少的含有丰富信息的点来表达这条曲线的算法
20、，我们也称这种算法为曲线简化算法。在早期，减少曲线上的点的数量是一个十分重要的课题，因为在当时而言，存储曲线的大量数据是一个很大的开销。于是就有许多学者开始研究如何用较少的含有丰富信息的点来代替原始曲线以达到曲线简化的目的。图 1 说明了曲线简化算法的基本思想。图 1a 是一条曲线，它有许多点组成，但其中只有少数被选择用来代表原来的线目标。图 1b 则显示了许多曲线简化的可能结果之一，它用五个点来代表原始曲线。（a）一条许多点组成的曲线 （b）用五个点代表原曲线图 1 曲线简化算法示例我们利用曲线简化算法进行线目标综合的原理如下：通常情况下，通过删除一些点，线的形状可以简化。所以许多学者用这种算法实现线目标的综合。曲线简化算法的目标是尽量用最少的点去拟合原始曲线。必须强调的是，在这些算法中应该尽量避免尺度的变化。这样就可以实现线目标的综合了。曲线简化算法的最初思想，是由 Attneave 在 1954 年发现的，他发现线目标上的一些点比其他一些点有着更丰富的信息，这些有着丰富信息的较少的点足以表达线目标的形状。换言之，大量的信息较少的点，可以被除去而不会造成线目标大的变形。在这种思想中，那些有着丰富信息的点，在计算机图形学和模式识别学我们称之为支配点；而在空间信息科学中则被我们称作关键点。关键点在许多学科中都是一个重要的概念，如计算机视觉、图像处理、模
