Сравнить фигуры как пишется

Есть ли способ сравнить две геометрические фигуры (или любые две более общие структуры данных), не используя грубую силу, когда допускается допуск?

Грубая сила (которая сравнивает каждое значение каждого объекта с каждым значением другого объекта) работает, но она медленная, и я не могу ее использовать.

Я попытался отсортировать данные и сравнить две отсортированные коллекции. Это быстро, но работает только с нулевой терпимостью. Как только я добавляю терпимость, я теряюсь. Проблема состоит в том, что два значения могут быть одинаковыми при сравнении и разными при сортировке.

Вот некоторые подробности моей проблемы.

В моей надстройке Excel VBA у меня есть коллекция объектов Shape, созданная из коллекции Line объектов, созданных двумя объектами Point каждый. Надстройка сканирует чертеж САПР с помощью COM и создает коллекцию объектов Shape.

Упрощенная версия может сгенерировать это:

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

Я испробовал два подхода с использованием отсортированных коллекций. Оба быстры, потому что сравнение двух отсортированных коллекций происходит быстрее, чем метод грубой силы, но в некоторых случаях они не работают:

1. Коллекция

   SortedValues содержит все значения X и Y всех строк. Значения отсортированы, поэтому информация о том, является ли значение X или Y, теряется. Я использовал этот подход месяцами без проблем, но он терпит неудачу, например, когда единственное различие между двумя формами — между точками (10, 20) и —- +: = 12 =: + —-. Я добавил угол линии в список значений, ситуация улучшилась, но все еще есть случаи, когда этот подход не работает, потому что некоторая информация теряется, когда значения сортируются вместе. В приведенном выше примере этот подход будет работать со следующими коллекциями:

   (20, 10)

2. Коллекция

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

   SortedLines

EDIT:

Фигуры импортируются из внешнего графического приложения через COM. Форма может быть простой, как прямоугольник, или сложной, как любой причудливый контур, с 10 кругами внутри, 20 внутренними фигурами и 30 линиями. Они представляют собой панели с отверстиями и простыми украшениями, а иногда они имеют форму зуба, который составляет дюжину краев.

2 ответа

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

    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)