How to test whether a set of four points can form a parallelogram

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?

-
Can the points form a parallelogram in any order? – augurar Aug 9 '14 at 7:56
@augurar: The given points are randomly chosen from a set of some points. The order is not known. – kiss my armpit Aug 9 '14 at 7:58

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}$.

-
@Pleasedon'ttouch: Is there anything unclear? I hope this helps. – mathlove Aug 9 '14 at 9:33
Please explain why you compared just those vectors. – kiss my armpit Aug 9 '14 at 9:54
@Pleasedon'ttouch: Sure. Because a simple (not self-intersecting) quadrilateral is a parallelogram if and only if one pair of opposite sides are parallel and equal in length. You can see this in the following page :en.wikipedia.org/wiki/Parallelogram#Characterizations – mathlove Aug 9 '14 at 9:58
@Pleasedon'ttouch: So, for example, if $\vec{P_1P_2}=\vec{P_4P_3}$, then the four points are vertices of a parallelogram $P_1P_2P_3P_4$. You'll see this if you draw some pictures. – mathlove Aug 9 '14 at 10:08
I think we need 4 tests. Your answer needs one more test which is $\vec{P_1P_2}=\vec{P_3P_4}$. – kiss my armpit Aug 9 '14 at 10:12

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.

-
We can save the calculation just by calculating the midpoint times 2 to avoid dividing by 2. – kiss my armpit Aug 9 '14 at 15:01
+1 I agree with that this is very simple. – mathlove Aug 10 '14 at 10:28

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.

-
So according to you for example the square with $P=(0,0)$, $Q=(1,1)$, $R=(1,0)$ and $S=(0,1)$ is not a parallelogram as $P_x-Q_x=-1$ but $R_x-S_x=1\neq-1$. – Jyrki Lahtonen Aug 9 '14 at 8:02
That is because $PQRS$ is not a paralelogram, $PRQS$ is. – Darth Geek Aug 9 '14 at 8:06
The OP specified that the points are given in a random order. – Jyrki Lahtonen Aug 9 '14 at 8:09
Yes, and if I'm given your $P,Q,R,S$ then I can conclude that $PQRS$ is not a paralelogram, but that $PRQS$ is. What I've answered is not false, it means that you might have to check up to three posible combinations to know if you can make a paralelogram out of the four points you are given. – Darth Geek Aug 9 '14 at 8:13

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.

-