Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Can the points form a parallelogram in any order? –  augurar Aug 9 at 7:56
    
@augurar: The given points are randomly chosen from a set of some points. The order is not known. –  Who is crazy first Aug 9 at 7:58

5 Answers 5

up vote 6 down vote accepted

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

share|improve this answer
    
@Pleasedon'ttouch: Is there anything unclear? I hope this helps. –  mathlove Aug 9 at 9:33
    
Please explain why you compared just those vectors. –  Who is crazy first Aug 9 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 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 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}$. –  Who is crazy first Aug 9 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.

share|improve this answer
1  
We can save the calculation just by calculating the midpoint times 2 to avoid dividing by 2. –  Who is crazy first Aug 9 at 15:01
    
+1 I agree with that this is very simple. –  mathlove Aug 10 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.

share|improve this answer
    
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 at 8:02
    
That is because $PQRS$ is not a paralelogram, $PRQS$ is. –  Darth Geek Aug 9 at 8:06
    
The OP specified that the points are given in a random order. –  Jyrki Lahtonen Aug 9 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 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.