vba 如何比较两个形状？

How to compare two shapes?

提问by stenci

Is there a way to compare two geometric shapes (or any two more generic data structures), without using the brute force when a tolerance is involved?

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

The brute force (that is comparing each value of each object against each value of the other object) works but it's slow, and I can't use it.

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

I tried sorting the data and comparing two sorted collections. It's fast, but it only works with zero tolerance. As soon as I add the tolerance I get lost. The problem is that two values can be identical when I compare and different when I sort.

我尝试对数据进行排序并比较两个排序后的集合。它很快，但它只能在零容忍的情况下工作。一旦我添加了容差，我就会迷路。问题是两个值在比较时可能相同，而在排序时可能不同。

Here are some details of my problem.

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

In my Excel VBA add-in I have a collection of Shapeobjects made by a collection of Lineobjects made by two Pointobjects each. The add-in scans a CAD drawing via COM and creates the collection of Shapeobjects.

在我的 Excel VBA 加载项中，我有一个Shape对象集合，这些Line对象集合由两个Point对象构成的对象集合构成。该插件通过 COM 扫描 CAD 绘图并创建Shape对象集合。

An simplified version could generate this:

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

            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

I need to find which shapes are identical to which shapes, where identical means has the same shape, size and orientation, but not the same position (so far it's trivial) plus or minus a tolerance (not so trivial now!)

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

The Point.IsIdenticalTo(OtherPoint)is defined as:

的Point.IsIdenticalTo(OtherPoint)定义为：

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

The brute force implementation of the Shape.IsIdenticalTo(OtherShape)works but it's too slow: if each Line(I)has an identical OtherShape.Line(J)and viceversa, then the two shapes are identical. Sometimes I have hundreds of shapes with hundreds of lines each, so the brute force solution doesn't work for me.

蛮力实现的Shape.IsIdenticalTo(OtherShape)作品但是太慢了：如果每个Line(I)都有一个相同的OtherShape.Line(J)，反之亦然，那么这两个形状是相同的。有时我有数百个形状，每个形状有数百条线，所以蛮力解决方案对我不起作用。

I tried two approaches involving sorted collections. Both are fast because comparing two sorted collections is faster than the brute force way, but both fail in some conditions:

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

1. A SortedValuescollection contains all the X and Y values of all the lines. The values are sorted, so the info about whether a value is an X or a Y is lost. I have used this approach for months without problems, but it fails for example when the only difference between two shapes is between the points (10, 20)and (20, 10). I added the line angle to the list of values, things have improved, but there are still cases where this approach fails, because some info is lost when the values are sorted together. In the example above this approach would work with the following collections:

   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. A SortedLinescollection contains all the lines sorted counter-clockwise and starting from the point closest to the origin. This approach doesn't lose any info, but it fails in the example above because the sorting algorithm doesn't agree with the equality comparison. If the tolerance is 0.5 they should be identical, but the sorting algorithm produces the collections shown below. Things get more difficult because my shapes contain sub-shapes, so there are many starting points on each shape.

           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
   

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
   

EDIT:

编辑：

Shapes are imported from an external graphical application via COM. A shape can be as simple as rectangle or as complex as any fancy outline with 10 circles inside, 20 internal shapes and 30 lines. They represent panels with holes and simple decorations, and sometimes they have a saw-tooth shape, which makes dozen of edges.

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

采纳答案by Spektre

1. handle shape as polygon

   convert your points (each line) to set of lines (length,angle)like on this image:

   

   this ensures invariance on rotation/translation. If you see more lines with angle=PIjoin them together to avoid miss comparisons of the same shapes with different sampling also try to match the same CW/CCWpolygon winding rule for both shapes.

2. find start point

   Can be biggest or smallest angle, length... or specific order of angles+lengths. So reorder lines of one polygon (cyclic shift)so your shapes are compared from the 'same point' if they can.

3. comparison - for exact match

   • number of lines have to be the same
   • perimeters must be the same +/- some accuracy

   so for example:

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

   if not shapes are different. Then compare all lengths and angles. If any one value differs more then accuracy value then shapes are different.

4. comparison - size does not matter

   compute perimeter of both polygons l1,l2and resize all lengths of compared poly2to match perimeter of poly1so all lengths of poly2are multiplied by value = l1/l2;. After this use comparison from bullet #3

5. comparison - shape deviations can still do positive match (size must be the same)

   try to set the number of lines to the same value (join all lines with angle close to PI). Then perimeters should "match" ... fabs(l1-l2)<=1e-3*l1. You can use bullet #4comparison

6. comparison - size and shape deviations can still match

   just resize poly2to match perimeter of poly1as in bullet #4and then use bullet #5

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以匹配poly1子弹#4中的周长，然后使用子弹#5

If you can not find the start point in booth polygons (bullet #2)

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

Then you have to check for all start point shifts so if your polygons have booth 5 lines:

然后你必须检查所有的起点偏移，所以如果你的多边形有 5 行：

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

Then you have to compare all 5 combinations (unless you found match sooner):

然后你必须比较所有 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)

[Notes]

[笔记]

1. There are also faster ways to compare but they can miss in some cases

   • you can compare histograms of lines, angles
   • you can use neural network (I do not like them but they are ideal for classifications like this)

2. if your shapes have to be oriented in the same ways (no rotation invariance)

   then instead of vertex angle use the line direction angle

3. if you can not ensure the same winding rule for both compared polygons

   then you have to check them booth:

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

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)
   

I know it is a bit vague answer but still hope it helps at least a little ...

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

回答by jurhas

I have the same problem. I compute the adjacent matrix of the vertex weighted with the distances. This compute all the sides length and diagonals. Then if the module of each row or column of the matrix are the same with the other matrix, then the two shapes are the same. For the tolerance just use the function round() before start. The complexity is O(n2 / 2), because you have to compute just an half of the adjacent matrix that is symmetric. The problem is that I cannot detect if a shape is flipped.

我也有同样的问题。我计算用距离加权的顶点的相邻矩阵。这将计算所有边长和对角线。那么如果矩阵的每一行或每一列的模块与另一个矩阵相同，那么这两个形状是相同的。对于公差，只需在开始前使用函数 round()。复杂度为 O(n2 / 2)，因为您只需计算对称矩阵的一半。问题是我无法检测形状是否翻转。

回答by Ali Taheri

I am not sure how do you want to solve this problem. you want to go deep or you just want a solution. I can suggest you use an OpenCV function called "matchShapes". This function is based on Hu moments and has a good performance for rigid shapes. After you extract the target and the main contours then use the below code to compare them.

我不确定你想如何解决这个问题。您想深入了解，或者您只是想要一个解决方案。我可以建议您使用名为“matchShapes”的 OpenCV 函数。该函数基于 Hu 矩，对于刚性形状具有良好的性能。提取目标和主要轮廓后，请使用以下代码进行比较。

dif = cv.matchShapes(Contour1, Contour2, 1, 0, 0)

Smaller "dif" value means more similarity between contours.

较小的“dif”值意味着轮廓之间的相似度更高。