Given four points $(x_1,y_1)$,$(x_2,y_2)$,$(x_3,y_3)$,$(x_4,y_4)$. How can we efficiently test them to make sure whether they are vertices of a parallelogram?
I think evaluating and comparing the distance between two points seems to be inefficient. What do you think? Do you have any better method?
$\endgroup$ 25 Answers
$\begingroup$Edit : As Siphor comments, the previous condition I wrote included the case that at least some three of the four points are on a line. So, we need to eliminate such situation.
Let $P_i(x_i,y_i)$. If there exist either $s\in\mathbb R$ or $t\in\mathbb R$ such that $$\vec{P_1P_2}=s\vec{P_1P_3},\ \ \ \vec{P_1P_2}=t\vec{P_1P_4},$$ then at least some three of the four points are on a line.
Hence, if there don't exist such $(s,t)$ and either of the following three holds, then the four points are vertices of a parallelogram.
(1) $x_2-x_1=x_3-x_4\ \text{and}\ y_2-y_1=y_3-y_4$.
(2) $x_3-x_1=x_2-x_4\ \text{and}\ y_3-y_1=y_2-y_4$.
(3) $x_3-x_1=x_4-x_2\ \text{and}\ y_3-y_1=y_4-y_2$.
P.S. We can write
(1)$\iff \vec{P_1P_2}=\vec{P_4P_3}$.
(2)$\iff \vec{P_1P_3}=\vec{P_4P_2}$.
(3)$\iff \vec{P_1P_3}=\vec{P_2P_4}$.
$\endgroup$ 14 $\begingroup$The convex quadrilateral $ABCD$ is a parallelogram if and only if the midpoint of $AC$ is the midpoint of $BD$, too. Hence you just need to compute $\binom{4}{2}=6$ midpoints and check that two of them are the same point.
By this way you get an affirmative answer even for degenerate parallelograms, like the one in which $B$ and $D$ are the midpoint of $AC$, just to say. To avoid such situations, you just have to check that exactly two midpoints are the same point.
$\endgroup$ 1 $\begingroup$Iff $PQRS$ is a paralelogram, then:
$$\begin{cases}P_x - Q_x = R_x - S_x & \\ P_x - S_x = Q_x - R_x &\\ P_y - Q_y = R_y - S_y & \\ P_y - S_y = Q_y - R_y \end{cases}$$
Where $P_x$ is the $x$ coordinate of $P$, $P_y$ is the $y$ coordinate of $P$, and so on.
$\endgroup$ 4 $\begingroup$We use vectors. Let $A=(x_1,y_1),...,D=(x_4,y_4)$
Then $\vec {AC}=\vec {BD}$ or $\vec {AB}= \vec {CD}$ or a couple of other options is the necessary and sufficient condition. $\vec {AD}=(x_4-x_1,y_4-y_1)$ btw.
The other answers are equivalent but vectors are the intuitive way of understanding it.
This problem can be easily generalized to $n$ dimensions.
If $\vec{AB} = \vec{DC}$, or, equivalently, $\vec{AD}=\vec{BC}$, then $ABCD$ is a parallelogram, because this means that $AB$ has same length and is parallel to $DC$ (or, equivalently, same thing with $AD$ and $BC$), which defines the parallelogram.
$\endgroup$
