基于图元形位特征码的重复对象检测技术，快速分析图形文件中重复对象

vectra

本文介绍了一种利用散列函数分析图形文件中重复对象的方法

一般图元的位置和形状通过1 2 10 11 12 13 14 15 40 50 51等组码来表达，为加快比对分析的效率，对上述组码通过散列函数提取该图元的特征码，特征码为一个整数型数值，相当于将一个图元压缩成一个整数，只要该整数相同，即可认为图元相同，由于整数便于排序，大大加快了对比的效率。
核心HASH函数，为BKDR
这个算法来自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。是一个非常简单高效的哈希算法。

1. (defun hash-1 (e h /)
   
2.   (+ (fix e) (* 31 h))
   
3. )
   

(defun hash-1 (e h /)<br />   (+ (fix e) (* 31 h))<br /> )<br />

点的HASH方法，本例中对浮点数进行了取整操作，对于一般工程制图没有影响。

1. (defun hash-p (lst h /)
   
2.   (foreach e lst
   
3.     (setq h (hash-1 e h))
   
4.   )
   
5. )

(defun hash-p (lst h /)<br />   (foreach e lst<br />     (setq h (hash-1 e h))<br />   )<br /> )

生成块表对象中所有图元的HASH代码，如果需要对对象的图层，颜色等进行判断，可以表中加入8 62等组码。句柄及运行时生成的图元名不应加入。

1. (defun hash-block (block / dxf h ht)
   
2.   (vlax-for item block
   
3.     (setq dxf (entget (p-ensure-ename item))
   
4.     h   (hash
   
5.     (mapcar
   
6.       'cdr
   
7.       (vl-remove-if-not '(lambda (e) (member (car e) '(1 2 10 11 12 13 14 15 40 50 51))) dxf)
   
8.     )
   
9.         )
   
10.     )
    
11.     (setq ht (cons (cons h (p-cls-get dxf 5)) ht))
    
12.   )
    
13.   ht
    
14. )
    

(defun hash-block (block / dxf h ht)<br />   (vlax-for item block<br />     (setq dxf (entget (p-ensure-ename item))<br />     h   (hash<br />     (mapcar<br />       'cdr<br />       (vl-remove-if-not '(lambda (e) (member (car e) '(1 2 10 11 12 13 14 15 40 50 51))) dxf)<br />     )<br />         )<br />     )<br />     (setq ht (cons (cons h (p-cls-get dxf 5)) ht))<br />   )<br />   ht<br /> )<br />

性能：
对于两三万对象的图形一般可以数秒内完成，而且算法时间复杂度为N，数据量增加时耗时线性增长。


存在的问题：

一个整数不可能完全代表所有对象，即会产生碰撞，但几率比较小，对于有数万个图元的图形来说，几乎难以发生。对于需要高度可靠的场景，可以对相同HASH值的图元进行二次排查。


完整的代码见附件

1028695446

每组重复对象，只选中n-1个对象

pengfei2010

看来楼主的消重只能针对 完全重叠的 图元，那这个意义不大了，因为
第一：重叠必定存在一定的容差，所以程序必须能有容差值参数
第二：多段相重叠的直线，必须获取其最长线的点
第三：圆弧同直线，如果是封闭成圆的圆弧，那消重后就是圆了
还有很多情况需要考虑，单纯消除完全重叠 其实很简单，效率也很快

pengfei2010

关于消重 程序，我已经写了，并且优化了 2年了，就是 效率稍慢，超过6000个图元就会卡，2000以内图元还是比较轻松消重的，看看楼主的算法 效率怎么样，最主要是 效果是否完美

amen1981628

学习一下！

cable2004

学习一下！
学习一下！

liwen888888

什么好东西，谢谢分享

yshf

回复学习，学习！

liunian0524

感谢楼主分享,学习一下！

lrd1861

yoyoho

回复学习，学习了!!!!!

lijiao

新思想，一定要学习学习

434939575

这个好，不知道删除重复能用不，先谢谢了！