사각에 가장 잘 맞음

Question

나는 4 개의 점 A, B, C 및 D로 구성된 모양을 가지고 있는데 그 중 유일한 위치가 알려져 있습니다. 목표는이 점을 서로에 대해 특정 각도와 오프셋을 가지도록 변형하는 것입니다.

예 : A(-1,-1) B(2,-1) C(1,1) D(-2,1) : AB, BC, CD 및 AD 사이의 오프셋이 모두 완전한 정사각형 (모든 각도 90)으로 변환되어야합니다. 결과는 반 시계 방향으로 약간 회전 한 정사각형이어야합니다.

이 작업을 수행하는 가장 효율적인 방법은 무엇입니까? 간단한 블록 시뮬레이션 프로그램에 사용하고 있습니다.

Answer 1

마크에서 언급했듯이 제한된 최적화를 사용하여 원본 구석까지의 거리의 제곱을 최소화하는 측면 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) 

빠른 냅킨 스케치는 이러한 제약이 충분하다는 것을 설득해야 Lagrange multipliers의 방법에 따라

, 나는 다음과 같은 거리 제한을 선택했다.

그런 다음 g 제목이 모두 0 인 f를 최소화하려고합니다.

라그랑 함수이다 :

F + L = SUM (I = 1 내지 5, 리튬 GI)을 li S는 라그랑주 승수이다

.

그라데이션은 비선형이므로 헤센을 가져 와서 multivariate Newton's method을 사용하여 솔루션을 반복해야합니다.

여기에 (검은 색) 주어진 데이터에 대한 내가 가진 솔루션 (적색)입니다 :

는이 단계의 L2 규범이 6.5106e-9이었다 후 5 반복을했다.