Transform math formula into code (line-line intersection)

Question

I'm having hard times transforming a math formula to code. I can solve it on the paper easily, but it's hard for me to bring it into code form. Is it generally possible to bring a math formula directly into a program, or, if not, how can it be transferred?

Taking, for example, the Pythagorean Theorem: a² + b² = c². Having a and b defined in the code, it is straight forward to apply this formula.

c = sqrt(pow(a, 2) + pow(b, 2))

Currently, I'm having hard times bringing the line-line intersection, that I've solved on paper, into my program. Assuming a line being defined as L: O + a * D, one can find the intersection of two lines by setting them as equal.

L1: O1 + a * D1
L2: O2 + b * D2

=> O1 + a * D1 = O2 + b * D2

Using pen an paper, I would have already defined values and can solve the equation by splitting the equation into three sub-equations and applying simple substituion (I hope you can read my hand writing):

My actual problem

... is that substitution can not be applied algorithmically, or I don't know how to do. The equation L1 = L2 must be transformed to a generalized formula that can be directly translated into code (like a² + b² = c²), but I don't know how.

I was hoping for a step-by-step explanation (either as answer or linked) on how to come to the formula/algorithm I am searching for. I know there are quite many websites that describe the intersection of two lines, but I would like to understand how to find the algorithm from a mathematical starting point.

Answer 1

As you already suggest in your question, there is a big difference between implementing a formula, and implementing a calculation routine. Your paper solution is a routine, not a formula.

• You needed paper to write down numbers as intermediate results. Your algorithm will need something similar. Algorithms for solving systems of equations typically manipulate a matrix (2D array) of numbers. Put your equation factors into an 2D array, and try to describe the substitions as an operation on that matrix.

• When solving this on paper, you take decisions along the way. Eg. You choose to combine the first and third equation and solve that towards R. Then you used the second equation to solve p. This will not always work if there are some 0 factors in your equation. You might need to solve towards another variable, or combine the equations in a different order. The algorithm needs to take into account all these scenarios.

• Your problem is 'overdetermined': In general, 2 lines in 3D will not intersect. It will require a 'lucky shot' (special case) for them to intersect. Your paper example happens to have a solution. And it happens to be round numbers: easy to check. What if your first solution for P would be 1.0 and your second solution would be 0.9999999? Would that be a rounding error of the algorithm, or would the problem have no solution?

Answer 2

I'd probably suggest taking a pair of the sub-equations and seeing if there is a unique solution that can then be used for the third line. There are a few special cases to handle algorithmically:

1. If the two lines are in fact the same line. This could be easily solved by seeing that D1 is a multiple of D2. Note that in this case, all the points of the line are the intersection.

2. Standard case: Take the top pair of equations to get a system of 2 equations in 2 unknowns that could be solved via Matrix arithmetic. It is possible to compute an inverse of a 2 x 2 matrix and thus this gives a solution if the determinant isn't zero. This then gets applied to the other dimensions to see that the solution does in fact hold and if so is in fact a solution.

3. If the lines don't intersect. Consider line 1 that goes through (0,0,1) and has slope (0,1,0) and line 2 that goes through (1,0,0) and has slope (0,0,1). These lines don't intersect at all as all the points of the first line have an x-coordinate of 0 and the second line has an x-coordinate of 1.

At least, this is how I'd handle it programatically. You could consider line 1 going through (a,b,c) with slope (d,e,f) and line 2 going through (g,h,i) and with slope (j,k,l) and consider the algebra to generate the formulas to do this in code.