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

1 郑州航空工业管理学院 毕 业 论 文（设 计） 2013 届 机械制造与自动化 专业 1022012 班级 题 目 凹多边形相似度大小的判别与实现 姓 名 张旺 学号 10221240 指导教师 陈志远 职称 副教授 二 一 三 年 5 月 20 日 2 内 容 摘 要 凹多边形作为简单凸多边形和复杂多边形的过度 桥梁，其相似度的判别准则和识别算法的合理性，能有效地解决图形智能识别的关键问题，不但对矢量图形，而且也可将光栅图形转化为矢量图形后， 为基于光栅图形的矢量化识别与比较提供高效的算法。 本文利用可视化的面向对象开发工具 Visual C+6.0 和基于 AutoCAD 平台的 Object ARX 软件饱满的支持而开发的应用程序，借助 Visual C+语言能方便高效地开发典型 Windows风格的 CAD应用程序，采用参数化设计的思想，把设计过程中重复出现的步骤全部由程序来完成，这样大大提高了绘图速度，同时方便了编辑和操作本 文结合图文中多边形的化简过程与其化简规则，提出了多边形相似性描述的因子，并结合这些因子给出了一个计算相似度的公式，从而提出了一个新的思路，实验结果表明，该方法简单有效。 关键词 相似度 ； 多边形 ； ObjectARX 与 Visual C+；凹多边形 3 Similarity discriminant concave polygon size and Implementation Author Zhangwang Tutor Chen zhiyuan lecturer Abstract Content Abstract Concave 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 graphics, 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 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 speed, while convenient 4 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, experimental results show that the method is simple and effective. Keyword Similarity； polygon； ObjectARX and Visual C + +； concave polygon 5 目 录 1. 绪论 . 7 1.1 相似度的应用背景 . 7 1.2 开发工具 . 8 2.工具的介绍 . 11 2.1 ObjectARX 功能说明 . 11 2.3 ObjectARX 类库 . 12 2.3.1 AcDb 库 . 13 2.4 ObjectARX 数据 库 . 13 2.5 ObjectARX 实体对象 . 14 3. 多边形 . 16 3.1 凸多边形定义 . 16 3.2 凸多边形判别方 法 . 16 3.3 凹多边形的定义 . 17 3.4 凹多边形的判别方法 . 17 3.5 简单多边形凸凹顶点的识别 . 18 3.6 简单多边形方向性的识别方法 . 20 3.7 利用极点顺序的多边形顶点凹凸性判别算法 . 22 4.凹多边形相似度的分析 . 23 4.1 三角形的相似度 . 23 4.2 多边形的相似度 . 26 6 4.2.1 凸多边形相似度 . 27 4.2.2 凹多边形相似度 . 28 4.3 向量相似度 . 29 5. 程序设计 . 35 6. 结束语 . 38 7. 源程序（见附录） . 39 7 凹多边形相似度大小的判别与实现 102201240 张旺 指导教师 陈志远 讲师 1.绪论 1.1 相似度的应用背景 相似性是最常用的、但又不确定的概念之一就人的感知而言，物体的所有可视特征都是识别物 体的依据但对机器视觉而言，大多数情况下，仅物体的几何形状被利用。因此，对多边形的研究具有普遍意义 图像在多边形近似后，对它的表示和描述是决定其特征是否易于利用的重要方面，它与识别的关系密不可分对多边形的描述可以采用通用的傅里叶算子、链码、局部曲率值等方法，也可以为特定的用途采用其他方法多边形的识别已有多种不同的方法提出，主要算法是从模板图形和对比图形中分别抽取一系列的特征值构成特征矢量，然后依据最小均方误差准则判别它们是否相近。 两个轮廓的相似度量有基于轮廓上的点的相似度量 和基于角和边的相 似度量。本文提出了多边形的三角形划分、三角形弱划分、保角划分的概念和基于这些划分的多边形相似度量的新方法。 图像识别 ，是利用 计算机 对图像进行处理、分析和理解，以识别各种不同模式的目标和对像的技术。地理学中指将遥感图像进行分类的技 8 术。 图形刺激作用于 感觉器官 ，人们辨认出它是经验过的某一图形的过程 ,也叫 图像 再认。在图像识别中 ,既要有当时进入感官的信息 ,也要有记忆中存储的信息。只有通过存储的信息与当前的信息进行比较的加工过程，才能实现对图像的再认。 人的图像识别能力是很强的。图像距离的改变或图像在感觉器官上作用位置的改变，都会造成图像在 视网膜 上的大小和形状的改变。即使在这种情况下，人们仍然可以认出他们过去知 觉过的图像。甚至图像识别可以不受感觉通道的限制。例如，人可以用眼看字，当别人在他背上写字时，他也可认出这个字来。 矢量化， 计算机中显示的图形一般可以分为两大类 矢量图 和 位图 。 矢量图 使用直线和曲 线来描述图形，这些图形的元素是一些点、线、矩形、多边形、圆和弧线等等，它们都是通过数学公式计算获得的。例如一幅花的 矢量图形 实际上是由线段形成外框轮廓，由外框的颜色以及外框所封闭的颜色决定花显示出的颜色。由于 矢量图形 可通过公式计算获得，所以 矢量图形文件 体积一般较小。 矢量图形 最大的优点是无论放大、缩小或旋转等不会失真；最大的缺点是难以表现色彩层次丰富的逼真图像效果。 Adobe公司的 Illustrator、 Corel公司的 CorelDRAW是众多矢量图形 设计软件中的佼佼者。大名鼎鼎的 FlashMX制作 的动画也是 矢量图形 动画。 1.2 开发工具 关于 AutoCAD应用广泛重要性 9 CAD，即 Computer Aided Design,是指以计算机为辅助手段完成整个产品设计过程。 AutoCAD是美国 Autodesk公司开发的通用计算机辅助绘图、设计系统，引起强大的功能，使用上的便利以及良好的开放性，是世界上最为流行的通用 CAD平台。在国内应用非常广泛，影响深远，尤其是在建筑和机械行业，拥有强大的应 用和开发队伍，几乎家喻户晓，堪称我国的CAD平台。从 1982年推出的 AutoCAD R1.0到 1997年 7月推出的 AutoCAD R14 for Windows 95/NT，其界面和风格都经历了很大的变化，其中二次开发技术的不断更新更是令人注目。 关于开发工具 ObjectARX ObjectARX 是一个以 C+语言为基础的面向对象的开发环境和应用程序接口，开发人员可以利用这个接口使用、修改和扩展 AutoCAD。用VC+语言编写的程序经过编译、链接，最后生成 ObjectARX应用程序。ObjectARX应 用程序是一个分享 AutoCAD的地址空间，并可以对 AutoCAD直接调用的动态链接库。采用可扩展性思想实处的 ObjectARX库，库中包含了用于定义新类的宏，提供了对已存在库中的类进行实施添加新功能的能力。此外，为了使开发者能根据自己的需要和能力选择开发工具，ObjectARX库提供了与 ADS、 AutoLISP应用程序相链接的接口。 ObjectARX库中有各种各样的系列工具，开发人员可通过 AutoCAD的开放结构，直接对 AutoCAD的数据结构，图形系统和内部命令进行操作。 Vc开发工具 C+这个词在 中国大陆 的 程序员 圈子中通常被读做“ C 加加”，而西 10 方的程序员通常读做“ C plus plus”，“ CPP”。 它是一种使用非常广泛的 计算机编程语言 。 C+是一种静态 数据类型 检查的、支持多重编程范式的通用 程序设计 语言。它支持过程化 程序设计 、 数据抽象 、 面向对象程序设计 、 泛型 程序设计等多种 程序设计风格 。 我们使用 Visual C+6.0软件作为三维透视图的开发工具。 Visual C+语言是一种面向对象的程序设计语言，同时也是对 C 语言的扩展，它继承了 C语言功能丰富、表达能力强、使用灵活、目标 程序高效率高、可移植性好等的特性，同时融合了面向对象的能力，支持面向对象的程序设计。 Visual C+代表了基于 Windows 的 C+语言产品，它集成了传统的编程工具，也集成了 Windows中的特殊工具箱，如 MFC(微软基本类库 )。 MFC类库为我们提供了丰富的类资源，特别是 MFC类库中绘图类提供了几乎所有的绘图函数，功能非常全，为我们进行图形设计提供了丰富的手段。由于 Visual C+突出的优点，使得它在计算机绘图领域得到了广泛使用。用 Visual C+语言进行绘图程序设计具有明显的优越性。一般图形都 有层次结构，任何复杂的图形均可用简单图素描述。而 C+语言具有指针、结构等的丰富的数据类型，同时它的面向对象程序设计方法使图素模块之间的关系变得更加清晰，便于对图形进行修改、删除、插入等操作。 下图 1-2是 Visual C+软件的开发环境。 11 图 1-2 Visual C+ 6.0的开发环境 2.工具的介绍 2.1 ObjectARX 功能说明 ObjectARX 开发环境提供了一个面向对象的 C+应用程序接口，开发人员可以利用接 口使用，修改和扩展 AutoCAD。用 VC+语言编写的程序经过翻译、链接，最后生成 ObjectARX 应用程序。 ObjectARX 应用程序是一个分享 AutoCAD 的地址空间、并可对 AutoCAD 直接调用的动态链接库。采用可扩展性思想设计出的 ObjectARX 库，库中包含了用于定义新类的宏，提供了对已存在库中的类进行实时添加新功能的能力。此外，为了使开发者能根据自己的需要和能力选择开发工具， ObjectARX 库提供了与 ADS、 AutoLISP应用程序相链接的接口。 ObjectARX 库中有各种各样 的系列工具，开发人员可以通过 AutoCAD 的数据结构、图形系统和内部命令进行操作。 2.2 ObjectARX 与 Visual C+ ObjectARX 是 Visual C+ 的子集， ObjectARX 并不是独立的开发 12 平台，而是运行于 Visual C+ 平台之上。在前面的简介当中已经涉及了 ObjectARX 与 Visual C+ 的关系。 ObjectARX 是一个以 C+语言为基础的面向对象的开发环境和应用程序接口。 ObjectARX 程序本质上为 Windows动态链接库（ DLL） 。 ObjectARX 作为 Visual C+的动态链接库与其他的动态链接库有着很大的区别。 Visual C+当中的其他动态链接库都是严格以 C+语言为基础，作为 Visual C+ 的一个模块程序。而ObjectARX 程序在 C+语言的基础上规定了自己的语法，它是专门用来对 AutoCAD 进行二次开发的工具。因此说 ObjectARX 是 Visual C+ 的一个子集。 2.3 ObjectARX 类库 通常， ObjectARX 提供如下一些库 （ 1） AcRx 库，该 库用于连编应用程序及运行时类注册和标识的类。 （ 2） AcEd 库，该库用于注册本地命令及系统事件通知的类。 （ 3） AcDb 库，该库用于 AutoCAD 数据库类（存放所有的实体及其他类型）。 （ 4） AcGi 库，该库用于渲染 AutoCAD 实体的图形接口。 （ 5） AcGe 库，该库用于普通线性代数和几何实体通用库。 （ 6） ADSRX 库，该库用于创建 AutoCAD 应用程序的 C 语言库， ObjectARX 应用程序用这个来实现实体选择、选择操作和获取数据。 13 2.3.1 AcDb 库 AcDb 库的内容较多，它包 含了所有的符号表，如线性、层、文本样式、尺寸样式等。每一个 AutoCAD 数据库都有一个有名对象字典AcDbDictionary ，可以用来存放图形文件中的用户数据。有名对象字典是该库的一部分， AutoCAD 各实体也是这样。正如前面所见，它可以对 AutoCAD 编辑器做出响应，也可以响应发生在 AutoCAD 数据库中对象之间的事件。该库提供的主要类有： AcDbObject 类负责打开和关闭对象及向 AutoCAD 数据库添加对象。 AcDbDictionary 类允许向数据文件中添加用户数据，在数据字典中几个 重要的条目是 AutoCAD 的“ groups”和“ mline”样式。 符号表从其名称就可以知道他们所包含的内容，最主要的大概要算 AcDbBlockTable 了。所有的 AutoCAD 实体都是存放在这个表中的。AcDbBlockTable 中 最 主 要 的 两 条 记 录 是 *MODEL_SPACE 记录和*PAPER_SPACE记录。 AutoCAD 数据库中所有的实体都属于这些记录中的一条。块的定义也存放在 AcDbBlockTable 中。 最后， AutoCAD中的每一个实体都是从 AdDbEntity中 派生出来的，用户也可以从 AdDbEntity中派生出自己的实体。 2.4 ObjectARX 数据库 一个 AutoCAD 图形是储存于一个数据库中对象的集合。一些基本的数据库对象是实体、符号表和字典，如图 2-4 AutoCAD 数据库关键组件 所示。在数据库中的每个对象均有一个句柄，这个句柄对于特定图 14 形的上下文之间是惟一的识别标志。在一个 AutoCAD 图形中，实体是一种特别的数据库对象，它具有图形表示，例如直线、圆、文本、三维实体、面域、样条曲线和椭圆。用户可以在屏幕上看见一个实体并可以操作它。 图 2-4 AutoCAD数据库关键组件 符号表和字典是用来保存数据库对象的容器，两个容器对象映射一个数据库对象的一个符号名，该符号名为一个文本字符串。一个 AutoCAD 数据库包括一个固定的符号表集，每个符号表均包含一个特定的符号表记录类的实例。用户不能向数据库添加一个新的符号表。符号表实例是层表（ AcDbLayerTable）和块表（ AcDbBlockTable）的结合，层表中包含有层表记录，块表中包含有块表记录。所有的 AutoCAD 实 体均为块表记录所有。 2.5 ObjectARX 实体对象 一个实体是一个具有图形表示的数据库对象。实体包括直线、圆、圆弧、文本、面域、三维实体、样条曲线和椭圆等。 AcDbEntity类是由图形数据库 块表 层表 其他符号 命名字典 块表记录 层表记录 符号记录表 对象 实体 15 ObjectARX类派生而来的。 除了少数例外，实体一般包括所有必要的几何信息，少数实体还包括其他具有几何信息或属性的对象。图 2-5 显示了数据库实体的所有关系。 图 2-5 显示了数据库实体的所有关系。 AcDbDatabase AcDbBlockTable AcDbBlockTableRecord AcDbBlockBegin AcDbEntity AcDbBlockEnd AcDbxxx Vertex or AcDbFaceRecord or AcDbAttribute AcDbSequenceEnd 16 3.多边形 由三条或三条以上的线段首位顺 次连接所组成的 封闭图形 叫做多边形。按照不同的标准，多边形可以分为正多边形和非正多边形、 凸多边形 及凹多边形等 。 3.1 凸多边形定义 凸多边形又可称为平面多边形，是 多边形 中的一种，与 凹多边形 相对，一般在中学阶段对多边形的学习只涉及凸多边形。 所谓凸多边形，就是把一个多边形任意一边向两方无限延长成为一条 直线 ，如果多边形的其他各边均在此直线的同旁，那么这个多边形就叫做凸多边形，也可以理解为通过凸多边形的任意一条边作平面，并与此多边形所在的平面相异，那么凸多边形的其他所有部分都在所作平面的同一侧。如图所示，多边形 ABCDEF，把线段 AF 向两方无限延长，此多边形的其他各边 AB、 BC、 CD、 DE、 EF 均在此直线的同旁，所以多边形 ABCDEF是凸多边形。凸多边形包含 三角形 和平面四边形。 3.2 凸多边形判别方法 1凸多边形的 内角 均小于 180，边数为 n（ n 为整数且 n 大于 2）的凸多边形内角 和为（ n 2） 180，但任意凸多边形 外角和 均为360，并可通过反证法证明凸多边形内角中锐角的个数不能多于 3个。 2凸多边形所有 对角线 都在内部，边数为 n的凸多边形对角线条数为 n（ n 3） /2，其中通过任一顶点可与其余 n 3个顶点连对角线。（如 17 下图 3-2所示。） 图 3-2 3.3 凹多 边形的定义 凹多边形 (Concave Polygon):至少有一个优角 (Reflexive Angle)的多边形。 把一个各边不自交的多边形任意一边向两方无限延长成为一直线，如果多边形的所有边中只要有一条边向两方无限延长成为一直线时，其他各边不在此直线的同旁，那么这个多边形就叫做凹多边形。凹多边形有一个或多个内角大于 180度。 3.4 凹多边形的判别方法 凹多边形的内角和的解，其实我们可以通过（ n-2） 180来计算。实 18 际上是把大于 平角 的角划分为两个角（如下图 3-3所示） 任意一个凸（或凹） N多边形，都可分画为 N-2个三角形，因此凹多边形的内角和，也适用 （ N-2） 180这个公式 理由是： （ 1）先把凹多边形画分成 N-2个三角形 （ 2）每个三角形的内角和为 180度 图 3-3 3.5 简单多边形凸凹顶点的识别 对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究，对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设 19 多边形方向后判断的重复判断思路，使得算法原理简单明了，实现 过程容易。本算法采用 C+语言、 Visual Basic 语言混合编程、 Visual Basic 6 O 演示输出结果。实际运行表明，该算法快捷，运行稳定。对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究，对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设多边形方向后判断的重复判断思路，使得算法原理简单明了，实现过程容易。本算法采用 C+语言、 Visual Basic语言混合编程、 Visual Basic6.0演示输出结果。 对由拓扑映射关系确定多边形顶点凸凹性的算法进行深入研究， 对多边形的方向进行预处理，使其按逆时针方向排列，彻底摆脱了先假设多边形方向后判断的重复判断思路，使得算法原理简单明了，实现过程容易。本算法采用 C+语言、 Visual Basic语言混合煽程、 Visual Basic 6 O演示输出结果。实际运行表明，该算法快捷，运行稳定。 为了预测材料内含有裂纹时的性能 M. Kacha-nov 等人用细观力学理论建立了一系列的力学模型，使得当材料中含有圆型、椭圆型、环形等规则形状裂纹时材料的性能预测成为可能。事实上，材料中的裂纹在通常情况下其形状是相当不规则的。 CSforecast是针对材料内含有不规则形状裂纹时，为预测其性能而升发的软件。它所依据的是 M Kachanov的含不规则形状裂纹的弹性柔度估算理论。在对不规则形状裂纹的处理过程中，由于要对裂纹形状进行一系列的分形处理，如对由裂纹构成的多边形的凸凹性及顶点的凸凹性进行频繁的判断，因而，研究快速、实 20 用的算法非常必要。国内外学者对此进行了大量的研究，归结起来其判别方法主要有角度法、凸包法以及位置关系法等。角度法是通过逐个计算多边形各顶点的内角，比较内角与的大小来判别顶点的凸凹性。由于求取每一个顶点的角度需要计算三角函数，从 而使得计算速度较慢，效率低下且易出现奇异值，实用性较差。凸包法采用分层求凸包的方法交替地筛选出凸点和凹点，该算法的基础为复杂的凸包计算。位置关系法实质上是计算矢量叉积来确定多边形顶点的凸凹性，这种算法虽然实现简单，但计算行列式要涉及若干次乘法运算，计算量较大。 通过拓扑映射，把识别顶点凹凸性的问题转换为判断映射点在映射线上的位置关系问题，为多边形顶点的凹凸性判断开拓了一种新的思路。但由于文献 (51采用了先假设后检验的方式，各个顶点要进行二次检验，存在着大量的重复计算，使得算法的实现效卒有所降低。本文充分考虑 了简单多边形的方向性与顶点凹凸性的联系，根据极值顶点的性质预先确定多边形的方向，对多边形的走向首先进行预处理，用“多边形方向性的判别规则”判断多边形的方向，经判断如其为顺时针方向则按逆序排列顶点数据，使多边形的方向始终为逆时针方向再通过多边形顶点的坐标确定其拓扑映射点的具体位置。结合以上两方面对顶点的凹凸性作出判断，从而避免了大量的重复计算经过验证，其实现过程简单、效率明显提高、运行稳定可靠。 3.6 简单多边形方向性的识别方法 给定一个简单多边形，其顶为 Pl一（砥， y；）， l-I， 2， 3， n， 21 P。 + - Pl，它的方向是逆时针的还是顺时针的，对于判别顶点的凸、凹性起决定性的作用。因而要确定顶点的凸、凹性，首先必须要判别它的方向。具体做法是：先求出给定多边形的四个极值顶点（由定理知极值顶点为凸硬点），使该多边形落人由极值顶点构成的矩形区域内，然后跟据该多边形在每个极值点处与相邻两顶点的位置关系来确定该多边形的方向。 多边形每个顶点凹凸性的判别，是在多边形方向已确定的基础上进行。对于简单多边形 P1， P2， Pn，判断顶点 Pi(1 f n)凹凸性的方法是，取其前后相邻两顶点 Pi-1 Pi+与其构 成一个三角形Pi-iPPi+i (PO=Pn， Pn+l=P1)，如果该三角形的方向与简单多边形的方向一致，则顶点 Pi为凸项点，若相反则顶点 Pi为凹项点。 对于三角形方向的确定可以采用和多边形方向确定类似的方法，找出其 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点替换最左点显然也不会改变三角形的方向，进而对新三角形进行方向判 22 别，如图 3-6所示。 图 3-6 3.7 利用极点顺序的多边形顶点凹凸性判别算法 提出一种根据多边形各个极点在顶点序列中的先后顺序确定多边形方向的算法。对于多边形顶点凹凸性的判别，提出通过确定某个顶点与其相邻两顶点构成三角形的方向，进而利用多边形方向与该三角形方向是否相同而确定该顶点凹凸性的方法。该算法包括了点包含的判别。试验表明，该算法不合乘法运 算，使运算高效稳定。 筒单多边形的方向、顶点凹凸性及点包含的判别，是计算机图形学中的一个基本问题，由于在模式识别、图像处理和地理信息等众多领域都有广泛的应用，所以判别方法的效率和稳定性具有重要的研究价值。对此不少学者做了许多研究，提出了多种判别方法。总的来说对简单多边形方向的确定主要有有向面积法和叉积法，但都要进行 3阶行列式的计算，缺点是计算量较大。对顶点凹凸性的判别方法较多，有角度法、 23 有向面积法、叉积法、拓扑映射法以及基于边向量斜率比较的方法等，但这些方法也都要进行耗时较多的乘法运算。对点包含的判别方法主 要有射线法和标号法。作者提出一种基于极点顺序对多边形顶点凹凸性进行判别的新算法，可以在没有乘法运算的情况下，仅通过判断运算就可确定多边形方向，进而可判断出顶点的凹凸性以及点与多边形的包含关系。如图 3-7所示。 图 3-7 4.凹多边形相似度的分析 4.1 三角形的相似度 对应角相等，对应边成比例的两个三角形叫做相似三角形。（ similar triangles）互为相似形的三角形叫做相似三角形。例如下图 4中，若BC/BC，那么角 B=角 B，角 BAC=角 CAB，是对顶角，那么我们就说 ABC ABC 24 图 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 )min|A B|， |B C|， |C A|)； ABC I, R( ABC)=1一 (2 )min|A 一 , 2|， |B 一 , 2|， |C一 2| ABC R E( ABC)= 1一 (1 )max|A B|， |B C|， |C A|； ABC 25 E 给定任意两个三角形 x， y，其中： x的三个内角为 A 、 B、 C； y的三个内角为 A 、 B 、 C ， X 和 y的相似度量为 ( x， y )=max P 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 ， 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 B c， 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 |， |C C |=2 3 max|A A | |B 一 B |C C |=4 3 所以为使 0 1 1， 0 2 1令 1=3 2， 2=3 4 这样得到任意两个三角形 (A B C， A” B” C” )的相似度量为 I( x， y )=1一 (3 2 )max|A A |+|B B |+|C C |) 或 ( x， y )=1一 (3 4 )max|A A |+ |B B |+ |C C | 26 4.2 多边形的相似度 由三角形的相似我们不难看出，如果两个多边形的 对应角相等，对应边成比例，那么这两个或多个多边形叫相似多边形也称为多边形的相似度准则。 设 B一 x|x是多边形 ； C一 y|y是正多边形 ； D 一 z|z是某一多边形 i 的顶点 ； E 一 e|e 是对应多边形完全图的边 ；关系“ 是按顺时针排列，“”是按逆时针排列。 定义 l 设 a B，则 y-对关系 ”是一个偏序集， V y-。我们把顶点 叫问隔顶点对，三个顶点形成的三角形记作 x。 定义 2 设 a B， e E，使得 e与问隔顶点对相关连，进而得到一个三角形集合 P= x1， x2 xi xm如果满足下列三个条件： (1)V x， y P， i j，有： x y= （ 2） 的每条边是 x中的一条边； (3)U x ， =a一 a ， a， a B且不包含口的边，则集合 P= x1， x2 xi xm对“ 构成一个偏序集，叫多边形的三角形划分 定义 3 定义 2中，如果不满足条件 (2)， (3)且 有一条边是中的边，则称这样的 P叫多边形的弱划分；记作 Pr。 定义 4 设 a B，把 a看成一个图，加入使得 a的每一个 顶点的度为 4的边，把以每顶点形成的三角形集合记作 PA= x1， x2 xi xm， PA对“ 形成的偏序集称 a的保角划分。 由定义 2和定义 4得知 P和 PA存在一定关系，后面再加以说明。 27 图 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对“ ”形成偏序集，则得到多边形的镜像解 (所谓镜像解就是从反方向看一物体所形成的像 )。 4.2.1 凸多边形相似度 对于两个凸多边形，假如我们称它们是相似的，如果满足以下条件： 角对应相等 28 边对应成比例 全等凸多边形 就是对应边相等且角对应相等的特殊相似凸多边形。当然只要满足上述其中任何一个，那么该种凸多边形也相似。如下图 4-2-1所示。 图 4-2-1 4.2.2 凹多边形相似度 对于两个凹多边形，当对应边成比例时，如下图 4-2-2所示，它们并不相似，甚至区别很大，所以说对于凹多边形，不仅需要对应边成比例 而且还得对应角相等。也就是说 边长 角度 =K 这一变量取决于该凹多边形是否相似。 图 4-2-2 29 4.3 向量相似度 凹多边形相似度，可以完全转化为两个向量之间的相似度。而向量的相似度通常可以用曼哈顿距离或者余弦距离来计算。 事实上，这种表示方法压缩了字符串，用每个字符出现的次数代替了字符串本身，损失了字符出现的位置信息。因此，对 于同一个消息，如果只调换了字符顺序的话，通过这种方式计算出的消息指纹不变。但实际情况中，这种情况往往出现较少。 （一个极端的例子 。是“喜欢”和“欢喜”） 3.3.2 最短编辑距离 最短编辑距离是一个经典的概念。对一个字符串进行添加一个字符、删除一个字符或修改一个字符定义为进行一次操作。两个字符串的最短编辑距离是指把一个字符串变为另外一个字符串需要的最少操作次数。 求解最小编辑距离是一个可以用动态规划方法解决的经典问题 。 基于距离的计算方法 1. 欧氏距离 (Euclidean Distance) 欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。 (1)二维平面上两点 a(x1,y1)与 b(x2,y2)间的欧氏距离： (2)三维空间两点 a(x1,y1,z1)与 b(x2,y2,z2)间的欧氏距离： 30 (3)两个 n维向量 a(x11,x12, ,x1n)与 b(x21,x22, ,x2n)间的欧氏距离： 也可以用表示成向量运算的形式： (4)Matlab计算欧氏距离 Matlab 计算距离主要使用 pdist 函数。若 X 是一个 M N 的矩阵，则 pdist(X)将 X矩阵 M行的每一行作为一个 N维向量，然后计算这 M个向量两两间的距离。 例子：计算向量 (0,0)、 (1,0)、 (0,2)两两间的欧式距离 X = 0 0 ； 1 0 ； 0 2 D = pdist(X,euclidean) 结果： 31 D = 1.0000 2.0000 2.2361 2. 曼哈顿距离 (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)两两间的曼哈顿距离 32 X = 0 0 ； 1 0 ； 0 2 D = pdist(X, cityblock) 结果： D = 1 2 3 5. 标准化欧氏距离 (Standardized Euclidean distance ) (1)标准欧氏距离的定义 标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧 氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集 X的均值 (mean)为 m，标准差 (standard deviation)为 s，那么 X 的“标准化变量”表示为： 而且标准化变量的数学期望为 0，方差为 1。因此样本集的标准化过程 (standardization)用公式描述就是： 标准化后的值 = ( 标准化前的值 分量的均值 ) /分量的标准差 33 经过简单的推导就可以得到两个 n 维向量 a(x11,x12, ,x1n)与 b(x21,x22, ,x2n)间的标准化欧氏距离的公式： 如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离 (Weighted Euclidean distance)。 (2)Matlab计算标准化欧氏距离 例子：计算向量 (0,0)、 (1,0)、 (0,2)两两间的标准化欧氏距离 (假设两个分量的标准差分别为 0.5和 1) X = 0 0 ； 1 0 ； 0 2 D = pdist(X, seuclidean,0.5,1) 结果： D = 2.0000 2.0000 2.8284 7. 夹角余弦 (Cosine) 有没有搞错，又不是学几何，怎么扯到夹角余弦了？各位看官稍安勿躁。几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。 34 (1)在二维空间中向量 A(x1,y1)与向量 B(x2,y2)的夹角余弦公式： (2) 两个 n 维 样本点 a(x11,x12, ,x1n)和 b(x21,x22, ,x2n)的夹角余弦 类似的，对于两个 n 维样本点 a(x11,x12, ,x1n)和 b(x21,x22, ,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。 即： 夹角余弦取值范围为 -1,1。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值 1，当两个向量的方向完全相反夹角余弦取最小值 -1。 夹角余弦的具体应用可以参阅参考文献 1。 (3)Matlab计算夹角余弦 例子：计算 (1,0)、 ( 1,1.732)、 ( -1,0)两两间的夹角余弦 35 X = 1 0 ； 1 1.732 ； -1 0 D = 1- pdist(X, cosine) % Matlab中的 pdist(X, cosine)得到的是 1减夹角余弦的值 结果： D = 0.5000 -1.0000 -0.5000 5. 程序设计 该部分为图形范围 pt11X=0； pt11Y=0.0； pt11Z=0.0； pt12X=2000； pt12Y=2000； pt12Z=0.0； ads_name First； 36 选定窗口范围 acedSSGet(W,pt11,pt12,NULL,First)； int flag1=FirstAdsLength/2； 分别选取原始图形和待比较图形 for(int i=0；iFirstAdsLength；i+) 选取该集合的直线 ID 号 SearchedIdArray.append(eId)； 选取该子集合的直线 ID，搜索顺序分别从顺时针和逆时针方向进行比较 SearchedIdArray1.append(eId)； 计算边长 LineLength=sqrt(pow(SourcelineendPoint.x-SourcelinestartPoint 计算角度 computerAngleArray(SearchedIdArray)； 计算边长 角度 double jVale=doubleArray.at(j)/AngledoubleArray.at(j)； 计算相似度 computerSimilary()； 原图方向记号 if(wiseFlag=1|wiseFlagCompared=1)/clock wise computer line angle 逆时针方向 if(wiseFlag=0|wiseFlagCompared=0)/counter 37 如下图所示 38 6. 结束语 本文利用可视化的面向对象开发工具 Visual C+6.0和基于AutoCAD 平台的 Object ARX 软件饱满的支持而开发的应用程序，借助Visual C+语言能方便高效地开发典型 Windows风格的 CAD应用程序，采用参数化设计的思想，把设计过程中重复出现的步骤全部由程序来完成，这样大大提高了绘图速度，同 时方便了编辑和操作。 致 谢 本论文是在陈志远老师的精心指导下完成的。在课题的选择，方案制定、课题研究、及论文的撰写过程中都得到了陈志远教老师的指导和帮助，陈志远老师平易近人的风格，渊博开阔的知识，科学谨慎的研究方法，严谨求实的治学态度，敏锐活跃的学术将使我终生受益。在论文完成之际，谨向辛勤培养自己多年的老师致以崇高的敬意和衷心的感谢 ! 感谢在学习过程中给予我极大帮助和支持的同学。衷心感谢我的家人在我求学期间给予我毫无 保留的支持和无微不至的关怀，使我能够全身心地投入到学习去。我所取得的每一分成绩都离不开家人的关心和鼓励。最后，再一次向支持帮助我完成学业的所有人表示感谢。 39 参考文献 1 李长勋 .AutoCAD ObjectARX 程序开发技术：国防工业出版社 .2005 2 崔凤奎 .AutoCAD 基础及开发教程：国防工业出版社 .2001 3 （爱尔兰） Charles MCAuley， AutoCAD2000 ObjectARX 编程指南：机械工业出版社 .2000.4 4 杨国清 . 用 ObjectARX 开发 AutoCAD2000应用程序：人民邮电出版社 .2000 5 赵卫东，柳先辉，卫刚 .CAD 软件二次开发平台实现技术 .计算机辅助设计与图形学学 报 .2003.4 6 郭朝勇等 .AutoCAD 2002定制与开发 .清华大学出版社 .2002.3 7 余承飞，方勇编 .AutoCAD 2000二次开发技术 .北京 :人民邮电出版社 .1999.12 8 王福军，张志民，张师伟 .AUIOCAD 2000环境下 CIVisual C+应用程序开发教程 . 北京希望电子出版社 .2000.6 7. 源程序（见附录） / / ObjectARX defined commands, created by 2013-2-16, , #include StdAfx.h #include StdArx.h #includemath.h #includedbents.h #includemigrtion.h #includegevec3d.h #includegemat3d.h #define PI 3.1415926 40 AcGePoint3dArray intPoints； AcDbObjectIdArray SearchedIdArray； AcDbObjectIdArray SearchedIdArray1； AcDbObjectIdArray FirstIdArray； AcDbObjectIdArray BorderIdArray； AcDbObjectIdArray FirstBordertempIdArray； int CircleFlag=0； int index=-1； int IndexFlag=-1； int wiseFlag=-1； int wiseFlagCompared=-1； int CirNum=-1； AcDbIntArray MinBorderFlagShuzhu； AcGeDoubleArray doubleArray；/line length AcGeDoubleArray AngledoubleArray；/line angle AcGeDoubleArray doubleArray1；/line length AcGeDoubleArray AngledoubleArray1；/line angle AcGeDoubleArray sourceLineAngleArray；/first AcGeDoubleArray comparedLineAngleArray；/others AcGeDoubleArray InOrderDx； int flagcomputeAng=0； /- / This is command SIM, by 2013-2-16, , void CZYsim() #ifdef OARXWIZDEBUG acutPrintf (nOARXWIZDEBUG - CZYsim() called.)； #endif / OARXWIZDEBUG / TODO: Implement the command wiseFlagCompared=-1； int minIndex=-1； ads_point pt11,pt12； 41 pt11X=0； pt11Y=0.0； pt11Z=0.0； pt12X=2000； pt12Y=2000； pt12Z=0.0； ads_name First； acedSSGet(W,pt11,pt12,NULL,First)； long FirstAdsLength； acedSSLength(First,&FirstAdsLength)； acutPrintf(nFirstAdsLength=%d:,FirstAdsLength)； acutPrintf(nPlease select a closed drawings in order!)； int flag1=FirstAdsLength/2； for(int i=0；iFirstAdsLength；i+) AcDbObjectId eId； ads_name en； ads_point pt； if(iflag1) acedEntSel(nSelect an entity in source drawing:,en,pt)； acdbGetObjectId(eId,en)； SearchedIdArray.append(eId)； else acedEntSel(nSelect an entity in object drawing:,en,pt)； acdbGetObjectId(eId,en)； SearchedIdArray1.append(eId)； acedSSFree(First)； acutPrintf(nSearchedIdArray.logicalLength()=%d:,SearchedIdArray.logicalLength()； acutPrintf(nSearchedIdArray1.logicalLength()=%d:,SearchedIdArray1.logicalLength()； for(int i2=0；i2isKindOf(AcDbLine:desc()&(pSourceDrawingObj1-isKindOf(AcDbLine:desc() AcGePoint3d SourcelinestartPoint(0,0,0)； AcGePoint3d SourcelineendPoint(0,0,0)； AcDbLine*pSourceEntity=AcDbLine:cast(pSourceDrawingObj)； SourcelinestartPoint=pSourceEntity-startPoint()；/get source line startPoint 1 SourcelineendPoint=pSourceEntity-endPoint()；/get source line endPoint double LineLength=sqrt(pow(SourcelineendPoint.x-SourcelinestartPoint.x,2)+pow(SourcelineendPoint.y-SourcelinestartPoint.y,2)； doubleArray.insertAt(i2,LineLength)；/compute line length 111 AcGePoint3d SourcelinestartPoint1(0,0,0)； AcGePoint3d SourcelineendPoint1(0,0,0)； AcDbLine*pSourceEntity1=AcDbLine:cast(pSourceDrawingObj1)； SourcelinestartPoint1=pSourceEntity1-startPoint()；/get source line startPoint 1 SourcelineendPoint1=pSourceEntity1-endPoint()；/get source line endPoint double LineLength1=sqrt(pow(SourcelineendPoint1.x-SourcelinestartPoint1.x,2)+pow(SourcelineendPoint1.y-SourcelinestartPoint1.y,2)； doubleArray1.insertAt(i2,LineLength1)；/compute line length 111 acutPrintf(nLineLength=:%fn,LineLength)； acutPrintf(nLineLength1=:%fn,LineLength1)； pSourceDrawingObj-close()； pSourceDrawingObj1-close()； 43 acutPrintf(nflagcomputeAng=:%dn,flagcomputeAng)； computerAngleArray(SearchedIdArray)； for(int j=0；jSearchedIdArray.logicalLength()；j+) double jVale=doubleArray.at(j)/AngledoubleArray.at(j)； sourceLineAngleArray.insertAt(j,jVale)； flagcomputeAng+； acutPrintf(nflagcomputeAng=:%dn,flagcomputeAng)； computerAngleArray(SearchedIdArray1)； for(int j1=0；j1SearchedIdArray1.logicalLength()；j1+) double jVale1=doubleArray1.at(j1)/AngledoubleArray1.at(j1)； comparedLineAngleArray.insertAt(j1,jVale1)； acutPrintf(ncomparedLineAngleArray.at(j1)=:%fn,comparedLineAngleArray.at(j1)； computerSimilary()； AngledoubleArray.setLogicalLength(0)； doubleArray.setLogicalLength(0)； comparedLineAngleArray.setLogicalLength(0)； FirstIdArray.setLogicalLength(0)； SearchedIdArray.setLogicalLength(0)； BorderIdArray.setLogicalLength(0)； FirstBordertempIdArray.setLogicalLength(0)； MinBorderFlagShuzhu.setLogicalLength(0)； intPoints.setLogicalLength(0)； CircleFlag=0； index=-1； IndexFlag=-1； flagcomputeAng=0； 44 void computerAngleArray(AcDbObjectIdArray PassedInSearchedIdArray) for(int i=0；istartPoint()； e1=pLine1-endPoint()； s2=pLine2-startPoint()； e2=pLine2-endPoint()； AcDbLine*pWise1=new AcDbLine()； AcDbLine*pWise2=new AcDbLine()； if(s1=s2) pWise1-setStartPoint(s1)； pWise1-setEndPoint(e1)； pWise2-setStartPoint(s2)； pWise2-setEndPoint(e2)； if(s1=e2) pWise1-setStartPoint(s1)； pWise1-setEndPoint(e1)； pWise2-setStartPoint(e2)； pWise2-setEndPoint(s2)； if(e1=s2) pWise1-setStartPoint(e1)； pWise1-setEndPoint(s1)； 45 pWise2-setStartPoint(s2)； pWise2-setEndPoint(e2)； if(e1=e2) pWise1-setStartPoint(e1)； pWise1-setEndPoint(s1)； pWise2-setStartPoint(e2)； pWise2-setEndPoint(s2)； AcGePoint3d p1s=pWise1-startPoint()； double s1x=p1s.x； double s1y=p1s.y； AcGeMatrix3d mat3d；/move AcGeVector3d vec(-s1x,-s1y,0.0)； mat3d=mat3d.translation(vec)； pWise1-transformBy(mat3d)； pWise2-transformBy(mat3d)； AcGePoint3d p1e； p1e=pWise1-endPoint()； double edx=p1e.x； double edy=p1e.y； double fabsx=fabs(p1e.x)； double fabsy=fabs(p1e.y)； double baseAng=0.0； double RotAng； if(edx0&edy0) baseAng=0.0； RotAng=baseAng-atan2(fabsy,fabsx)； else if(edx0&edy0) RotAng=-0.5*PI； else if(edx=0&edy0) RotAng=-1.5*PI； else if(edx0) baseAng=PI； RotAng=-(baseAng-atan2(fabsy,fabsx)； else if(edx0&edy0) RotAng=0； else if(edy=0&edxtransformBy(mat3dRot)； pWise2-transformBy(mat3dRot)； / acutPrintf(nRotAng=%f:,RotAng)；/computer first line rotated angle AcGePoint3d p2e； p2e=pWise2-endPoint()； 47 double edx2=p2e.x； double edy2=p2e.y； double fabsx2=fabs(p2e.x)； double fabsy2=fabs(p2e.y)； double baseAng2=0.0； double RotAng2； / if(wiseFlag=1|wiseFlagCompared=1)/clock wise computer line angle / if(edx20&edy20) baseAng2=0.0； RotAng2=atan2(fabsy2,fabsx2)*180/PI； else if(edx20&edy20) RotAng2=0.5*PI； else if(edx2=0&edy20) RotAng2=1.5*PI； else if(edx20) baseAng2=PI； RotAng2=(baseAng2-atan2(fabsy2,fabsx2)*180/PI； else if(edx20&edy20&edy20) baseAng2=2*PI； RotAng2=(baseAng2-atan2(fabsy2,fabsx2)*180/PI； else if(edx20&edy20) R