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.

2 answers

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), потому что вы должны вычислить лишь половину смежной матрицы, которая является симметричной. Проблема заключается в том, что я не могу обнаружить, если форма переворачивается.