如何比较两个形状？

问题描述

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

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.

在我Excel中的VBA加载我有一个由线集合所做图形对象的集合对象由两个点发对象，每个。加载项扫描CAD通过COM绘图，并创建了图形的对象集合。

In my Excel VBA add-in I have a collection of Shape objects made by a collection of Line objects made by two Point objects each. The add-in scans a CAD drawing via COM and creates the collection of Shape objects.

这是简化版本，可能会产生这样的：

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!)

在 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）的作品，但它的速度太慢：如果每个线（我）具有相同的 OtherShape.Line（J），反之亦然，那么这两个形状是相同的。有时候，我有数百个形状有数以百计的每个线条，使蛮力解决方案并没有为我工作。

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.

我试了两种方法涉及到排序的集合。两者都很快，因为比较两个排序集合比蛮力方式快，但均不能在某些条件：

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 SortedValues​​ 集合包含所有的X和所有行的Y值。值进行排序，所以大约值是否为一个X或Y被丢失的信息。我已经没有问题，用这种方法好几个月了，但失败例如，当两个形状之间的唯一区别是点之间的（10，20）和（20，10）。我增加了线条的角度值列表，事情已经改善，但仍有一些这种方法失败的情况下，因为当值进行排序以及一些信息丢失。在上述这种方法的例子与下面的集合：

1. A SortedValues collection 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

A SortedLines 集合包含所有行逆时针和最靠近原点的点开始排序。这种方法不丢失任何信息，但它不能在上面因为排序算法不与相等比较同意的例子。如果容差是0.5他们应该是相同的，但排序算法产生如下所示的集合。事情变得更加困难，因为我的形状包含子的形状，所以有每个形状许多出发点。

A SortedLines collection 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

编辑：

形状与通过COM外部图形应用程序导入。一个形状可以是简单的矩形或复杂的任何花哨的外形与10圈里，20个内部形状和30日线。他们重新present板孔和简单的装饰，有时候他们有一个锯齿形，这就使得十几个边缘。

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.

推荐答案

1.handle形状的多边形

1.handle shape as polygon

• 在转换您的点（每行）
• 要在此图像中设定的行（长度，角度），像

• 这确保不变性在旋转/平移
• 如果您看到更多的线，角= PI将它们连接在一起
• 要避免与不同的取样相同形状的小姐比较
• 也尝试匹配相同的顺时针/逆时针多边形缠绕规则为形状

2.find起点

• 可以是最大或最小的角度，长度...
角
• 或特定的顺序+长度
• 在一个多边形的重新排序线（循环移位）
• 让你的形状是从，如果他们能
在同一个点相比，

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

3.comparison - 为精确匹配

3.comparison - for exact match

• 行数必须是相同的
• 在周边必须是相同的+/-一些精度
• 因此，例如：晶圆厂（POLY 1的各个长度的总和 - 聚2-所有长度的总和）与LT = 1E-3
• 如果没有形状不同
• 然后比较所有的长度和角度
• 如果任何一个值相差那么多的精度值则形状不同

4.comparison - 大小并不重要

4.comparison - size does not matter

• 在两个多边形L1的计算周长12
• 调整相比，聚2-对所有的长度相匹配POLY 1的周长
• 这样：聚2的所有长度乘以值= L1 / L2;
• 在从子弹3
这个用的比较

• compute perimeter of both polygons l1,l2
• resize all lengths of compared poly2 to match perimeter of poly1
• so: all lengths of poly 2 is multiplied by value = l1/l2;
• after this use comparison from bullet 3

5.comparison - 形状偏差仍然可以做积极的匹配（大小必须相同）

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

• 尝试到行数设置为相同的值（联同角度接近PI所有行）
• 在周边应当匹配......晶圆厂（L1-L2）＆LT; = 1E-3 * L1
• 在可以使用的子弹4比较

6.comparison - 大小和形状的偏差仍然可以匹配

6.comparison - size and shape deviations can still match

• 在刚刚调整聚2-匹配POLY 1的周界子弹4
• 然后用子弹5

如果你不能找到在展位多边形的起点（子弹2）

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

• 那么你必须检查所有的启动点偏移
• 因此，如果您的多边形有展位5行
• POLY 1：L11，L12，L13，L14，L15
• 聚2-：L21，L22，L23，L24，L25

• 那么你必须比较所有5种组合（除非你找到匹配越快）

• then you have to check for all start point shifts
• so if your polygons have booth 5 lines
• 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)

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.有也更快的方式来进行比较，但他们可以在某些情况下会错过

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

• 您可以比较行的直方图，角度
• 您可以利用神经网络（我不喜欢他们，但他们是理想的分类是这样）

2，如果你的形状都以相同的方式被定向（无旋转不变性）

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

• 然后，而不是顶角用线方向角

3，如果你不能保证相同的缠绕规则均比较多边形

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)

我知道这是一个比较含糊的答案，但还是希望它有助于至少有一点......

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

这篇关于如何比较两个形状？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！