6
$\begingroup$

I have $2$ lines in this form Line $1$: $(x_1,y_1)$ $(x_2,y_2)$ Line $2$: $(x_3,y_3)$ $(x_4,y_4)$

I want to detect if the two lines are parallel or almost parallel.

My idea is to if the angle between the two lines is $\leq$ some threshold angle (like $10$ degrees or so), then they are almost parallel.

But don't know how to compute angle between two lines.

Please help me with the equations or if there is any idea to detect almost parallel lines.

Thank you.

$\endgroup$
  • 2
    $\begingroup$ in the plane, two lines are parallel if they have the same slope (or put another way, if they make the same angle with one of the coordinate axes) $\endgroup$ – costrom Jul 13 '16 at 15:07
  • $\begingroup$ Thank you for your quick reply. Can you please bit more specific about the equations to be used? $\endgroup$ – helloansuman Jul 13 '16 at 15:11
  • 2
    $\begingroup$ Is there a specific application for checking if lines are almost parallel that you're interested in. Something you'd like to conclude from that? $\endgroup$ – snulty Jul 13 '16 at 15:50
  • $\begingroup$ I am applying this to know if two people are walking side-by-side to each other. I have their location. $\endgroup$ – helloansuman Jul 14 '16 at 6:53

12 Answers 12

11
$\begingroup$

A line of slope $m$ makes a signed angle with the $x$-axis equal to $\theta = \arctan(m)$ (expressed in radians), and this angle has value between $-\pi/2$ and $+\pi/2$.

For two lines of slopes $m_1$, $m_2$, which make signed angles equal to $\theta_1 = \arctan(m_1)$ and $\theta_2 = \arctan(m_2)$, the "angular distance" between those two lines will be either $|\theta_1 - \theta_2|$ or $\pi - |\theta_1 - \theta_2|$, whichever is smaller. The alternative $|\theta_1 - \theta_2|$ is used when that number is $\le \pi/2$, and if that number is $> \pi/2$ then the other alternative $\pi - |\theta_1 - \theta_2]$ will be $\le \pi/2$.

Once you have computed the angular distance between the two lines, set it to be less than whatever threshold you desire.

$\endgroup$
  • $\begingroup$ Thank you for a more specific idea of angle comparison. I am feeling now the angular comparison will be better than the idea of subtraction of slopes. $\endgroup$ – helloansuman Jul 13 '16 at 15:30
  • $\begingroup$ I made a correction to my formula for the angular distance. $\endgroup$ – Lee Mosher Jul 13 '16 at 18:10
10
$\begingroup$

Suppose you have vectors $u = (u_1,u_2)$ and $v = (v_1,v_2),$ where $u_1$ is the x-component and $u_2$ is the y-component of $u.$ Recall that $\cos{\theta} = \frac{u \cdot v}{||u|| \,||v||},$ where $u \cdot v = u_1v_1 + u_2v_2$ and $||u|| = \sqrt{u \cdot u}$.

Or, one could compute the slopes of each line, and say that if |slope 1 - slope 2| $< \epsilon$ threshold, then they are almost parallel.

$\endgroup$
  • $\begingroup$ Thank you for a specific answer. I think |m1-m2|< threshold will work hopefully. $\endgroup$ – helloansuman Jul 13 '16 at 15:18
  • $\begingroup$ When the slopes are close the tangents of two angles are close but that doesn't tell you how close together the angles are. $\endgroup$ – Ethan Bolker Jul 13 '16 at 15:19
  • 12
    $\begingroup$ Subtracting slopes is a terrible idea if the lines are nearly vertical. The difference of angles can be tiny while the difference of slopes is enormous. $\endgroup$ – Lee Mosher Jul 13 '16 at 15:21
  • $\begingroup$ Ethan @LeeMosher Thanks for identifying the problem in the solution. $\endgroup$ – helloansuman Jul 13 '16 at 15:26
  • $\begingroup$ It all depends on how one defines "almost parallel". From a visual perspective, using the angle between the lines would make most sense, as this is free from choosing a specific coordinate basis and computing the slopes relative to that basis, which may be a problem as Lee pointed out. However, there is no reason "almost parallel" can't be a difference in slopes, as this would give a measure of how much the two linear functions will vary later on down the line. So of course, it depends on what one is interested in. $\endgroup$ – Merkh Jul 13 '16 at 16:28
6
$\begingroup$

The slope of the first line is $m_{1}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}$ and the slope of the second is $m_{2}=\frac{y_{4}-y_{3}}{x_{4}-x_{3}}$. The lines are parallel if and only if $m_{1}=m_{2}$.

$\endgroup$
  • $\begingroup$ Thanks for the reply. But I have to also detect two lines are almost parallel condition. $\endgroup$ – helloansuman Jul 13 '16 at 15:17
  • 1
    $\begingroup$ Say that the two lines are $\epsilon$-almost parallel if $|m_{2} - m_{1}| < \epsilon$. $\endgroup$ – grndl Jul 13 '16 at 15:20
  • 3
    $\begingroup$ According to @LeeMosher above, it is a terrible idea to subtract slopes. $\endgroup$ – helloansuman Jul 13 '16 at 15:27
4
$\begingroup$

Let $u = (a_1, b_1) = (x_2 - x_1, y_2 - y_1)$ and $v = (a_2, b_2) = (x_4 - x_3, y_4 - y_3)$ be the corresponding vectors.

For detecting angles near 0, the best is to use the cross product: $$ \sin \theta = \frac{u \times v}{|u||v|},$$ where $u \times v = \det(u, v) = a_1 b_2 - a_2 b_1$.

So, for instance, if you want to test for $|\theta| < \theta_0$, you can just test for $$(u \times v)^2 < \varepsilon^2 |u|^2|v|^2,$$ with $\varepsilon = \sin\theta_0 \approx \theta_0$.

Notice that this formula only involves addition/subtraction and multiplication.

$\endgroup$
  • $\begingroup$ Thank you for a really simple explanation. The final equation is so simple and computational efficient. $\endgroup$ – helloansuman Jul 14 '16 at 4:37
2
$\begingroup$

Let

$$\mathrm v_1 := \mathrm x_2 - \mathrm x_1 \qquad \qquad \qquad \mathrm v_2 := \mathrm x_4 - \mathrm x_3$$

be the direction vectors of each of the two lines. Compute the rank of the following matrix

$$\begin{bmatrix} | & |\\ \mathrm v_1 & \mathrm v_2\\ | & |\end{bmatrix}$$

If the matrix has full column rank, then the two given lines are not parallel. If the matrix is rank-$1$, then the two given lines are parallel.

$\endgroup$
  • $\begingroup$ Thanks for the reply. But I have to also detect two lines are almost parallel condition. $\endgroup$ – helloansuman Jul 13 '16 at 15:17
  • $\begingroup$ @helloansuman Then normalize each of the two columns of the matrix and then compute the angle formed by the two columns. $\endgroup$ – Rodrigo de Azevedo Jul 13 '16 at 15:22
  • $\begingroup$ Thank you very much, sir. I will consider this solution too. As I am using MatLab to simulate a matrix representation will help. $\endgroup$ – helloansuman Jul 13 '16 at 15:33
2
$\begingroup$

Here's a method that may work for you. (The other answers so far will tell you whether the lines are parallel, but don't find the angle so don't give you a way to decide on "almost parallel".)

  1. Move both line segments to the origin. For the first one that would be $$ (x_2 - x_1, y_2 - y_1) . $$

  2. Calculate the angle between the line segments Lots of websites tell you how. One is http://www.wikihow.com/Find-the-Angle-Between-Two-Vectors .

  3. Decide how small that angle should be to count as "nearly parallel".

$\endgroup$
  • $\begingroup$ For actual numerics, I would not recommend the dot-product formula. See e.g. this. $\endgroup$ – J. M. is a poor mathematician Jul 13 '16 at 16:55
2
$\begingroup$

I have a method I've used to determine "almost parallelism" that may work for you. It's something I've used computationally to determine parallelism within some very small tolerance.

A consequence of Bezout's theorem is that two distinct lines will intersect at exactly 1 point. For parallel lines, they meet at infinity. "Almost parallel" lines will intersect at a point very far away. The question then becomes how to recognize a point very far away or at infinity.

If you change the points into homogeneous coordinates (for this case specifically, by mapping a 2D point $(X,Y)$ as a 3D point $(X,Y,1)$ and converting a 3D point $(x,y,w)$ to a 2D point $(x/w,y/w)$), you can do some neat tricks. You can then also represent the lines as triples $(a,b,c)$ such that it satisfies the implicit line equation $aX+bY+c=0$. Using the dot product operator, you can express this equation as a dot product: $(a,b,c) \cdot (x,y,w) = 0$. Another cool trick is that you can similarly use the cross product operator to determine the implicit triple for the line that passes through the 2 points: $(x_1,y_1,w_1)\,\times\,(x_2,y_2,w_2) = (a,b,c)$.

You can again use the cross product operator to determine the point at which 2 lines expressed as implicit triples intersect: $(a_1,b_1,c_1)\,\times\,(a_2,b_2,c_2)=(x,y,w)$. What's interesting about this is that it tells you where the point is, even at infinity. Because of the way we defined the mapping from 2D to 3D, if the $w$ component of the 3D point is small, the $x$ and $y$ components of the 2D point are large. If $w=0$, then the 2D point is at infinity.

For my uses, I only test strictly for $w=0$ (the exactly parallel case), however you might be able to adapt this for your use case. Hope this helps!

$\endgroup$
  • $\begingroup$ Got your trick. I have to just put a threshold on the final 'w' value. Thanks for contribution. I will have a look on that. $\endgroup$ – helloansuman Jul 14 '16 at 4:20
  • $\begingroup$ I think you'll also need some way to truly use w as a distance comparison. What you can do is a sort of normalization, where you force sqrt(x^2+y^2)=1 by dividing all components by sqrt(x^2+y^2). Otherwise, with a naive w test, (0.2,0.5,0.1) would seem "farther" than (2,5,1) when they really represent the same point. $\endgroup$ – CADJunkie Jul 15 '16 at 0:31
  • $\begingroup$ Thank you all for helping me out with my problem. I think I just found 1000 ways of solving the same problem. But I am still confused which one to use. I am going to try every methods. $\endgroup$ – helloansuman Aug 1 '16 at 18:09
2
$\begingroup$

Quicker than finding the arctan of each slope, I'd use the slopes themselves; call them $a,b$. The tangent of the divergence angle is then $$\pm\frac{a-b}{1+ab}$$ This requires no transcendental operations, after you choose a threshold.

EDIT: To lessen the possibility of overflow that J.M. points out, use instead $$\pm\frac{\Delta y_a \Delta x_b - \Delta x_a \Delta y_b}{\Delta x_a \Delta x_b + \Delta y_a \Delta y_b}$$ This expression is equivalent to the first, with numerator and denominator multiplied by $\Delta x_a \Delta x_b$. We may note in passing that it is the magnitude of the cross product divided by the dot product.

LATER EDIT: Better yet, test whether $$ |{\Delta y_a \Delta x_b - \Delta x_a \Delta y_b}| < m \, |{\Delta x_a \Delta x_b + \Delta y_a \Delta y_b}| $$ where m = tan(maxangle); no divisions this way.

$\endgroup$
  • $\begingroup$ For nearly vertical lines, of course, multiplying the slopes can lead to overflow. $\endgroup$ – J. M. is a poor mathematician Jul 14 '16 at 11:37
1
$\begingroup$

Two lines are parallel or not. I suppose that the notion of ''almost parallel'' refers, for you, to a situation in which the angle between the two lines is less than some fixed (small) value.

If it is so, and if you want the angle between the two lines, note that the slope of the first line is $m_1=\frac{y_2-y_1}{x_2-x_1}$ and the slope of the second line is $m_2=\frac{y_4-y_3}{x_4-x_3}$, so you can find the angles between the lines and the $x$ axis as $\theta_1=\arctan m_1$ and $\theta_2=\arctan m_2$ and the angle between the lines is $\theta=|\theta_1-\theta_2|$.

$\endgroup$
  • $\begingroup$ You got me right. That was my idea to calculate angle between them if it is zero then parallel or if angle is less than some threshold then almost parallel. $\endgroup$ – helloansuman Jul 13 '16 at 15:23
  • $\begingroup$ Yes. Note that you have some problem if $x_2=x_1$ or $x_4=x_3$, but you can treat this cases (lines parallel to the $y$ axis) separately. $\endgroup$ – Emilio Novati Jul 13 '16 at 15:34
  • $\begingroup$ That is not a problem as that case will not appear in my case all points are distinct. Thanks for pre-informing though. $\endgroup$ – helloansuman Jul 13 '16 at 15:43
  • $\begingroup$ In practice, one will of course use two-argument arctangent... $\endgroup$ – J. M. is a poor mathematician Jul 13 '16 at 16:48
  • $\begingroup$ @J.M. Sorry can't got your point. Can you please elaborate? Thanks. $\endgroup$ – helloansuman Jul 14 '16 at 4:22
0
$\begingroup$

Generally, the inner product or dot product of two vectors is used to find the angle between two lines and so whether they're parallel or almost parallel. Or you can skip to the bottom for just the formula.

First find a corresponding vector for each line, which we'll write as the change in x and y coordinates respectively. For vector $\vec u$ representing the direction of line 1, $$\vec u = (u_x, u_y) = (x_2-x_1,y_2-y_1)$$ and for vector $\vec v$ representing the direction of line 2, $$\vec v = (v_x, v_y) = (x_4-x_3,y_4-y_3)$$ The inner product of two vectors, $\vec u \cdot \vec v$ (also written $\langle \vec u, \vec v \rangle$) can be calculated by summing the products of matching terms in the two vectors. Here, $$\vec u \cdot \vec v = u_x v_x + u_y v_y = (x_2-x_1)(x_4-x_3) + (y_2-y_1)(y_4-y_3)$$

To find the angle $\theta$ between $\vec u$ and $\vec v$ we use that $$\vec u \cdot \vec v = \lVert \vec u \rVert \lVert \vec v \rVert cos(\theta)$$ so $$ \theta = cos^{-1}(\frac{\vec u \cdot \vec v}{\lVert \vec u \rVert \lVert \vec v \rVert}) $$ where the norm or magnitude $\lVert \vec v \rVert$ of a vector $\vec v$ here is its length which we can find with the Pythagorean theorem. $$ \lVert \vec u \rVert = \sqrt{(u_x)^2 + (u_y)^2} = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$$ $$ \lVert \vec v \rVert = \sqrt{(v_x)^2 + (v_y)^2} = \sqrt{(x_4-x_3)^2 + (y_4-y_3)^2}$$ In the case of two lines, we can check if the angle is less than some value $\theta_{max}$ with $$ \lvert \vec u \cdot \vec v \rvert < \lVert \vec u \rVert \lVert \vec v \rVert cos(\theta_{max}) $$ where the absolute value accounts for how we could pick our vectors to go in either direction along each line. So for 10 degrees $$ \lvert \vec u \cdot \vec v \rvert < cos(10^\circ) \lVert \vec u \rVert \lVert \vec v \rVert$$ is approximately $$ \lvert \vec u \cdot \vec v \rvert < .985 \lVert \vec u \rVert \lVert \vec v \rVert $$ Or written out completely, lines given by $(x_1,y_1)$ $(x_2,y_2)$ and $(x_3,y_3)$ $(x_4,y_4)$ are almost parallel (here given as within about 10 degrees of each other) if and only if $$ \lvert (x_2 - x_1)(x_4 - x_3) + (y_2 - y_1)(y_4 - y_1) \rvert < .985 \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \sqrt{(x_4 - x_3)^2 + (y_4 - y_3)^2}$$ where .985 can be changed to the cosine of whichever angle you want to be the threshold.

$\endgroup$
0
$\begingroup$

The others have responded on how to find angle between two lines.

Difference between slopes or angles of inclination of two given lines to x-axis .. that is what you want to control:

$$ \tan^{-1} \frac{y_2-y_1}{x_2-x_1}-\tan^{-1} \frac{y_4-y_3}{x_4-x_3} < \frac{10\, \pi}{180}$$

The smaller it is, the more parallel the lines are. If zero, they are completely parallel.

Taking tan on both sides seems to bring it to an algebraic form, but I think it is really not better for numerical calculation.

$\endgroup$
  • $\begingroup$ Thank you for your answer. So according to you what type of computation you are suggesting? $\endgroup$ – helloansuman Jul 14 '16 at 11:09
0
$\begingroup$

The orthogonality of two vectors is detected by the scalar product, while the parallelity is detected by the cross product. Therefore put $${\bf u}:=(x_2-x_1,y_2-y_1),\quad {\bf v}:=(x_4-x_3,y_4-y_3)$$ and compute the (unsigned) angle $\phi$ between the two lines by means of $$\sin\phi={{\bf u}\wedge{\bf v}\over |{\bf u}|\>|{\bf v}|}={|u_1v_2-u_2v_1|\over\sqrt{u_1^2+u_2^2}\>\sqrt{v_1^2+v_2^2}}\ .$$

$\endgroup$

protected by Jyrki Lahtonen Jul 14 '16 at 10:13

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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