Ваша первая мысль может быть пытаться найти ротацию, которая отображает один объект в другой, но это очень сложная тема ... и на самом деле не нужна! Вы не спрашиваете, как лучше всего соответствовать двум, вы просто спрашиваете, одинаковы они или нет.
Характеризуйте свою модель по списку всех расстояний между точками. Отсортируйте список на этом расстоянии. Теперь сравните список для каждого объекта. Они должны быть идентичными, поскольку на переводные интервалы не влияет перевод или ротация.
три вопроса:
1) Что делать, если количество точек велико, что это большой список пар (N * (N-1)/2). В этом случае вы можете выбрать только самые длинные, или даже лучше, сохранить 1 или 2 самых длинных для каждой вершины, чтобы каждая часть вашей модели имела некоторый вклад.Однако удаление информации, подобной этой, изменяет проблему на вероятностную и не детерминированную.
2) Для определения формы, а не ребер используются только вершины. Это может быть хорошо (и на практике будет), но если вы ожидаете иметь цифры с одинаковыми вершинами, но разные соединительные края. Если это так, сначала проверьте соответствие вершины. Если это пройдет, назначьте уникальную маркировку каждой вершине, используя это отсортированное расстояние. Самый длинный край имеет две вершины. Для каждой из THOSE вершин найдите вершину с самым длинным (оставшимся) ребром. Обозначьте первую вершину 0 и следующую вершину 1. Повторитесь для других вершин в порядке, и у вас будут назначены теги, которые не зависят от сдвига и вращения. Теперь вы можете точно сравнить топологии ребер (проверьте, что для каждого ребра в объекте 1 между двумя вершинами имеется соответствующее ребро между теми же двумя вершинами в объекте 2). Примечание: это начинает становиться действительно сложным, если у вас есть несколько одинаковых интервалов расстояния, и поэтому вы необходимо сопоставить тай-брейк, чтобы задания были стабильными и уникальными.
3) Существует вероятность того, что две фигуры имеют одинаковые популяции длины ребер, но они не идентичны. Это верно, когда один объект является зеркальным отображением другого. Это довольно раздражает, чтобы обнаружить! Один из способов сделать это - использовать четыре некомпланарных точки (возможно, те, которые помечены от 0 до 3 с предыдущего шага) и сравнить «ручность» системы координат, которую они определяют. Если ручность не соответствует, объекты являются зеркальными изображениями.
Обратите внимание, что список расстояний дает вам легкое отклонение неидентичных объектов. Он также позволяет добавлять «нечеткое» принятие, допуская некоторую ошибку в заказах. Возможно, использование среднеквадратичной разницы между двумя списками как «мера подобия» будет хорошо работать.
Редактировать: Похоже, ваша проблема - облако точек без краев. Тогда раздражающая проблема краевого соответствия (№ 2) даже не применяется и может быть проигнорирована! Вы все равно должны быть осторожны с проблемой зеркального изображения № 3.
Я знаю некоторые способы грубой силы для этого, хочу узнать, есть ли еще более простой способ. – stevedbrown
Интересная проблема. То, как я решаю проблему, если бы я просто проверял одинаковые наборы, было бы найти две самые отдаленные точки и сделать ось x, а затем найти самую удаленную точку от этой оси и сделать нормалью от оси x до это указывает на ось y. Но это может легко потерпеть неудачу для «похожих» множеств. – Nosredna
@Nosredna: такая нормализация та же самая, что я нашел в статье о видении робота. Единственное отличие состоит в том, что он оценивается для каждой пары точек, потому что вы можете иметь окклюзии. Как только вы нормализуете и получите все пары, вы можете квантовать и оценивать сходство, используя метод подсчета голосов, чтобы согласиться, если все будет правильно соответствовать. –