如何比较两个形状？

有没有办法比较两个几何形状（或任何两个更通用的数据结构），而不是在涉及容差时使用暴力？

蛮力（比较每个对象的每个值与另一个对象的每个值）是有效的，但速度很慢，我不能使用它。

我试着对数据进行sorting并比较两个已sorting的集合。 速度很快，但它只适用于零容忍。 一旦我添加容忍，我迷路了。 问题是，当我比较时，两个值可能是相同的，而当我sorting时，这两个值是不同的。

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

在我的Excel VBA加载项中，我有一个Shape对象集合，它们由两个Point对象构成的Line对象集合构成。 该加载项通过COM扫描CADgraphics并创buildShape对象的集合。

一个简化的版本可以产生这个：

  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) ，反之亦然，那么这两个形状是相同的。 有时我有几百个形状，每个都有几百行，所以暴力解决scheme不适合我。

我尝试了两种涉及sorting集合的方法。 两者都很快，因为比较两个sorting后的集合比暴力方式更快，但是在某些情况下都失败了：

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

    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集合包含逆时针sorting的所有行，从最接近原点的点开始。 这种方法不会丢失任何信息，但在上面的例子中失败了，因为sortingalgorithm与平等比较不一致。 如果公差是0.5，它们应该是相同的，但是sortingalgorithm会生成如下所示的集合。 事情变得更加困难，因为我的形状包含子形状，所以每个形状上有许多起点。

     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从外部graphics应用程序导入形状。 形状可以像矩形一样简单，也可以像任何花式轮廓一样简单，内部有10个圆形，20个内部形状和30个线条。 他们代表有洞和简单装饰的面板，有时他们有一个锯齿形状，这使得十几个边缘。

Answer 1

1. 像多边形一样处理形状

   将你的点（每一行）转换为一组线(length,angle)就像这个图像：

   

   这确保了旋转/平移的不变性。 如果您看到更多的线条与angle=PI连接在一起，以避免不同取样的相同形状的错过比较也尝试匹配两个形状相同的CW / CCW多边形缠绕规则。

2. find起点

   可以是最大或最小的angle, length …或angles+lengths特定顺序。 所以重新排列一个多边形的行(cyclic shift)所以你的形状如果可以的话就从“相同点”进行比较。

3. 比较 – 完全匹配

   • 行数必须相同
   • 周界必须相同+/-一些准确度

   例如：

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

   如果不是形状是不同的。 然后比较所有的长度和angular度。 如果任何一个值的差异超过精度值，则形状不同。

4. 比较 – 大小无关紧要

   计算两个多边形l1,l2周长l1,l2并调整比较的poly2所有长度以匹配poly1周长，因此poly1所有长度都乘以value = l1/l2; 。 在这个使用比较从子弹＃3

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

   尝试将行数设置为相同的值（连接angular度接近PI所有行）。 那么周界应该“匹配”… fabs(l1-l2)<=1e-3*l1 。 你可以使用子弹＃4比较

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

   只需调整poly2大小来匹配poly2周长， poly1 ＃4中的子弹一样，然后使用子弹＃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. 还有更快的方法来比较，但在某些情况下可能会错过

   • 你可以比较直线，angular度的直方图
   • 你可以使用neural network（我不喜欢它们，但它们是这样的分类的理想select）

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

   那么代替顶angular使用线的方向angular

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

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

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

我知道这是一个模糊的答案，但仍然希望至less有一点帮助…

Answer 2

我有同样的问题。 我计算用距离加权的顶点的相邻matrix。 这将计算所有的边长和对angular线。 那么如果matrix的每行或每列的模块与另一个matrix相同，那么这两个形状是相同的。 对于公差，只需在启动前使用函数round（）。 复杂度是O（n2 / 2），因为你必须计算相邻matrix的一半是对称的。 问题是，我无法检测到形状是否翻转。