3

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?

kiss my armpit
  • 3,896

5 Answers5

7

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

mathlove
  • 139,939
  • Please explain why you compared just those vectors. – kiss my armpit Aug 09 '14 at 09: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 :http://en.wikipedia.org/wiki/Parallelogram#Characterizations – mathlove Aug 09 '14 at 09: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 09 '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 09 '14 at 10:12
  • @Pleasedon'ttouch: It is already included in (3): $\vec{P_1P_3}=\vec{P_2P_4}$ because in this case we have a parallelogram $P_1P_3P_4P_2$, so $\vec{P_1P_2}=\vec{P_3P_4}$ also holds. (Please draw a picture) Hence, we need only three tests. – mathlove Aug 09 '14 at 10:18
  • If $P_1$ is the opposite of $P_3$ then the last two tests are false. So the first test might be either false or true. – kiss my armpit Aug 09 '14 at 10:23
  • @Pleasedon'ttouch: Yes. So I wrote "Either of the following three holds, the four points are vertices of a parallelogram". – mathlove Aug 09 '14 at 10:30
  • But all of your three tests may be false even though the given 4 points can be vertices of a parallelogram. – kiss my armpit Aug 09 '14 at 10:31
  • @Pleasedon'ttouch: No. The condition I wrote is neccesary and sufficient condition, which means both that if either of the three holds, then the four points are vertices of a parallelogram and that if the four points are vertices of a parallelogram, then the four points must satisfy the condition I wrote. This is because of the condition which I introduced in the link in the above comment. – mathlove Aug 09 '14 at 10:35
  • Isn't a test missing for when all points are on the same line? – Siphor Aug 09 '14 at 11:09
  • @Siphor: Oh, you are right. Thank you for pointing it out. I'll edit it. – mathlove Aug 09 '14 at 11:12
  • How about the case there are 3 points on a line? – kiss my armpit Aug 09 '14 at 12:00
  • @Pleasedon'ttouch: Good point. I edited some points. Take a look. – mathlove Aug 09 '14 at 12:05
  • This is greatly simplified by just considering midpoints, see my answer below. – Jack D'Aurizio Aug 09 '14 at 14:02
3

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.

Jack D'Aurizio
  • 353,855
2

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.

User
  • 1,173
ShakesBeer
  • 3,641
1

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.

Darth Geek
  • 12,296
  • 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 09 '14 at 08:02
  • That is because $PQRS$ is not a paralelogram, $PRQS$ is. – Darth Geek Aug 09 '14 at 08:06
  • The OP specified that the points are given in a random order. – Jyrki Lahtonen Aug 09 '14 at 08: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 09 '14 at 08:13
0

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.

Danijel
  • 1,588