# How to compare two shapes?

 Refresh December 2018 Views 6k time
4

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

The `Point.IsIdenticalTo(OtherPoint)` is defined as:

``````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.

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` 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
``````
2. 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
``````

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.

4
1. обрабатывать форму, как многоугольник

конвертировать ваши очки (каждую линию) для установки линий , `(length,angle)`как на этой картинке:

это обеспечивает инвариантность ротационно / перевода. Если вы видите несколько строк с `angle=PI`соединить их вместе , чтобы избежать несоосности сравнения одних и тех же форм с разной выборки также пытаются соответствовать один и тот же / CCW CW многоугольник обмотку правило для обеих форм.

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

Если вы не можете найти точку на стенде многоугольников (пуля # 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)
``````

Я знаю, что это немного расплывчатый ответ, но все-таки надеюсь, что это помогает, по крайней мере немного ...

1

У меня та же проблема. Я вычислить прилегающую матрицу вершины, взвешенную с расстояниями. Это все вычисления длины сторон и диагоналей. Тогда, если модуль каждой строки или столбца матрицы являются одинаковыми с другой матрицей, то эти две формы являются одинаковыми. Для допуска просто использовать функцию раунд () перед запуском. Сложность O (n2 / 2), потому что вы должны вычислить лишь половину смежной матрицы, которая является симметричной. Проблема заключается в том, что я не могу обнаружить, если форма переворачивается.