I am a Belgian engineer working on software in C# to provide smart bending solutions to a manufacturer of press brakes.
In this context I am searching for the best way to determine if two lines are parallel, based on the following information:
- Each line has two points of which the coordinates are known
- These coordinates are relative to the same frame
- So to be clear, we have four points: A (ax, ay, az), B (bx,by,bz), C (cx,cy,cz) and D (dx,dy,dz)
Which is the best way to be able to return a simple boolean that says if these two lines are parallel or not? Can someone please help me out?
Edit after reading answersBelow is my C#-code, where I use two home-made objects, CS3DLine and CSVector, but the meaning of the objects speaks for itself. A toleratedPercentageDifference is used as well.
public static bool AreParallelLinesIn3D(CS3DLine left, CS3DLine right) { double toleratedPercentageDifference = 1; CSVector vLeft = new CSVector(left.p1, left.p2); CSVector vRight = new CSVector(right.p1, right.p2); double ricoX = vLeft.X / vRight.X ; double ricoY = vLeft.Y / vRight.Y ; double ricoZ = vLeft.Z / vRight.Z ; if (Math.Abs(ricoX - ricoY) > Math.Abs(toleratedPercentageDifference * ricoX / 100)) return false; if (Math.Abs(ricoX - ricoZ) > Math.Abs(toleratedPercentageDifference * ricoX / 100)) return false; return true; }6 Answers
$\begingroup$Compute $$AB\times CD$$ which is zero for parallel lines.
In practice there are truncation errors and you won't get zero exactly, so it is better to compute the (Euclidean) norm and compare it to the product of the norms. Hence
$$(AB\times CD)^2<\epsilon^2\,AB^2\,CD^2.$$
Note that this is the same as normalizing the vectors to unit length and computing the norm of the cross-product, which is the sine of the angle between them.
So in the above formula, you have $\epsilon\approx\sin\epsilon$ and $\epsilon$ can be interpreted as an angle tolerance, in radians.
$\endgroup$ 2 $\begingroup$The two lines are parallel just when the following three ratios are all equal: $$ \frac{ax-bx}{cx-dx}, \ \frac{ay-by}{cy-dy}, \ \frac{az-bz}{cz-dz} \ . $$ It's easy to write a function that returns the boolean value you need. But the floating point calculations may be problematical. If any of the denominators is $0$ you will have to use the reciprocals. If your points are close together or some of the denominators are near $0$ you will encounter numerical instabilities in the fractions and in the test for equality. Take care. Program defensively.
$\endgroup$ 1 $\begingroup$All you need to do is calculate the DotProduct. (Google "Dot Product" for more information.)
In detail:
If line #1 contains points A and B, and line #2 contains points C and D, then:
Calculate vector #1: Vector1 = A - B.
Calculate vector #2: Vector2 = C - D.
Then, normalize both vectors.
Then, calculate the dot product of the two vectors. (The dot product is a pretty standard operation for vectors so it's likely already in the C# library.) This will give you a value that ranges from -1.0 to 1.0.
If Vector1 and Vector2 are parallel, then the dot product will be 1.0. If the vector C->D happens to be going in the opposite direction as A->B, then the dot product will be -1.0, but the two lines will still be parallel.
There could be some rounding errors, so you could test if the dot product is greater than 0.99 or less than -0.99. In either case, the lines are parallel or nearly parallel.
If you google "dot product" there are some illustrations that describe the values of the dot product given different vectors. Here's one:
$\endgroup$ $\begingroup$Hint: Write your equation in the form $$\vec{x}=[ax,ay,az]+s[bx-ax,by-ay,bz-az]$$ where $s$ is a real number. Can you proceed? Or do you need further assistance? the other one $$\vec{x}=[cx,cy,cz]+t[dx-cx,dy-cy,dz-cz]$$ where $t$ is a real number. Now you have to discover if exist a real number $\Lambda such that
$$[bx-ax,by-ay,bz-az]=\lambda[dx-cx,dy-cy,dz-cz]$$
$\endgroup$ 3 $\begingroup$Recall that given $2$ points $P$ and $Q$ the parametric equation for the line passing through them is
$$P+t(Q-P)=P+tv$$
with $v=Q-P$ the direction vector.
Then, let consider the direction vectors
- $v_{AB}=(ax-bx,ay-by,az-bz)$
- $v_{CD}=(cx-dx,cy-dy,cz-dz)$
if they are multiple, that is linearly dependent, the two lines are parallel.
$\endgroup$ 1 $\begingroup$Write a helper function to calculate the dot product:
double Dot(CSVector a, CSVector b)
{ return a.X*b.X + a.Y*b.Y + a.Z*b.Z;
}then the two lines are parallel if:
double productOfLengths = Math.Sqrt(Dot(left,left) * Dot(right, right));
bool parallel = productOfLengths > epsilon && Math.Abs(Dot(left, right)) > Math.Cos(tolerance) * productOfLengthswhere tolerance is an angle (measured in radians) and epsilon catches the corner case where one or both of the vectors has length 0
Unlike the solution you have now, this will work if the vectors are parallel or near-parallel to one of the coordinate axes.
Also make sure you write unit tests, even if the math seems clear. Include corner cases, where one or more components of the vectors are 0 or close to 0, e.g.
$left = (1e-12,1e-5,1); right = (1e-5,1e-8,1)$
should be parallel and
$left = (1e-5,1,0.1); right = (1e-12,0.2,1)$
should not - I think your code gives exactly the opposite result.
Note: I think this is essentially Brit Clousing's answer. But since you implemented the one answer that's performs worst numerically, I thought maybe his answer wasn't clear anough and some C# code would be helpful
$\endgroup$ 2
