Если у меня есть произвольное множество точек, а затем один и тот же набор точек, повернутых в некоторой степени, кто-нибудь знает какие-либо алгоритмы для вычисления/оценки, где находится центр вращения? Или область изучения, где эти алгоритмы необходимы? У меня возникли проблемы с поиском релевантной информации.
Спасибо
Предположим, что у вас есть одна точка (x, y), которая переместилась в (x ', y').
Тогда центр вращения должен лежать на прямой, перпендикулярной (x, y) - (x ', y') и пересекающей центр (x, y) - (x ', y').
Теперь возьмем другую точку (x2, y2), которая переместилась в (x'2, y'2). Это также приводит к линии, на которой должен располагаться центр вращения.
Теперь возьмите эти две строки и вычислите пересечение. Там у вас есть центр вращения.
Обновление. Если у вас нет соответствия того, куда пошло место, не следует слишком сложно это понять. Вот предложение от головы: Найдите центр масс "до" -точек. Закажите очки в соответствии с их расстоянием от этой точки. Теперь сделайте то же самое с "after" -points. Теперь порядок двух наборов должен совпадать. (Точка, ближайшая к центру масс перед вращением, должна быть точкой, ближайшей к центру массы после вращения.)
Это был бы сумасшедший избыток для этого типа проблем, но я думаю, что функциональность обобщенного преобразования Hough для обнаружения объекта, по крайней мере, охватывает то, что вы хотите, хотя это не совсем для этой цели.
Для произвольной формы, созданной из набора точек и другого произвольного множества точек, она пытается найти форму в наборе точек, даже если она была повернута, масштабирована и переведена. Возможно, вы сможете извлечь масштабирование и перевод и получить то, что хотите.
В основном то, к чему это приведет, - это грубой форсинг возможных точек вращения, чтобы увидеть, какой из них лучше всего подходит для второго набора точек.
Очень интересная проблема. Мои знания об этом немного устарели, но, насколько я помню, есть некоторые исследования в использовании анализа подграфов на этом; т.е. характеризующие подразделы множества точек расстояниями между точками и дисперсиями в нем, а затем сопоставляя эти анализы подграфов между до и после вращения.
Это, конечно, предполагает очень сложный набор точек с неравномерным распределением.
Вам нужно найти некоторую подпись в вашем наборе данных, которая позволяет идентифицировать точки из первого набора (A) с теми, что указаны во втором наборе (B).
Простым способом является следующее:
Для каждого элемента E в найдите две ближайшие точки (N1, N2) и вычислите угол между N1, E, N2, что приведет к трем значениям: угол и расстояния от E до N1 и N2 ( ang, d1, d2).
Найдите 3 точки в с уникальными кортежами (ang, d1, d2).
Для каждого элемента из B вычислить также расстояние до двух ближайших соседей и угол. Найдите 3 точки, соответствующие выбранным из A.
Вычисление вращения - это всего лишь вопрос геометрического анализа.
update: вам нужно 3 балла, чтобы определить поворот в трехмерном пространстве. В 2D два будут делать.
update 2: поскольку другие комментируют другие сообщения, в могут быть симметрии, которые помешали бы вам найти 3 уникальных триплета для (ang, d1, d2). В этом случае для каждой из выбранных трех точек в вам придется выполнить поиск по всем элементам в B, соответствующим их триплетам, до тех пор, пока некоторая комбинация не приведет к вращению, которое работает для всех элементов в A.