凹多边形相似度大小的判别与实现毕业论文.doc

《凹多边形相似度大小的判别与实现毕业论文.doc》由会员分享，可在线阅读，更多相关《凹多边形相似度大小的判别与实现毕业论文.doc（55页珍藏版）》请在三一办公上搜索。

1、郑州航空工业管理学院毕 业 论 文（设 计） 2013 届 机械制造与自动化 专业 1022012 班级题 目 凹多边形相似度大小的判别与实现 姓 名 张旺 学号 10221240 指导教师 陈志远 职称 副教授 二一 三 年 5 月 20 日内 容 摘 要 凹多边形作为简单凸多边形和复杂多边形的过度桥梁，其相似度的判别准则和识别算法的合理性，能有效地解决图形智能识别的关键问题，不但对矢量图形，而且也可将光栅图形转化为矢量图形后，为基于光栅图形的矢量化识别与比较提供高效的算法。本文利用可视化的面向对象开发工具Visual C+6.0和基于AutoCAD平台的Object ARX软件饱满的支持而

2、开发的应用程序，借助Visual C+语言能方便高效地开发典型Windows风格的CAD应用程序，采用参数化设计的思想，把设计过程中重复出现的步骤全部由程序来完成，这样大大提高了绘图速度，同时方便了编辑和操作本文结合图文中多边形的化简过程与其化简规则，提出了多边形相似性描述的因子，并结合这些因子给出了一个计算相似度的公式，从而提出了一个新的思路，实验结果表明，该方法简单有效。关键词 相似度；多边形；ObjectARX 与 Visual C+；凹多边形Similarity discriminant concave polygon size and Implementation Author Zh

3、angwang Tutor Chen zhiyuan lecturerAbstractContent AbstractConcave polygon as a simple convex polygons and complex polygons over the bridge, and its similarity criterion of rationality and recognition algorithms, can effectively solve the graphical identification of key issues, not only for vector g

4、raphics, but can also be converted to raster graphics after vector graphics, raster graphics to vector-based identification and comparison provides efficient algorithms. In this paper, visual object-oriented development tools, Visual C + +6.0 and AutoCAD platform-based Object ARX software with full

5、support for the development of applications using Visual C + + language can be easily and efficiently develop a typical Windows-style CAD application, the use of parametric design ideas on the design process all the steps are repeated by the program to complete, thereby greatly enhancing the drawing

6、 speed, while convenient for graphic editing and manipulation of polygons in this paper, the simplification process and its simplification rules, proposed similar polygons description of the factors, and these factors combined gives a formula for calculating similarity thus proposed a new idea, expe

7、rimental results show that the method is simple and effective.Keyword Similarity; polygon; ObjectARX and Visual C + +; concave polygon目 录1. 绪论71.1 相似度的应用背景71.2 开发工具82.工具的介绍112.1 ObjectARX 功能说明112.3 ObjectARX 类库122.3.1 AcDb 库132.4 ObjectARX 数据库132.5 ObjectARX 实体对象143. 多边形163.1 凸多边形定义163.2 凸多边形判别方法163

8、.3 凹多边形的定义173.4 凹多边形的判别方法173.5 简单多边形凸凹顶点的识别183.6 简单多边形方向性的识别方法203.7 利用极点顺序的多边形顶点凹凸性判别算法224.凹多边形相似度的分析234.1 三角形的相似度234.2 多边形的相似度264.2.1 凸多边形相似度274.2.2 凹多边形相似度284.3 向量相似度295. 程序设计356. 结束语387. 源程序（见附录）39凹多边形相似度大小的判别与实现102201240 张旺 指导教师 陈志远 讲师 1.绪论1.1 相似度的应用背景 相似性是最常用的、但又不确定的概念之一就人的感知而言，物体的所有可视特征都是识别物体的

9、依据但对机器视觉而言，大多数情况下，仅物体的几何形状被利用。因此，对多边形的研究具有普遍意义图像在多边形近似后，对它的表示和描述是决定其特征是否易于利用的重要方面，它与识别的关系密不可分对多边形的描述可以采用通用的傅里叶算子、链码、局部曲率值等方法，也可以为特定的用途采用其他方法多边形的识别已有多种不同的方法提出，主要算法是从模板图形和对比图形中分别抽取一系列的特征值构成特征矢量，然后依据最小均方误差准则判别它们是否相近。 两个轮廓的相似度量有基于轮廓上的点的相似度量 和基于角和边的相似度量。本文提出了多边形的三角形划分、三角形弱划分、保角划分的概念和基于这些划分的多边形相似度量的新方法。图像

10、识别，是利用计算机对图像进行处理、分析和理解，以识别各种不同模式的目标和对像的技术。地理学中指将遥感图像进行分类的技术。图形刺激作用于感觉器官，人们辨认出它是经验过的某一图形的过程,也叫图像再认。在图像识别中,既要有当时进入感官的信息,也要有记忆中存储的信息。只有通过存储的信息与当前的信息进行比较的加工过程，才能实现对图像的再认。人的图像识别能力是很强的。图像距离的改变或图像在感觉器官上作用位置的改变，都会造成图像在视网膜上的大小和形状的改变。即使在这种情况下，人们仍然可以认出他们过去知觉过的图像。甚至图像识别可以不受感觉通道的限制。例如，人可以用眼看字，当别人在他背上写字时，他也可认出这个字

11、来。 矢量化，计算机中显示的图形一般可以分为两大类矢量图和位图。矢量图使用直线和曲线来描述图形，这些图形的元素是一些点、线、矩形、多边形、圆和弧线等等，它们都是通过数学公式计算获得的。例如一幅花的矢量图形实际上是由线段形成外框轮廓，由外框的颜色以及外框所封闭的颜色决定花显示出的颜色。由于矢量图形可通过公式计算获得，所以矢量图形文件体积一般较小。矢量图形最大的优点是无论放大、缩小或旋转等不会失真；最大的缺点是难以表现色彩层次丰富的逼真图像效果。Adobe公司的Illustrator、Corel公司的CorelDRAW是众多矢量图形设计软件中的佼佼者。大名鼎鼎的FlashMX制作的动画也是矢量图形

12、动画。 1.2 开发工具 关于AutoCAD应用广泛重要性 CAD，即Computer Aided Design,是指以计算机为辅助手段完成整个产品设计过程。AutoCAD是美国Autodesk公司开发的通用计算机辅助绘图、设计系统，引起强大的功能，使用上的便利以及良好的开放性，是世界上最为流行的通用CAD平台。在国内应用非常广泛，影响深远，尤其是在建筑和机械行业，拥有强大的应用和开发队伍，几乎家喻户晓，堪称我国的CAD平台。从1982年推出的AutoCAD R1.0到1997年7月推出的AutoCAD R14 for Windows 95/NT，其界面和风格都经历了很大的变化，其中二次开发技

13、术的不断更新更是令人注目。 关于开发工具ObjectARXObjectARX是一个以C+语言为基础的面向对象的开发环境和应用程序接口，开发人员可以利用这个接口使用、修改和扩展AutoCAD。用VC+语言编写的程序经过编译、链接，最后生成ObjectARX应用程序。ObjectARX应用程序是一个分享AutoCAD的地址空间，并可以对AutoCAD直接调用的动态链接库。采用可扩展性思想实处的ObjectARX库，库中包含了用于定义新类的宏，提供了对已存在库中的类进行实施添加新功能的能力。此外，为了使开发者能根据自己的需要和能力选择开发工具，ObjectARX库提供了与ADS、AutoLISP应用

14、程序相链接的接口。ObjectARX库中有各种各样的系列工具，开发人员可通过AutoCAD的开放结构，直接对AutoCAD的数据结构，图形系统和内部命令进行操作。 Vc开发工具C+这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“C plus plus”，“CPP”。 它是一种使用非常广泛的计算机编程语言。C+是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。我们使用Visual C+6.0软件作为三维透视图的开发工具。Visual C+语言是一种面向对象的程序设计语言，同时

15、也是对C语言的扩展，它继承了C语言功能丰富、表达能力强、使用灵活、目标程序高效率高、可移植性好等的特性，同时融合了面向对象的能力，支持面向对象的程序设计。Visual C+代表了基于Windows的C+语言产品，它集成了传统的编程工具，也集成了Windows中的特殊工具箱，如MFC(微软基本类库)。MFC类库为我们提供了丰富的类资源，特别是MFC类库中绘图类提供了几乎所有的绘图函数，功能非常全，为我们进行图形设计提供了丰富的手段。由于Visual C+突出的优点，使得它在计算机绘图领域得到了广泛使用。用Visual C+语言进行绘图程序设计具有明显的优越性。一般图形都有层次结构，任何复杂的图形

16、均可用简单图素描述。而C+语言具有指针、结构等的丰富的数据类型，同时它的面向对象程序设计方法使图素模块之间的关系变得更加清晰，便于对图形进行修改、删除、插入等操作。 下图1-2是Visual C+软件的开发环境。 图1-2 Visual C+ 6.0的开发环境2.工具的介绍2.1 ObjectARX 功能说明ObjectARX 开发环境提供了一个面向对象的C+应用程序接口，开发人员可以利用接口使用，修改和扩展AutoCAD。用VC+语言编写的程序经过翻译、链接，最后生成 ObjectARX 应用程序。ObjectARX 应用程序是一个分享AutoCAD 的地址空间、并可对AutoCAD 直接调

17、用的动态链接库。采用可扩展性思想设计出的ObjectARX 库，库中包含了用于定义新类的宏，提供了对已存在库中的类进行实时添加新功能的能力。此外，为了使开发者能根据自己的需要和能力选择开发工具，ObjectARX 库提供了与ADS、AutoLISP应用程序相链接的接口。ObjectARX 库中有各种各样的系列工具，开发人员可以通过 AutoCAD 的数据结构、图形系统和内部命令进行操作。2.2 ObjectARX 与 Visual C+ObjectARX 是 Visual C+ 的子集，ObjectARX 并不是独立的开发平台，而是运行于 Visual C+ 平台之上。在前面的简介当中已经涉及

18、了 ObjectARX 与 Visual C+ 的关系。ObjectARX 是一个以C+语言为基础的面向对象的开发环境和应用程序接口。ObjectARX 程序本质上为Windows动态链接库（DLL）。ObjectARX 作为Visual C+的动态链接库与其他的动态链接库有着很大的区别。Visual C+当中的其他动态链接库都是严格以C+语言为基础，作为Visual C+ 的一个模块程序。而ObjectARX 程序在 C+语言的基础上规定了自己的语法，它是专门用来对 AutoCAD 进行二次开发的工具。因此说 ObjectARX 是 Visual C+ 的一个子集。 2.3 ObjectAR

19、X 类库通常，ObjectARX 提供如下一些库 （1）AcRx 库，该库用于连编应用程序及运行时类注册和标识的类。 （2）AcEd 库，该库用于注册本地命令及系统事件通知的类。（3） AcDb 库，该库用于AutoCAD 数据库类（存放所有的实体及其他类型）。（4） AcGi 库，该库用于渲染 AutoCAD 实体的图形接口。（5） AcGe 库，该库用于普通线性代数和几何实体通用库。（6） ADSRX 库，该库用于创建AutoCAD 应用程序的C语言库， ObjectARX 应用程序用这个来实现实体选择、选择操作和获取数据。2.3.1 AcDb 库 AcDb 库的内容较多，它包含了所有的符

20、号表，如线性、层、文本样式、尺寸样式等。每一个AutoCAD 数据库都有一个有名对象字典AcDbDictionary ，可以用来存放图形文件中的用户数据。有名对象字典是该库的一部分，AutoCAD 各实体也是这样。正如前面所见，它可以对AutoCAD 编辑器做出响应，也可以响应发生在AutoCAD 数据库中对象之间的事件。该库提供的主要类有：AcDbObject 类负责打开和关闭对象及向AutoCAD 数据库添加对象。AcDbDictionary 类允许向数据文件中添加用户数据，在数据字典中几个重要的条目是 AutoCAD的“groups”和“mline”样式。 符号表从其名称就可以知道他们所

21、包含的内容，最主要的大概要算AcDbBlockTable 了。所有的AutoCAD 实体都是存放在这个表中的。AcDbBlockTable 中最主要的两条记录是*MODEL_SPACE记录和*PAPER_SPACE记录。AutoCAD 数据库中所有的实体都属于这些记录中的一条。块的定义也存放在AcDbBlockTable 中。 最后，AutoCAD中的每一个实体都是从AdDbEntity中派生出来的，用户也可以从AdDbEntity中派生出自己的实体。2.4 ObjectARX 数据库 一个AutoCAD 图形是储存于一个数据库中对象的集合。一些基本的数据库对象是实体、符号表和字典，如图2-4

22、 AutoCAD数据库关键组件 所示。在数据库中的每个对象均有一个句柄，这个句柄对于特定图形的上下文之间是惟一的识别标志。在一个AutoCAD 图形中，实体是一种特别的数据库对象，它具有图形表示，例如直线、圆、文本、三维实体、面域、样条曲线和椭圆。用户可以在屏幕上看见一个实体并可以操作它。 图形数据库块表层表其他符号命名字典块表记录层表记录符号记录表对象实体图2-4 AutoCAD数据库关键组件 符号表和字典是用来保存数据库对象的容器，两个容器对象映射一个数据库对象的一个符号名，该符号名为一个文本字符串。一个AutoCAD 数据库包括一个固定的符号表集，每个符号表均包含一个特定的符号表记录类的

23、实例。用户不能向数据库添加一个新的符号表。符号表实例是层表（AcDbLayerTable）和块表（AcDbBlockTable）的结合，层表中包含有层表记录，块表中包含有块表记录。所有的AutoCAD 实体均为块表记录所有。2.5 ObjectARX 实体对象一个实体是一个具有图形表示的数据库对象。实体包括直线、圆、圆弧、文本、面域、三维实体、样条曲线和椭圆等。AcDbEntity类是由ObjectARX类派生而来的。除了少数例外，实体一般包括所有必要的几何信息，少数实体还包括其他具有几何信息或属性的对象。图 2-5 显示了数据库实体的所有关系。AcDbDatabaseAcDbBlockTab

24、leAcDbBlockTableRecordAcDbBlockBeginAcDbEntityAcDbBlockEndAcDbxxx Vertex orAcDbFaceRecord orAcDbAttributeAcDbSequenceEnd图 2-5 显示了数据库实体的所有关系。3.多边形 由三条或三条以上的线段首位顺次连接所组成的封闭图形叫做多边形。按照不同的标准，多边形可以分为正多边形和非正多边形、凸多边形及凹多边形等。 3.1 凸多边形定义 凸多边形又可称为平面多边形，是多边形中的一种，与凹多边形相对，一般在中学阶段对多边形的学习只涉及凸多边形。所谓凸多边形，就是把一个多边形任意一边向两

25、方无限延长成为一条直线，如果多边形的其他各边均在此直线的同旁，那么这个多边形就叫做凸多边形，也可以理解为通过凸多边形的任意一条边作平面，并与此多边形所在的平面相异，那么凸多边形的其他所有部分都在所作平面的同一侧。如图所示，多边形ABCDEF，把线段AF向两方无限延长，此多边形的其他各边AB、BC、CD、DE、EF均在此直线的同旁，所以多边形ABCDEF是凸多边形。凸多边形包含三角形和平面四边形。3.2 凸多边形判别方法1凸多边形的内角均小于180，边数为n（n为整数且n大于2）的凸多边形内角和为（n2）180，但任意凸多边形外角和均为360，并可通过反证法证明凸多边形内角中锐角的个数不能多于3

26、个。2凸多边形所有对角线都在内部，边数为n的凸多边形对角线条数为n（n3）/2，其中通过任一顶点可与其余n3个顶点连对角线。（如下图3-2所示。） 图3-23.3 凹多边形的定义 凹多边形(Concave Polygon):至少有一个优角(Reflexive Angle)的多边形。把一个各边不自交的多边形任意一边向两方无限延长成为一直线，如果多边形的所有边中只要有一条边向两方无限延长成为一直线时，其他各边不在此直线的同旁，那么这个多边形就叫做凹多边形。凹多边形有一个或多个内角大于180度。3.4 凹多边形的判别方法凹多边形的内角和的解，其实我们可以通过（n-2）180来计算。实际上是把大于平角

27、的角划分为两个角（如下图3-3所示）任意一个凸（或凹）N多边形，都可分画为N-2个三角形，因此凹多边形的内角和，也适用（N-2）180这个公式理由是：（1）先把凹多边形画分成N-2个三角形（2）每个三角形的内角和为180度图3-33.5 简单多边形凸凹顶点的识别对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究，对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设多边形方向后判断的重复判断思路，使得算法原理简单明了，实现过程容易。本算法采用C+语言、Visual Basic语言混合编程、Visual Basic 6O演示输出结果。实际运行表明，该算法快捷，运行稳定。对由拓扑映射

28、关系确定多边形顶点凸凹性的算法进行深入研究，对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设多边形方向后判断的重复判断思路，使得算法原理简单明了，实现过程容易。本算法采用C+语言、Visual Basic语言混合编程、Visual Basic6.0演示输出结果。对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究，对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设多边形方向后判断的重复判断思路，使得算法原理简单明了，实现过程容易。本算法采用C+语言、Visual Basic语言混合煽程、Visual Basic 6O演示输出结果。实际运行表明，该算法快捷，运行稳

29、定。为了预测材料内含有裂纹时的性能M. Kacha-nov等人用细观力学理论建立了一系列的力学模型，使得当材料中含有圆型、椭圆型、环形等规则形状裂纹时材料的性能预测成为可能。事实上，材料中的裂纹在通常情况下其形状是相当不规则的。CSforecast是针对材料内含有不规则形状裂纹时，为预测其性能而升发的软件。它所依据的是MKachanov的含不规则形状裂纹的弹性柔度估算理论。在对不规则形状裂纹的处理过程中，由于要对裂纹形状进行一系列的分形处理，如对由裂纹构成的多边形的凸凹性及顶点的凸凹性进行频繁的判断，因而，研究快速、实用的算法非常必要。国内外学者对此进行了大量的研究，归结起来其判别方法主要有角

30、度法、凸包法以及位置关系法等。角度法是通过逐个计算多边形各顶点的内角，比较内角与的大小来判别顶点的凸凹性。由于求取每一个顶点的角度需要计算三角函数，从而使得计算速度较慢，效率低下且易出现奇异值，实用性较差。凸包法采用分层求凸包的方法交替地筛选出凸点和凹点，该算法的基础为复杂的凸包计算。位置关系法实质上是计算矢量叉积来确定多边形顶点的凸凹性，这种算法虽然实现简单，但计算行列式要涉及若干次乘法运算，计算量较大。通过拓扑映射，把识别顶点凹凸性的问题转换为判断映射点在映射线上的位置关系问题，为多边形顶点的凹凸性判断开拓了一种新的思路。但由于文献(51采用了先假设后检验的方式，各个顶点要进行二次检验，存

31、在着大量的重复计算，使得算法的实现效卒有所降低。本文充分考虑了简单多边形的方向性与顶点凹凸性的联系，根据极值顶点的性质预先确定多边形的方向，对多边形的走向首先进行预处理，用“多边形方向性的判别规则”判断多边形的方向，经判断如其为顺时针方向则按逆序排列顶点数据，使多边形的方向始终为逆时针方向再通过多边形顶点的坐标确定其拓扑映射点的具体位置。结合以上两方面对顶点的凹凸性作出判断，从而避免了大量的重复计算经过验证，其实现过程简单、效率明显提高、运行稳定可靠。3.6 简单多边形方向性的识别方法给定一个简单多边形，其顶为Pl一（砥，y；），l-I，2，3，n，P。+- Pl，它的方向是逆时针的还是顺时针

32、的，对于判别顶点的凸、凹性起决定性的作用。因而要确定顶点的凸、凹性，首先必须要判别它的方向。具体做法是：先求出给定多边形的四个极值顶点（由定理知极值顶点为凸硬点），使该多边形落人由极值顶点构成的矩形区域内，然后跟据该多边形在每个极值点处与相邻两顶点的位置关系来确定该多边形的方向。 多边形每个顶点凹凸性的判别，是在多边形方向已确定的基础上进行。对于简单多边形P1，P2，Pn，判断顶点Pi(1fn)凹凸性的方法是，取其前后相邻两顶点Pi-1 Pi+与其构成一个三角形Pi-iPPi+i (PO=Pn，Pn+l=P1)，如果该三角形的方向与简单多边形的方向一致，则顶点Pi为凸项点，若相反则顶点Pi为凹

33、项点。对于三角形方向的确定可以采用和多边形方向确定类似的方法，找出其4个极点最左点Pa，最右点Pb，最下点Pe，最上点Pd。此时口、6、c、d的4个值有以下两种情况。(1)口、6、c、d其中有且仅有两个值相等此时可按照表所列规别对三角形方向进行判别。(2)口、6、c、d其中有两对值相等（a-c，b=d或者口=Z 6=c）在此种情况下，将最左或最右极点（不妨取最左点）变换为边PaPb的中点M，M点的x，y坐标分别为Pa和Pb相应坐标和的一半，用M点替换最左点显然也不会改变三角形的方向，进而对新三角形进行方向判别，如图3-6所示。图3-63.7 利用极点顺序的多边形顶点凹凸性判别算法提出一种根据多

34、边形各个极点在顶点序列中的先后顺序确定多边形方向的算法。对于多边形顶点凹凸性的判别，提出通过确定某个顶点与其相邻两顶点构成三角形的方向，进而利用多边形方向与该三角形方向是否相同而确定该顶点凹凸性的方法。该算法包括了点包含的判别。试验表明，该算法不合乘法运算，使运算高效稳定。筒单多边形的方向、顶点凹凸性及点包含的判别，是计算机图形学中的一个基本问题，由于在模式识别、图像处理和地理信息等众多领域都有广泛的应用，所以判别方法的效率和稳定性具有重要的研究价值。对此不少学者做了许多研究，提出了多种判别方法。总的来说对简单多边形方向的确定主要有有向面积法和叉积法，但都要进行3阶行列式的计算，缺点是计算量较

35、大。对顶点凹凸性的判别方法较多，有角度法、有向面积法、叉积法、拓扑映射法以及基于边向量斜率比较的方法等，但这些方法也都要进行耗时较多的乘法运算。对点包含的判别方法主要有射线法和标号法。作者提出一种基于极点顺序对多边形顶点凹凸性进行判别的新算法，可以在没有乘法运算的情况下，仅通过判断运算就可确定多边形方向，进而可判断出顶点的凹凸性以及点与多边形的包含关系。如图3-7所示。图3-74.凹多边形相似度的分析4.1 三角形的相似度 对应角相等，对应边成比例的两个三角形叫做相似三角形。（similar triangles）互为相似形的三角形叫做相似三角形。例如下图4中，若BC/BC，那么角B=角B，角B

36、AC=角CAB，是对顶角，那么我们就说ABCABC 图4-1取论域U = (A，B，C)|A+B+C=，A、B、C是三角形的三内角。把等腰三角形、直角三角形、等边三角形分别记作I(ABC)、R(ABC)、E(ABC)简记J，R、E。首先讨论一个给定三角形与特殊三角形J、R、E的相似度量问题，然后给出两个任意三角形的相似度量。 近似等腰三角形、近似直角三角形及近似等边三角形分别是论域U上的一个模糊子集，分别记作I(ABC)、R(ABC)、E(ABC)；简记I、R、E。I，R，E中的元素对I ，R，E的相似度量记作I(ABC)、R(ABC)和E(ABC)，它们的相似度量规定为I(ABC)=1一(3

37、)min|A B|，|B C|，|C A|)；ABC I,R(ABC)=1一(2)min|A 一,2|，|B 一,2|，|C一 2|ABC RE(ABC)= 1一(1)max|A B|，|B C|，|C A|；ABC E给定任意两个三角形x，y，其中：x的三个内角为A 、B、 C；y的三个内角为A、 B 、C ，X 和y的相似度量为(x，y )=maxP 1一( 1)max|A 一 A|，|B 一 B|，|C C|或( x，y)=maxP21一(02)max|A 一 A|+|B 一 B|+|C C|其中，P ，是待定常数。Pi一6，即有6种可能：X = A ，Y= B ，Z=C 或X =A ，

38、Y=C ，Z=B 或X=B ，Y= A ，Z=C 或X = B ，Y= c，Z= A 或X =C ，Y=B ，Z=A 或X = C ，Y= A ，Z=B 。对于任意两个三角形，如果A Bc，A B c 那么(x，y )=1一( 1)max|A 一 A|，|B 一 B|，|C C|或(x，y )= 1一(2 )max|A 一 A|+|B 一 B|+|C C|因为对于任意两个三角形的三个内角，如果A B C，A” B” C” 那么max|A A|，|B B|，|CC|=23max|A A| |B 一 B|C C|=43所以为使01 1，02 1令1=32， 2=34 这样得到任意两个三角形(AB

39、C， A”B”C” )的相似度量为I(x，y )=1一(32)max|A A|+|B B|+|C C|)或( x，y )=1一(34)max|A A|+ |B B|+ |C C|4.2 多边形的相似度由三角形的相似我们不难看出，如果两个多边形的对应角相等，对应边成比例，那么这两个或多个多边形叫相似多边形也称为多边形的相似度准则。设B一x|x是多边形; C一y|y是正多边形 ；D 一z|z是某一多边形i的顶点；E一e|e是对应多边形完全图的边；关系“ 是按顺时针排列，“”是按逆时针排列。定义l 设aB，则y-对关系 ”是一个偏序集，V y-。我们把顶点 叫问隔顶点对，三个顶点形成的三角形记作x。

40、定义2 设aB，eE，使得e与问隔顶点对相关连，进而得到一个三角形集合P=x1，x2xixm如果满足下列三个条件：(1)Vx，yP，i j，有：xy=（2）的每条边是x中的一条边；(3)Ux ，=a一a，a，a B且不包含口的边，则集合P=x1，x2xixm对“ 构成一个偏序集，叫多边形的三角形划分定义3 定义2中，如果不满足条件(2)，(3)且 有一条边是中的边，则称这样的P叫多边形的弱划分；记作Pr。定义4 设aB，把a看成一个图，加入使得a的每一个顶点的度为4的边，把以每顶点形成的三角形集合记作PA=x1，x2xixm，PA对“ 形成的偏序集称a的保角划分。由定义2和定义4得知P和PA存

41、在一定关系，后面再加以说明。图4-2定义1、2、3、4的图解见图4-2。其中：a1a3，a2a4是两个间隔顶点对。P=a1a2a3 ，a3a4a5，a5a6a1是图4-2(a)多边形的一个划分。 P=a1a2a3 ，a3a4a5是图4-2(b)正多边形的一个弱划分。PA =a1a2a3 ，a2a3a4，a3a4a5，a4a5a6，a5a6a7，a6a7a1，a7a1a2是图4-2(c)多边形的一个保角划分。 划分的概念是针对边为偶数的多边形，弱划分是针对边为奇数的正多边形，而保角划分是针对边为任意的多边形。在定义2、3、4中P、 P、PA是多边形的正解；若使P、 P、PA对“ ”形成偏序集，则

42、得到多边形的镜像解(所谓镜像解就是从反方向看一物体所形成的像)。4.2.1 凸多边形相似度对于两个凸多边形，假如我们称它们是相似的，如果满足以下条件： 角对应相等 边对应成比例全等凸多边形就是对应边相等且角对应相等的特殊相似凸多边形。当然只要满足上述其中任何一个，那么该种凸多边形也相似。如下图4-2-1所示。 图4-2-14.2.2 凹多边形相似度对于两个凹多边形，当对应边成比例时，如下图4-2-2所示，它们并不相似，甚至区别很大，所以说对于凹多边形，不仅需要对应边成比例而且还得对应角相等。也就是说 边长角度=K 这一变量取决于该凹多边形是否相似。 图4-2-24.3 向量相似度凹多边形相似度

43、，可以完全转化为两个向量之间的相似度。而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算。 事实上，这种表示方法压缩了字符串，用每个字符出现的次数代替了字符串本身，损失了字符出现的位置信息。因此，对于同一个消息，如果只调换了字符顺序的话，通过这种方式计算出的消息指纹不变。但实际情况中，这种情况往往出现较少。 （一个极端的例子 。是“喜欢”和“欢喜”）3.3.2 最短编辑距离 最短编辑距离是一个经典的概念。对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作。两个字符串的最短编辑距离是指把一个字符串变为另外一个字符串需要的最少操作次数。 求解最小编辑距离是一个可以用动态规

44、划方法解决的经典问题 。基于距离的计算方法1. 欧氏距离(Euclidean Distance) 欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：(3)两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的欧氏距离：也可以用表示成向量运算的形式：(4)Matlab计算欧氏距离Matlab计算距离主要使用pdist函数。若X是一个MN的矩阵，则pdist(X)将X矩阵M行的每一行作为一个N维向量，然后计算这

45、M个向量两两间的距离。例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离X = 0 0 ; 1 0 ; 0 2D = pdist(X,euclidean)结果：D = 1.0000 2.0000 2.23612. 曼哈顿距离(Manhattan Distance) 从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源， 曼哈顿距离也称为城市街区距离(City Block distance)。(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离(2)两个n维向量a(x11,x12,x1n)与 b(x21,x22,x2n)间的曼哈顿距离(3) Matlab计算曼哈顿距离例子：计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离X = 0 0 ; 1 0 ; 0 2D = pdist(X, cityblock)结果：D = 1 2 35. 标准化欧氏距离 (Standardized Euclidean distance )(1)标准欧氏距离的定义标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案