# Optimal fit of four points to a square

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.

• What exactly do you mean by 'minimum movement'? I guess the idea is to minimise the sum of Euclidean distances of the changes? Dec 14, 2022 at 14:04
• 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.
– Community Bot
Dec 14, 2022 at 14:08
• @afreelunch, yes you are correct. The sum of Euclidean distances. I will update my question. Dec 14, 2022 at 14:12

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.

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.

• 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? Dec 14, 2022 at 16:25
• By direct differentiation. Dec 14, 2022 at 16:32