Можно ли преобразовать один многоугольник в другой, используя только параллельный перенос и пропорциональное масштабирование?

Question

На входе даны два многоугольника (координаты вершин этих многоугольников перечислены в порядке их обхода; однако, порядок обхода для разных углов многоугольника можно выбирать по-разному). Можно ли преобразовать один многоугольник в другой, используя только параллельный перенос и пропорциональное масштабирование?

У меня есть следующая идея Итак, найдите какой-то общий пик для двух многоугольников и сделайте перенос одного многоугольника так, чтобы эти вершины лежали в одной точке, а затем масштабирование, чтобы соседняя точка совпадала с соответствующей точкой другого многоугольника, но я думаю, что это неправильно, по крайней мере, я могу ' написать в коде

Есть ли какая-то специальная формула или теорема для этой проблемы?

Answer 1

Я бы решил это следующим образом.

1. Найдите необходимый параллельный транспорт.
2. Найдите необходимое масштабирование.
3. Посмотрите, являются ли они одним и тем же полигоном сейчас.

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

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

Теперь посмотрим, совпадают ли все точки.Если нет, они разные.В противном случае ответ - да.

Answer 2

Вычислить выровненные по оси ограничивающие рамки двух полигонов.

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

X = s.(x - xtl) + Xtl
Y = s.(y - ytl) + Ytl

, где s - коэффициент масштабирования, а (xtl, ytl), (Xtl, Ytl) - углы.

Теперь выберите вершину первого многоугольника, спрогнозируйте координаты в другом и найдите соответствующую вершину.Если вы не можете, ответ отрицательный.В противном случае вы можете сравнить оставшиеся вершины *.

---

* Я предполагаю, что полигоны не имеют перекрывающихся вершин.Если они могут иметь произвольные перекрытия, я думаю, что вы должны попытаться сопоставить все вершины со всеми циклическими перестановками.