?
?
?
?
《MicroDraw图形控件》
—矢量图形比对模块
?
?
?
算
法
设
计
文
档
?
?
?
?
?
?
?
2012.11
?
?
?
第一部分、运行环境及功能需求
?
此算法模块需要MicroDraw图形控件支持；通过图形控件来调用此模块进行文件比对；
算法模块的库文件为 AsCompareFle.dll 此dll文件需要放在控件的目录下；二次开发主要调用控件的 CompareFile函数来实现比对功能；具体使用方法参见vc6示例工程 CompareFileDeom；
?
?
功能需求文档（见附件 ；用户需求文档）
?
?
第二部分 、算法模型简介
?
算法相关类
?
As_Pt????????????点
As_Vec????????向量????
As_Tran????????矩阵变换
As_Loop????????封闭区域
As_Void_List????????链表
As_Real_List????????实数链表
?
MicroDraw 模型相关类
?
MB_Gemo ????????几何
MB_Dimension????尺寸
MB_Layer????????图层
MB_Drawing????????图形文件
?
比对模块 AsCompareFile相关类
?
MB_Cp_Compare????比较管理类
MB_Cp_Search_Loop 用于搜索loop的类
MB_Cp_Loop????????封闭区域（派生自Asloop）
MB_Cp_Pairloop????配对关系
MB_Cp_Rotate_State????????旋转状态
MB_Cp_Raster_Compare????光栅比对类
?
?
第三部分 、算法实现之－－旋转对齐部分
算法实现步骤：
?
????3.1 . 打开原图和扫描图，初始化比较链表；
在控件内打开cad原图；将原图内的尺寸元素和几何元素分别放入两个链表dimension_list ， origin_list内； 插入扫瞄图，将扫瞄图的元素放入另外一个链表内 scan_list内； 同时创建图层"scan_layer"，将插入进来的扫瞄图元素放到"scan_layer"层上；
?
3.2. 计算外框，寻找封闭区域(loop),；
分别计算原图链表origin_list和扫瞄链表scan_list的最大外框和中心点； 并计算出两个loop链表（mb_cp_search_loop类用来搜索所有封闭区域loop）；origin_loop_list 和 scan_loop_list; 原图和扫瞄图都是由一个或多个封闭区域组成； 每个封闭区域可能由一个或多个几何元素组成；我们将每个封闭区域用一个loop来表示； loop在链表内按照面积从大到小排列，即最外面的loop为链表的头节点； 同时出计算每个loop的面积，周长，最大框；
如下图：loop在链表内顺序为1，2，3，4；
?
3.3. 生成原图loop链表的点阵对象
为了随后的光栅比对，需要先将原图loop生成点阵对象；根据最外框的大小按比例生成； 并对点阵对象进行填充；空白处值为0， 边线值为1， loop内部值为－1， 极值点值为2或3； 比对的时候主要看内部点的重合个数； 对于原图来说，点阵对象仅生成一次；
?
?
?
3.4. 添加扫描loop链表的镜像链表：
?
对于扫描图，需要将其的loop链表进行镜像而生成新的loop链表 scan_mirror_loop_list, 镜像轴为链表最外框的中轴线；
?
3.5.旋转比对，生成loop配对关系：
扫描图每次旋转都生成一个旋转状态rnode_state对象；此对象记录当前的旋转角度、和原图的重合度等信息；注意旋转扫瞄loop链表后还要旋转镜像链表；
?
3. 5.1 初略比对：
将scan_loop_list scan_mirror_loop_list两个链表进行1-360度的旋转；每转一度，得到新的最外框（同时也得到了新的宽度和高度），将得到的宽度和高度和原图的宽度和高度比较； 如果相差超过 1/10； 则初步判断此旋转状态不符合条件；
?
?
3. 5.2 光栅比对求出大概位置：
如果旋转后外框相差较小，则根据当前的角度将扫瞄loop链表转换为点阵图形；生成点阵对象的方式和上面原图生成点阵对象的方式相同； 需要注意的是：需要考虑旋转变换和平移变换； 旋转变换即当前的角度变换，平移变换即当前的rect中心到原图rect中心的变换；将当前点阵对象和原图的点阵对象进行比对；得到内部重合点的个数；记录在旋转状态内；
?
?
3.5.3 分析旋转状态链表；初步得到最优解；
对所有的旋转状态进行排序，得到重合率最大的那个对象；其角度就是我们需要的解；这个角度fit_angle是光栅比对得到的最优解；
?
3.5.4 矢量旋转比对：
对于以上计算得到角度fit_angle； 我们需要进一步的精确比对； 具体思路就是从 fit_angle-1 到 fit_angle＋1，每次加0.1或者0.01，再进行比对，此时比对不需要调用光栅比对算法；仅需要对每个loop的中心点距离和rect的高宽差进行比对；找到误差最小的；
?
3.5.5 loop配对关系的建立
loop的配对是将几何特性相似的loop组成一对；即让每个扫瞄loop都到原图中进行查找和其最相似的loop；算法中我们仅考虑如何过滤几何特征明显不同的loop，剩下的loop再用rect的中心点进行比较，中心点离的最近的loop就是我们要找的配对loop；
过滤方法如下：
?
如果两个loop的rect不相交，则忽略过；
?
如果两个loop的面积相差过大（10%） ，则忽略过；
?
然后寻找最近的loop；
?
到此为止，扫瞄片和原图已经找到最佳的对齐角度；并且生成了原图loop和扫瞄图loop之间的配对关系；
?
?
?
第四部分 、算法实现之－－处理配对关系
在配对关系的链表内；每个配对节点对象(MB_Cp_Paireloop）都可能存在以下三种情况；
?
情形1：扫瞄图中缺少loop：
即配对关系中发现原图中有loop，但扫瞄图中没有找到loop；
?
情形2：扫瞄图中多出loop：
即配对关系中原图loop不存在，但扫瞄loop存在；
?
情形3: 原图loop和扫瞄loop都存在
?
出现情形1和情形2， 则证明两个图形存在较大的差异；再进行下一步的比较意义不大；如果还需要进行下面的比较；则需要过滤情形1和情形2的相关loop；否则会影响下一步的平均误差值；
?
?
?
第五部分 、算法实现之－－寻找最小平均误差
算法实现步骤：
?
5.1 重设所有loop的起点：
对于原图和扫瞄图的所有loop进行预处理； 修改其起点的位置； 每个loop的rect的右边中点水平向左边做射线和loop求交， 从右到左的第一个交点为loop的起点； 也就是在loop中插入此交点（如果交点为loop上的点则不插入）。 改变起点的位置不会影响loop的形状；
?
5.2 生成每个loop的等分点数组：
根据配对关系，先找到原图loop， 将此loop等分为多个点（按照长度和点的设置计算等分点的个数）； 按照此个数再去等分扫瞄loop，同样生成等长度的点数组； 原图loop和扫瞄图loop的起点位置基本相等；所以理论上两个等分的点数组每个点都有个对应关系；如果两个loop最接近重合；那么对应等分点数组之间的距离接近0；
?
?
?
5.3 最小范围内x，y偏移寻找最优解
?
……
此算法和后面的手动对比原理相同；
?
第六部分、寻找尺寸的对应关系
?
对MB_Dimension 尺寸类进行扩充； 在原图中，尺寸会记录一个或两个几何元素；并会记录相关的loop； 通过几何可以找到其产生的loop， 然后再根据配对的loop链表找到扫瞄图中对应的loop； 根据扫瞄的loop计算扫瞄图上的实际尺寸值，并将此值以扩展数据的方式记录在尺寸内；
?
?
在原图上对尺寸的对应关系进行计算整理；
?
因为原图上的元素和扫瞄图上的元素很难实现一一对应； 但原图上的loop和扫瞄图上的loop实现对应关系相对来说比较容易； 所有我们需要建立尺寸和原图loop的对应关系；
?
?
以上的对应关系可以清楚表示原图上的尺寸在扫瞄图内的对应关系； 比如：尺寸A在原图内标注了rect的宽度； 那么A对应的则是扫描图中Rect的宽度；
?
处理步骤：
6.1 在原图中将所有尺寸分类，找出其明显特征；
这些特征包括是否为圆半径标注，是否为直径标注； 是否为rect的长宽等等；
?
6.2 根据这些特征在扫瞄图的loop链表内寻找新的对应关系；
比如：特征显示尺寸B标注了 loop1左边到 loop2右边的距离；那么我们在扫瞄loop链表内分别找到 loop1，loop2 的配对loop1‘，loop2‘； 计算loop1‘左边到loop2‘右边的距离，此距离就是尺寸B在扫瞄图上的对应值；这种算法不会涉及到具体的那个几何元素的尺寸；比较准确的反映扫描图和原图的尺寸；
6.3 处理没有明显特征的尺寸关系；
如果尺寸没有明显特征； 则得到和尺寸相关的几何元素，用此元素到扫描图中寻找最合适的点链表；因为点连和几何的不确定性，这种方法得到的扫描图尺寸误差可能较大；
?
?
第七部分 、寻找几何元素之间的配对关系
算法实现步骤：
因为扫瞄后一个元素可能变成多个元素的组合，所以geom之间的配对关系准确率不高； 此配对关系仅限于存在尺寸标注的元素；
?
第八部分 、汇总比较结果
算法实现步骤：
?
?
最后更新时间 2012.12.09
原文：http://www.cnblogs.com/asuo/p/5224011.html