7
$\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$
4
  • 3
    $\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, 2016 at 15:07
  • $\begingroup$ Thank you for your quick reply. Can you please bit more specific about the equations to be used? $\endgroup$ Jul 13, 2016 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, 2016 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$ Jul 14, 2016 at 6:53

12 Answers 12

12
$\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$
2
  • $\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$ Jul 13, 2016 at 15:30
  • $\begingroup$ I made a correction to my formula for the angular distance. $\endgroup$
    – Lee Mosher
    Jul 13, 2016 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$
5
  • $\begingroup$ Thank you for a specific answer. I think |m1-m2|< threshold will work hopefully. $\endgroup$ Jul 13, 2016 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$ Jul 13, 2016 at 15:19
  • 14
    $\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, 2016 at 15:21
  • $\begingroup$ Ethan @LeeMosher Thanks for identifying the problem in the solution. $\endgroup$ Jul 13, 2016 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, 2016 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$
3
  • $\begingroup$ Thanks for the reply. But I have to also detect two lines are almost parallel condition. $\endgroup$ Jul 13, 2016 at 15:17
  • 1
    $\begingroup$ Say that the two lines are $\epsilon$-almost parallel if $|m_{2} - m_{1}| < \epsilon$. $\endgroup$
    – aduh
    Jul 13, 2016 at 15:20
  • 3
    $\begingroup$ According to @LeeMosher above, it is a terrible idea to subtract slopes. $\endgroup$ Jul 13, 2016 at 15:27
6
$\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$
2
  • $\begingroup$ Thank you for a really simple explanation. The final equation is so simple and computational efficient. $\endgroup$ Jul 14, 2016 at 4:37
  • 1
    $\begingroup$ This also works in higher dimensions, if we use the wedge product: $$\lVert u\wedge v\rVert^2<\varepsilon^2\lVert u\rVert^2\lVert v\rVert^2$$ $$\sum_{1\leq i<j\leq n}(u_iv_j-u_jv_i)^2<\varepsilon^2\sum_{1\leq i\leq n}u_i\!^2\sum_{1\leq j\leq n}v_j\!^2$$ $\endgroup$
    – mr_e_man
    Jan 8, 2020 at 4:11
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$
3
  • $\begingroup$ Thanks for the reply. But I have to also detect two lines are almost parallel condition. $\endgroup$ Jul 13, 2016 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$ Jul 13, 2016 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$ Jul 13, 2016 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$
1
  • $\begingroup$ For actual numerics, I would not recommend the dot-product formula. See e.g. this. $\endgroup$ Jul 13, 2016 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$
3
  • $\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$ Jul 14, 2016 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, 2016 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$ Aug 1, 2016 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$
1
  • $\begingroup$ For nearly vertical lines, of course, multiplying the slopes can lead to overflow. $\endgroup$ Jul 14, 2016 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$
6
  • $\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$ Jul 13, 2016 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$ Jul 13, 2016 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$ Jul 13, 2016 at 15:43
  • $\begingroup$ In practice, one will of course use two-argument arctangent... $\endgroup$ Jul 13, 2016 at 16:48
  • $\begingroup$ @J.M. Sorry can't got your point. Can you please elaborate? Thanks. $\endgroup$ Jul 14, 2016 at 4:22
1
$\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$
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$
1
  • $\begingroup$ Thank you for your answer. So according to you what type of computation you are suggesting? $\endgroup$ Jul 14, 2016 at 11:09

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