5
$\begingroup$

Suppose I have four points in $2D$ that are approximately the corners of a square. How do I find the minimum movements of the points that turn the approximate square into a perfect square?

By "minimum movements" I mean, for example, the sum of Euclidean movements of the points.

$\endgroup$
3
  • $\begingroup$ What exactly do you mean by 'minimum movement'? I guess the idea is to minimise the sum of Euclidean distances of the changes? $\endgroup$
    – afreelunch
    Dec 14, 2022 at 14:04
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Dec 14, 2022 at 14:08
  • $\begingroup$ @afreelunch, yes you are correct. The sum of Euclidean distances. I will update my question. $\endgroup$
    – Pibben
    Dec 14, 2022 at 14:12

2 Answers 2

2
$\begingroup$

The fitting error can be expressed as

$$ E=\sum_k(x_0+\rho\cos\left(\theta+\frac{\pi}{2}(k-1)\right)-x_k)^2+(y_0+\rho\sin\left(\theta+\frac{\pi}{2}(k-1)\right)-y_k)^2 $$

with $(x_k,y_k)$ the data, and after minimizing we can obtain

$$ \cases{ x_0 = \frac 14\sum_k x_k\\ y_0 = \frac 14\sum_k y_k\\ \rho = \frac 14\sqrt{(x_2-x_4+y_3-y_1)^2+(x_1-x_3+y_2-y_4)^2}\\ \theta = \arctan\left(\frac{x_1-x_3+y_2-y_4}{\sqrt{(x_2-x_4+y_3-y_1)^2+(x_1-x_3+y_2-y_4)^2}},-\frac{x_2-x_4+y_3-y_1}{\sqrt{(x_2-x_4+y_3-y_1)^2+(x_1-x_3+y_2-y_4)^2}}\right) } $$

NOTE

This formulation assumes that the data points are given in a clock wise sequence.

$\endgroup$
0
$\begingroup$

Let the modified coordinates of the four corners be

$A' = A + r_1 $

$B' = B + r_2 $

$C' = C + r_3 $

$D' = D + r_4 $

where $A,B,C,D , r_1, r_2, r_3, r_4 \in \mathbb{R}^2 $

Define

$f_1 = (B - A + r_2 - r_1)\cdot(D- A + r_4 - r_1 )$

$f_2 = (A - B + r_1 - r_2 ) \cdot ( C - B + r_3 - r_2 )$

$f_3 = (B- A + r_2 - r_1) \cdot (B - A + r_2 - r_1) - (D - A + r_4-r_1)\cdot(D - A + r_4 - r_1) $

$f_4 = (B - A + r_2 - r_1) \cdot (B - A + r_2 - r_1 ) - (C - B + r_3 -r_2) \cdot (C - B + r_3 - r_2 ) $

Lagrange Function to be minimized is

$ f = r_1^2 + r_2^2 + r_3^2 + r_4^2 + \lambda_1 f_1 + \lambda_2 f_2 + \lambda_3 f_3 + \lambda_4 f_4$

And we have the following conditions for the minimum

$ \nabla_{r_1} f = 2 r_1 + \lambda_1 \nabla_{r_1} f_1 + \lambda_2 \nabla_{r_1} f_2 + \lambda_3 \nabla_{r_1} f_3 + \lambda_4 \nabla_{r_1} f_4 = 0 $

$ \nabla_{r_2} f = 2 r_2 + \lambda_1 \nabla_{r_2} f_1 + \lambda_2 \nabla_{r_2} f_2 + \lambda_3 \nabla_{r_2} f_3 + \lambda_4 \nabla_{r_2} f_4 = 0 $

$ \nabla_{r_3} f = 2 r_3 + \lambda_1 \nabla_{r_3} f_1 + \lambda_2 \nabla_{r_3} f_2 + \lambda_3 \nabla_{r_3} f_3 + \lambda_4 \nabla_{r_3} f_4 = 0 $

$ \nabla_{r_4} f = 2 r_4 + \lambda_1 \nabla_{r_4} f_1 + \lambda_2 \nabla_{r_4} f_2 + \lambda_3 \nabla_{r_4} f_3 + \lambda_4 \nabla_{r_4} f_4 = 0 $

$f_1 = 0$

$f_2 = 0$

$f_3 = 0$

$f_4 = 0$

The gradients of $f_1, f_2 , f_3 ,f_4$ with respect to $r_1 $ are given by

$ \nabla_{r_1} f_1 = 2 r_1 - (B + D - 2 A + r_2 + r_4 ) $

$ \nabla_{r_1} f_2 = C - B + r_3 - r_2 $

$\nabla_{r_1} f_3 = - 2 (B - A + r_2 - r_1) + (D - A + r_4 - r_1) $

$ \nabla_{r_1} f_4 = -2 (B - A + r_2 - r_1 )$

$ \nabla_{r_2} f_1 = D - A + r_4 - r_1 $

$ \nabla_{r_2} f_2 = 2 r_2 - (A + C - 2 B + r_1 + r_3) $

$\nabla_{r_2} f_3 = 2 (B- A + r_2 - r_1) $

$ \nabla_{r_2} f_4 = 2 (B - A + r_2 - r_1 ) + 2 (C - B + r_3 - r_2)$

$ \nabla_{r_3} f_1 = 0 $

$ \nabla_{r_3} f_2 = A - B + r_1 - r_2 $

$\nabla_{r_3} f_3 = 0 $

$ \nabla_{r_3} f_4 = -2 (C - B + r_3 - r_2)$

$ \nabla_{r_4} f_1 = B - A + r_2 - r_1 $

$ \nabla_{r_4} f_2 = 0 $

$\nabla_{r_4} f_3 = 2 (D - A + r_4 - r_1) $

$ \nabla_{r_4} f_4 = 0$

So now we have $12$ nonlinear equations in $12$ variables, and we can use Newton-Raphson multivariate method to solve these $12$ equations.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your answer! I'm afraid it went a little bit over my head. The left hand side of the equations, the $ \nabla_{r_n} f_m$ part, how do I find the values of those? $\endgroup$
    – Pibben
    Dec 14, 2022 at 16:25
  • $\begingroup$ By direct differentiation. $\endgroup$ Dec 14, 2022 at 16:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .