# Find point closest to three lines

1. Sep 13, 2011

### takbq2

1. I would actually rather not give the equations. I'm not looking for someone to do this for me I just want a very quick reference on where to start or how to structure the solution and I can get it on my own.

2. I think Least Squares? This is why I haven't started it because I'm not sure the relevant equations.

Last edited: Sep 13, 2011
2. Sep 13, 2011

### phinds

Are the 3 lines in 3D space or 2D space? I don't have a solution for you, but I do know that for there to BE a solution, this has to be specified.

3. Sep 13, 2011

### takbq2

whoops, 2D. y = 2-x, y=3-2x, and y = -6+4x

4. Sep 13, 2011

### hotvette

The fundamental approach is the same as least squares, though the term usually refers to curve fitting situations where the number of data points is more than the number of unknown function parameters.

The key here is to recognize this as a function minimization problem and establish (1) the correct function to be minimized and (2) the unknowns. After that, it's a straightforward multi-variable minimization problem.

Last edited: Sep 13, 2011
5. Sep 15, 2011

### takbq2

My intuition tells me that I need to do something like pick (guess) a point pretty close to all three (just looking at them after plotting all three with arbitrary x's) then use the distance formula for the distance between a point and a line, and minimize d. That would get me minimized to one line, but it would put me on the line unless I use the other lines as constraints. Hmm.. lagrange multipliers? This is supposed to be an easy question and I am stupidly missing something big.

By the way, thanks for your input hotvette.

6. Sep 15, 2011

### phinds

I would start by finding the equation of the line that bisects the angle between two of the other lines and that is the bisector that has the least distance to the 3rd line. Then find a point on the bisector line and get the distance to all three lines and minimize that quantity.

This approach sounds baggy as hell to me and would result in very messy algebra but is the only think I can think of that would get you there and I'm not even sure it would get the absolute min since I can't think why the min would have to be on a bisector.

Hovetts' statement that it would then be a "straightforward multi-variable minimization problem" seems to me to gloss over some REALLY ugly algebra.

I agree w/ you that it just seems like there should be some simple (at LEAST conceptually simple) and elegant approach but I don't see what it is.

7. Sep 15, 2011

### hotvette

How ugly things get depends on whether the answer can be numeric only or needs to be an algebraic expression. The numeric approach is straightforward:

1. Write a single expression for the qty to be minimized. In this case, the sum of distances between an unknown point x*, y* and the three lines. Hint: it is a LOT easier to deal with distance squared rather than distance.

2. There are 5 unknowns: the coordinates of the point x*, y* and x-values on the three lines that represent the location of the shortest distance (the y-values come from the equations of the lines). Note: we all know the shortest distance to each line happens to be normal to the line, but that can be completely ignored when treating this as a simple function minimization problem.

3. Set partial derivatives of the fuction (i.e. sum of squared distances) with respect to each of the 5 unknowns equal to zero

4. Result is a 5 x 5 linear matrix equation that can be solved numerically for the 5 unknowns. The 5 equations could, in fact, be solved algebraically, but that would be quite ugly.

An algebraic approach can be as follows:

1. Assume a fixed point x*, y* and use calculus to find the shortest distance to one of the lines. Result is an algebraic expression for the x-value on the line in terms of x*, y* and known line parameters. Same result could be obtained using geometry.

2. Repeat step 1. for the remaining 2 lines. This can be done by inspection.

3. Write a single expression for the qty to be minimized. In this case, there will only be two unknowns (x*, y*). Setting partial derivatives wrt to the unknowns equal to zero results in two equations and two unknowns that can be readily solved algebraically. Ugly for sure.

If this is suppose to be an easy question, then I'm missing something also. Lagrange multipliers? Hmmm....maybe.

Last edited: Sep 15, 2011
8. Sep 15, 2011

### takbq2

Thanks a lot, phinds and hotvette. I'll have at it for awhile.

9. Sep 15, 2011

### hotvette

Ah, I found an elegant trick. The key is a concise expression for the distance from a point to a line:

http://www.intmath.com/plane-analytic-geometry/perpendicular-distance-point-line.php

Once you have that, the expression for sum of squared distances from the point to the 3 lines isn't so ugly. Note the comment part way down in the link:

Last edited: Sep 15, 2011
10. Sep 15, 2011

### takbq2

I'm def. going to do it numerically. I just need to get the matrix. I see what you are saying how there are 5 unknowns, but in my term to be minimized I only have two, (a,b), the unknown point. So I can't take partials w/r/t each of the 5 variables. Did I do something wrong?

The distance between a point and a line in y = mx + b form (which mine are) is

| y0 - mx0 - b| / sqrt(m2 + 1)

where x0 and y0 is the point I'm looking for.

But then you square this formula for simplicity because finding the smallest sum of the squares of the distances will minimize just as well as finding the smallest sum of the distances.

so then you just get the same formula with the numerator in parentheses and squared instead and the sqrt gone from the denominator.

Apply this formula to each of my three lines and sum:

d(line one) + d(line 2) + d(line 3)

but it does not contain the other three unknowns because the d formula only uses the point and slope of the other lines which are known....

so how do I get my 5x5 matrix :(

11. Sep 15, 2011

### takbq2

whoa, we posted same time -- it looks like that is what I've done.. but now what about my matrix? I have the expression to be minimized but it only contains the unknown point unknowns a and b.

12. Sep 15, 2011

### takbq2

In other words, how do I minimize:

(x0+y0-2)2
2

+

(2x0+y0-3)2
5

+

(-4x0+y0+6)2
17

Last edited: Sep 15, 2011
13. Sep 15, 2011

### hotvette

You are using the 2nd approach I mentioned which involves only two variables. OK, you have a function of two variables that you want to minimize. Using an analogy of a single variable function, what do you know about the derivative at the minimum? Same concept applies to multi-variable problems only you use partial derivatives (thus two equations in the case of two variables). Result should be two equations in x0 and y0 that can be solved by substitution. Pure algebraic solution. You are almost there.

Other side of the equal sign is the symbol representing the function to be minimized. Use whatever you want, doesn't matter.

Last edited: Sep 15, 2011
14. Sep 15, 2011

### takbq2

I got (1.04,2.55). I'm going to try to check it.

15. Sep 15, 2011

### takbq2

uh.. hmm. how can I check it? I tried against plots of the lines using an array of arbitrary x's. It doesn't seem right.

16. Sep 15, 2011

### takbq2

i did something wrong. chain rule still applies to partial derivatives right?

17. Sep 15, 2011

### hotvette

You have a function with two variables (x0 and y0). I don't see how the chain rule is needed.

There are a couple of practical ways to check. One is to verify that the expressions for the partial derivatives are indeed zero using the values of x0 and y0. The other way is to calculate the sum of distances and see if the sum increases or decreases with small changes in both directions of x0 and y0. That's basically a way to numerically determine the partials are zero. Better yet, plot sum of square distances as a function of x0 and y0 keeping each one constant while varying the other. You should see a nice parabolic looking plot in each case.

Last edited: Sep 15, 2011
18. Sep 15, 2011

### takbq2

when im taking the partial derivative of, say, x and the function is, say, (4x-2y)2

is the partial derivative not 2(4x-2y)*4

19. Sep 15, 2011

### takbq2

Sweet, I found a mistake in my calculation. I have something to go of of.

20. Sep 15, 2011

### takbq2

This time I got (1.517,0.317). It is still wrong, though, graphically the y-coordinate looks correct. I am stuck :S