Как узнать, имеют ли два набора точек одинаковый узор

Question

У меня есть 2 набора точек в 3D с одинаковым числом, я хочу знать, имеют ли они одинаковый узор, я подумал, что могу спроецировать их на плоскости XZ, XY и YZ, а затем сравнить проекции в каждой плоскости, но я не знаю, как это сделать, я подумал, что выпуклый корпус может помочь, но это будет неточно. Есть ли простой алгоритм для этого? сложность не является большой проблемой, поскольку количество очков будет крошечным, я реализую в Java.

Могу ли я решить эту проблему в 3D напрямую с тем же алгоритмом?

Прилагаемый изображение показывает пример того, что я имею в виду.

Изменить: Нет гарантии для заказа. Без шкалы, есть только вращение и перенос.

Answer 1

Если у вас есть фиксированный объект с разными формами и движениями, попарное или множественное сопоставление может быть для вас полезным решением. Например, см. этот документ . Этот метод можно расширить и для более высоких измерений.

Если у вас есть два разных набора точек, которые поступают из различные объекты, и вы обнаружите сходство между ними, одно решение может заключаться в вычислении дискретного расстояния Фреше в обоих наборах точек, а затем сравнения их значений.

Другая связанная концепция - Реконструкция формы . Вы можете смешать результат алгоритма восстановления правильной формы с двумя предыдущими методами для вычисления сходства:

Answer 2

Я бы собрал некоторую информацию о каждой точке: информацию, которая зависит только от «формы», а не от фактического перемещения / поворота. Например, это может быть сумма всех расстояний между точкой и любой другой точкой фигуры. Или это может быть самый большой угол между любыми двумя точками, если смотреть из рассматриваемой точки. Выберите любой показатель c, обеспечивающий наибольшее разнообразие.

Затем отсортируйте точки по этому метри c.

Проделайте то же самое для обеих групп точек.

Как На первом этапе вы можете сравнить обе группы по их отсортированному списку показателей. Оставьте небольшую погрешность, поскольку вы будете иметь дело с ограничениями точности с плавающей запятой. Если они не могут быть сопоставлены друг с другом, прервите алгоритм: они имеют разные формы.

Теперь переведите набор точек так, чтобы первая точка в упорядоченном списке была сопоставлена ​​с исходной точкой (0, 0, 0) , т.е. вычесть первую точку из всех точек в группе.

Теперь поверните набор точек вокруг оси Y так, чтобы вторая точка в упорядоченном списке совпадала с плоскостью XY. Поверните точку, установленную вокруг оси Z, так, чтобы эта точка совпадала с осью X: она должна соответствовать (d, 0, 0), где d - это расстояние между первой и второй точкой. в отсортированном списке.

Наконец, поверните набор точек вокруг оси X, чтобы третья точка в упорядоченном списке совпадала с плоскостью XY. Если эта точка совпадает с предыдущими точками, вам нужно продолжать делать это со следующей точкой (точками), пока вы не повернете неколинеарную точку.

Сделайте это с обеими группами точек. Затем сравните преобразованные таким образом координаты обоих списков.

Это основной алгоритм, но я пропустил случаи, когда значение metri c одинаково для двух точек, и, таким образом, отсортированный список может иметь перестановки без нарушения порядка сортировки:

В этом случае вам необходимо выполнить указанные выше преобразования с различными перестановками этих равнозначных точек в начале отсортированного списка, пока нет соответствия. 1021 *

Кроме того, проверяя соответствие, вы должны принять во внимание, что совпадающие точки могут быть не в том же порядке, что и в отсортированном списке другой группы, и вам следует проверить следующие точки, которые имеют такие же метри c тоже.