如何比较两个形状？

Question

有没有一种方法可以比较两个几何形状（或任何两个其他通用数据结构），而当涉及公差时不使用蛮力？

蛮力（将每个对象的每个值与另一个对象的每个值进行比较）有效，但速度很慢，我无法使用它。

我尝试对数据进行排序并比较两个排序的集合。它的速度很快，但只能在零公差下使用。一旦增加公差，我就会迷失方向。问题是当我比较时两个值可以相同，而当我排序时两个值可以不同。

这是我的问题的一些细节。

在我的Excel VBA加载项中，我有一个Shape对象集合，每个Line对象由两个Point对象组成。外接程序通过COM扫描CAD图并创建Shape对象的集合。

简化版本可能会生成以下内容：

            Shape 1     Shape 2
Point 1    0.0  5.0    0.0  4.9
Point 2    4.9  0.0    5.1  0.0
Point 3    5.0  5.0    5.0  5.0

我需要找出哪些形状与哪些形状相同，相同的方法具有相同的形状，大小和方向，但位置不同（到目前为止是微不足道的）加上或减去公差（现在不那么微不足道！）

的 Point.IsIdenticalTo(OtherPoint)定义为：

Function IsIdenticalTo(OtherPoint As Point) As Boolean
  IsIdenticalTo = Abs(X - OtherPoint.X) < Tolerance And Abs(Y - OtherPoint.Y) < Tolerance
End Function

暴力执行 Shape.IsIdenticalTo(OtherShape)作品但速度太慢：如果每个作品Line(I)都相同OtherShape.Line(J)，反之亦然，那么这两个形状是相同的。有时我有数百个形状，每个形状都有数百条线，因此强力解决方案对我不起作用。

我尝试了两种涉及排序集合的方法。两者都是快速的，因为比较两个排序的集合比蛮力方式要快，但是在某些情况下都失败了：

1. 一个SortedValues集合包含所有的所有行的X和Y值。这些值已排序，因此有关该值是X还是Y的信息都会丢失。我使用这种方法已经有几个月没有问题了，但是例如当两个形状之间的唯一区别是在点(10, 20)和之间时，它就失败了(20, 10)。我将线角添加到值列表中，情况有所改善，但是仍然存在这种方法失败的情况，因为在对值进行排序时会丢失一些信息。在上面的示例中，此方法适用于以下集合：

   Shape 1     Shape 2
     0.0         0.0
     0.0         0.0
     4.9         4.9
     5.0         5.0
     5.0         5.0
     5.0         5.1
   

2. 一个SortedLines集合包含所有行进行排序逆时针和最接近原点的点开始。这种方法不会丢失任何信息，但是在上面的示例中失败了，因为排序算法与相等性比较不一致。如果公差为0.5，则它们应该相同，但是排序算法将产生如下所示的集合。事情变得更加困难，因为我的形状包含子形状，因此每个形状上都有许多起点。

           Shape 1     Shape 2
   Point 1    4.9  0.0    0.0  4.9
   Point 2    5.0  5.0    5.1  0.0
   Point 3    0.0  5.0    5.0  5.0
   

编辑：

形状是通过COM从外部图形应用程序导入的。形状可以像矩形一样简单，也可以像任何花哨的轮廓一样复杂，里面有10个圆形，20个内部形状和30条线。它们代表带有孔和简单装饰的面板，有时它们具有锯齿形状，可形成数十个边缘。

Answer 1

1. 将形状处理为多边形

   将您的点（每条线）转换为(length,angle)如下图所示的线组：

   

   这样可以确保旋转/平移不变。如果看到更多线，angle=PI将它们连接在一起，以避免对具有不同采样的相同形状进行遗漏比较，则还应尝试为两个形状匹配相同的CW / CCW多边形绕线规则。

2. 寻找起点

   可以是最大或最小angle, length...或特定顺序angles+lengths。因此，对一个多边形的线进行重新排序，(cyclic shift)以便可以从“相同点”比较您的形状。

3. 比较-完全匹配

   • 行数必须相同
   • 周长必须相同+/-一定的精度

   因此，例如：

   fabs (sum of all lengths of poly1 - sum of all lengths of poly2) <= 1e-3
   

   如果不是，形状是不同的。然后比较所有长度和角度。如果任何一个值相差更大，那么精度值就不同。

4. 比较-大小无关紧要

   计算两个多边形的周长，l1,l2并调整与poly2匹配的周长的poly1所有长度的大小，从而将所有的长度poly2乘以 value = l1/l2;。在此之后，使用第3点的比较

5. 比较-形状偏差仍然可以进行正匹配（大小必须相同）

   尝试将线数设置为相同的值（连接所有角度接近的线PI）。然后周长应该“匹配” fabs(l1-l2)<=1e-3*l1。您可以使用项目符号4比较

6. 比较-尺寸和形状偏差仍然可以匹配

   只是调整大小poly2以匹配第4号poly1子弹的周长，然后使用第5号子弹

如果在展位多边形中找不到起点（项目符号＃2）

然后，您必须检查所有起点的平移，以便多边形是否具有5条展位线：

    poly1: l11,l12,l13,l14,l15
    poly2: l21,l22,l23,l24,l25

然后，您必须比较所有5种组合（除非您尽快找到匹配项）：

    cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25)
    cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
    cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
    cmp (l11,l12,l13,l14,l15),(l23,l24,l25,l21,l22)
    cmp (l11,l12,l13,l14,l15),(l24,l25,l21,l22,l23)
    cmp (l11,l12,l13,l14,l15),(l25,l21,l22,l23,l24)

[笔记]

1. 也有比较快速的方法，但是在某些情况下它们可能会丢失

   • 您可以比较直线，角度的直方图
   • 您可以使用神经网络（我不喜欢它们，但是它们非常适合这样的分类）

2. 如果您的形状必须以相同的方式定向（无旋转不变）

   然后使用线方向角代替顶点角

3. 如果您不能确保两个比较的多边形具有相同的缠绕规则

   那么您必须检查他们的展位：

   cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25)
   cmp (l11,l12,l13,l14,l15),(l25,l24,l23,l22,l21)
   

我知道答案有点含糊，但还是希望它至少能有所帮助。