Лучше всего подходит квадрат к четырехугольнику - PullRequest
Новая
       36

Лучше всего подходит квадрат к четырехугольнику

0 голосов
/ 08 марта 2012

У меня есть фигура, состоящая из четырех точек, A, B, C и D, из которых известна только их позиция.Цель состоит в том, чтобы преобразовать эти точки, чтобы иметь определенные углы и смещения относительно друг друга.

Например: A(-1,-1) B(2,-1) C(1,1) D(-2,1), который должен быть преобразован в идеальный квадрат (все углы 90) со смещениями между AB, BC, CD и AD все равно 2. Результат должен быть квадратом, слегка повернутым против часовой стрелки.

Какой самый эффективный способ сделать это?Я использую это для простой программы моделирования блоков.

1 Ответ

1 голос
/ 09 марта 2012

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

Нам нужно минимизировать f = (a-A)^2 + (b-B)^2 + (c-C)^2 + (d-D)^2 (где квадратфактически является точечным произведением векторного аргумента с самим собой) с учетом некоторых ограничений.

Следуя методу множители Лагранжа , я выбрал следующие ограничения расстояния: 

g1 = (a-b)^2 - 4
g2 = (c-b)^2 - 4
g3 = (d-c)^2 - 4

и следующие угловые ограничения: 

g4 = (b-a).(c-b)
g5 = (c-b).(d-c)

Быстрый набросок салфетки должен убедить вас в том, что этих ограничений достаточно.

Затем мы хотим минимизировать f при условии, что все g равны нулю.

Функция Лагранжа:

L = f + Sum (i = от 1 до 5, li gi)

, где li s - множители Лагранжа.

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

Вот решение, которое я получил (красный) дляданные приведены (черный):

Best fit square

Это заняло 5 итераций, после чего L2 норма шага была 6,5106e-9.

...