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$ 412 Answers
$\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$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$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$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$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$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".)
Move both line segments to the origin. For the first one that would be $$ (x_2 - x_1, y_2 - y_1) . $$
Calculate the angle between the line segments Lots of websites tell you how. One is .
Decide how small that angle should be to count as "nearly parallel".
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$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$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$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$ $\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$ $\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
