Register to reply 
Finding Collinear Points Given 1 point and 2 lines 
Share this thread: 
#1
Nov1512, 11:25 AM

P: 6

Hello 
I need help finding collinear points: Given: Equations of 2 lines, L1 and L2 1 points, P3 Want to find points P1 and P2 that lie on L1 and L2 respectively that are collinear to P3. I know that there can be multiple combinations of points P1 and P2 so to narrow down the list to just one set, I want to minimize the distance between P1 and P2. I'm trying to program this into an excel macro, so the method which would take the least computation time would be great. Thanks in advance! 


#2
Nov1512, 12:11 PM

P: 204

Hmm, are L1 and L2 parallel? Because if they aren't, the shortest distance between P1 and P2 will always be 0, when P1 and P2 both lie at the intersection point. Of course, this would satisfy collinearity because they would all lie on the line between the intersection and P3.
If they are parallel, then the shortest distance will be given by placing P1 and P2 at the intersections of L1 and L2 with a line through P3 that has a slope perpendicular to L1 and L2. I'm just going of the top of my head here, so let me know if I'm missing something... 


#3
Nov1512, 12:37 PM

P: 6




#4
Nov1512, 12:53 PM

P: 144

Finding Collinear Points Given 1 point and 2 lines
Btw, are you sure you are talking about points and lines in the plane? If it all happened in 3dimensional space, you actually have a meaningful question with a unique answer in the general case. 


#5
Nov1512, 01:21 PM

P: 6

This is all in a 2D plane. How is there more than one answer to the question? I think I've constrained it enough that there is only one answer. 


#6
Nov1512, 02:07 PM

P: 144




#7
Nov1512, 02:21 PM

P: 6

L1 has a range of values (x1,y1) to (x2,y2) L2 has a range of values (x3,y3) to (x4,y4) The points P1 and P2 have to fall into the range of their respective lines and the range does not contain the intersection of L1 and L2. 


#8
Nov1512, 02:30 PM

P: 999

The shortest distance must be achieved from an endpoint on the one line segment to an endpoint on the other line segment or from an endpoint on one line segment to an interiior point on the other line segment. I count eight cases to examine to determine the minimum distance. 


#9
Nov1512, 02:49 PM

P: 144

1) In most cases, there are no such P1 and P2 collinear with P3. 2) When such P1 and P2 do exist, they may very well be interior points, so what jbriggs say above is just wrong. 


#10
Nov1512, 02:52 PM

P: 6




#11
Nov1512, 07:52 PM

P: 204




#12
Nov1512, 07:57 PM

P: 204

Also, are the endpoints given in a particular order: i.e. L1 (a,b) to (c,d) where a<c and b<d, or something like that? The format of your input/spreadsheet, and any assumptions given would help determine the best computational route.
Edit: Finally, just to clarify, you want to find points with the shortest distance between P1 and P2... NOT with the shortest line segment connecting P1, P2 and P3, correct? 


#13
Nov1612, 07:52 AM

P: 6

1. get the slope and yintercept of both lines 2. Solver is set up to vary P1 and P2 until the distance between P1,P2 is minimized with the constraint that P1,P2,P3 are on the same line, distance between P1,P2 is greater than 1(to avoid the intersection point if there(safe assumption that distance is always >1 if possible)), the point P1 is greater than the min of segment L1 and less than the max of L1, the point P2 is greater than the min of segment L2 and less than the max of L2 Yes, shortest distance between P1 and P2. 


#14
Nov1612, 11:29 AM

P: 204

Actually, I think with some important exceptions, jbriggs444 is correct that the closest separation will often be the endpoint of one segment and somewhere in the middle of the other.
I just typed out a bunch of random ideas, but I'm not sure what you're looking for. There are a number of ways to go about this. If I was writing a python or C program to do this, I would probably write conditional statements defining all the possible exceptions and what to do in their cases, and then use the general rule if none of them applied. But with that said, it sounds like your looking for more of a brute force approach? I'm not familiar with how much you can make use conditional statements in a spreadsheet, if at all. If I'm off base here, let me know. One possible brute force method (that may need refinement): If you were to find the slopes of lines connecting P3 to each of the 4 endpoints (call the slopes s1, s1' (endpts of L1) s2, s2' (endpts of L2)), you could narrow your search down. If s1 and s1' are both < or both > than s2 and s2', you don't have any collinear points. That is, if [s1,s1'] doesn't intersect with [s2, s2']. If the ranges do overlap, then you only care about points P1 and P2 that have a line through P3 with a slope between the two middle values. To retirate, that is to say that L123 must have a slope that is in between s1 and s1' AND between s2 and s2'. In some cases, you'll still be checking all possible pairs, but this should help check for existence and narrow down your possible pairs in most cases. Do keep in mind that if you make an arbitrary minimum separation value, it is possible that you could get two line segments where collinear points exist, but with all P1 and P2 pairs having a separation >0 and <1. You may not care, but I think it's worth noting that you could have false negatives. 


#15
Nov1612, 12:21 PM

P: 999

Given that requirement it looks like one brute force approach would be to parameterize the problem in terms of the intersection point of a candidate shortestpath and one of the two lines and to express the parameter as the distance from one of the two segment endpoints. The candidate shortest path length would then be a [possibly messy] formula in one variable. The goal is to minimize the value of that function subject to the constraint that both intersection points lie within the two given line segments. The only possible minima are at the four boundaries (where the candidate shortest path intersects a segment endpoint) and any places where the first derivitive of the distance formula is zero. If one could solve for the zeroes of the first derivitive that then would lead to a bulky ifthenelse construct picking out a global minimum from the various candidates. 


#16
Nov1612, 05:29 PM

P: 204

After drawing out quite a few examples, I'm fairly confident that if solutions exist, they will involve at least one of the endpoints. Like I said, find the slopes from P3 to each of the endpoints. You just need to look for overlap between the ranges [S1, S1'] and [S2, S2']. The only exception I can find (other than intersection) is if the segments are parallel and P3 can be reached by a line perpendicular to BOTH of the segments. In that case, such a perpendicular line is actually the one connecting your P1 and P2 solutions. In other cases, parallel segments will still have a solution involving one of the endpoints.
If P3 = (1,1) L1: y1 = (1/2)x1 + 4 [endpts = (2,3) and (4,2)] L2: y2 = x2 + 8 [endpts = (2,6) and (4,4)] Then the end points of L1 and P3 give a slope range [(1/3), 2] The end points of L2 and P3 give a slope range [1, 5] Overlap is the range [1, 2], which in this case corresponds to the "bottom" endpt of L2 and "top" endpt of L1. The slopes of lines connecting all possible pairs of P1 and P2 will be between 1 and 2. (Try m = 2) > P3 line > y = 2x  1 P1 = (2,3) Find P2 > 2x1 = x+8 > x =3 > y = 5 P2 = (3,5) (Try m=1): > P3 line > y = x P2 = (4,4) Find P1 > x = (1/2)x + 4 > x = (8/3) > y = (8/3) P1 = (8/3, 8/3) With m = 2 you get a P1P2 distance of 2.24 With m = 1 you get a distance of 1.89 Any other solution will have a distance somewhere between these two. As I said, this holds in all cases I can think of drawing except the types of parallel lines I described at the top. Also, if the segments share an endpoint, finding P1 and P2 will be more complicated, but the [S1, S1'] overlap with [S2, S2'] still works to check existence of solutions, though note that the ranges will share a common endpoint, so you're looking to make sure they OVERLAP, not just touch. 


#17
Nov1712, 01:11 AM

P: 144




#18
Nov1912, 02:38 AM

P: 204

Nonetheless, even if an endpoint isn't involved in the solution, looking at the slopes between P3 and the endpoints is still of value in reducing the number of computations in a brute force approach. Unless I'm just going nutty, of course. 


Register to reply 
Related Discussions  
Finding the intersection points of the two lines in space  General Math  3  
Finding tangent lines that pass through given points  Calculus & Beyond Homework  5  
Finding two points on the vector joining two lines  Calculus & Beyond Homework  1  
Help with a question about collinear points  Calculus & Beyond Homework  2  
Can there be 3 collinear points in a curve?  General Math  25 