When i was writing my programming project the other day i ran into an interesting problem that i couldn't solve, i spent a while trying solutions with absolute values but none of that worked.
Here's the problem:
I saw a similar problem on this site: Finding the fourth vertex of a square But my problem differs in the fact that you cannot immediately know the diagonal of the square since the points are given in a random order.
Is this problem even possible? And if not why not?
On
The three distances among the points will always be $L$, $L$ and $L\sqrt{2}$. The two furthest apart are on a diagonal. With that information you can easily find the fourth vertex. The configuration can start out in any dimension. The three points will determine the plane of the square. The square can have any orientation in that plane.
On
Possible formulas are $$ x_4 = 2\max(x_1,x_2,x_3)+2\min(x_1,x_2,x_3)-(x_1+x_2+x_3) \\ y_4 = 2\max(y_1,y_2,y_3)+2\min(y_1,y_2,y_3)-(y_1+y_2+y_3) $$ Reasoning: There is at least one vertex on the left side and one vertex on the right side among $V_1$, $V_2$ and $V_3$. Therefore, we can calculate the sum of all x-coodinates in two different ways, either as $2\max(x_1,x_2,x_3)+2\min(x_1,x_2,x_3)$ or as $x_1+x_2+x_3+x_4$.
Let $u,v,w\in\mathbb R^2$ be the three known vertices (we don't require the four sides of the square to be parallel to the $x$-axis or $y$-axis) and $c$ be the centre of the square. Then $c$ is also the centre of the unique circumcircle of the square. That is, $c$ is the unique solution of $\|u-c\|^2 = \|v-c\|^2 = \|w-c\|^2$. Expanding the squared norms, we get $$ 2c^T\pmatrix{u-v&v-w} = (\|u\|^2-\|v\|^2,\ \|v\|^2-\|w\|^2). $$ Thus $$ c^T=\frac12(\|u\|^2-\|v\|^2,\ \|v\|^2-\|w\|^2)\pmatrix{u-v&v-w}^{-1} $$ and the remaining vertex is given by $4c-(u+v+w)$.